Travelling Salesman Problem

 

english version

 

Problemstellung:
Das sogenannte Travelling Saleman Problem stellt sich wie folgt:
Gegeben sind n Punkte (Städte) in der Ebene. Finde eine Rundreise (Tour), die jeden Punkt besucht und minimale Gesamtlänge hat. Dieses Problem ist NP-vollständig (triviale deterministische Lösung in Zeit O((n-1)! / 2) und daher für große n sehr zeitaufwändig. In diesem Projekt sollen Heuristiken implementiert werden, die eine möglichst gute Näherungslösung in vertretbarer Zeit finden.

Teilaufgaben:

  • Implementierung der Minimum-Spanning-Tree Methode, die eine Lösung garantiert, die höchstens doppelt so lang ist wie die optimale Tour.
  • Realisierung eines interaktiven Demo-Programmes unter Verwendung der GraphWin Klasse von LEDA.
  • Verbesserung der Lösung durch weitere heuristische Verfahren (lokale Optimierungen) mit Animation.
 

Hier finden Sie eine kurze Erklärung der im Folgenden verwendeten Begriffe.

Hier finden Sie ein kleines Demo-Programm zum Download.

Hier finden Sie einige allgemeine Erläuterungen zur Bedienung des Demo-Programms.

Lösungen

Lösung A (Minimum-Spanning-Tree Methode)
0. Eingabe der Knoten (Städte).
1. Berechnung des minimal aufspannenden Baumes (Minimum-Spanning-Tree) aus den zuvor eingegebenen Knoten.
2. Konstruktion einer Tour aus dem minimal aufspannenden Baum. mehr...
Die nächsten Schritte verbessern die Tour durch lokale Optimierungen.
3. Berechnung von Abkürzungen. mehr...
4. Anwendung von 2 - OPT mehr...

Lösung B (Minimum Weight Perfect Matching Methode)
0. wie 0. in A
1. wie 1. in A
2. Berechnung des Minimum Weight Perfect Matching der Knoten ungeraden Grades (Knoten an denen die Anzahl der Kanten ungerade ist). (Bemerkung: Die Anzahl der Knoten ungeraden Grades in einem Baum ist immer gerade. Die Voraussetzung um ein Perfect Matching berechnen zu können (und damit auch ein Minimum Weight Perfect Matching) ist somit erfüllt.)
Hinzufügen des Minimum Weight Perfect Matching in den minimal aufspannenden Baum. Als Resultat erhalten wir einen Graphen, der nur Knoten geraden Grades hat. Ein solcher Graph ist ein Eulergraph. Wir können also eine Tour als Folge von Kanten des Graphen bestimmen, mit der Eigenschaft, das jede Kante genau einmal benutzt wird.
3. Konstruktion einer Tour aus dem Graphen (Eulergraph).
Diese Tour hat höchstens die 1.5 - fache Länge der optimalen Tour
4. wie 3. in A
5. wie 4. in A