Beim Traveling Salesman Problem (TSP) - einem zentralen Problem der kombinatorischen Optimierung - geht es darum, die kürzeste Rundreise durch eine gegebene Menge von Städten zu finden. Auf dieser Seite finden Sie u. a. ein Programm zum Ausprobieren verschiedener Lösungsverfahren, kurze Erläuterungen zu den Algorithmen inkl. Quelltexten sowie die notwendigen Werkzeuge, um mit geringen Basiskenntnissen in (Free-)Pascal oder einer anderen Programmiersprache schnell selbst eigene TSP-Programme erstellen zu können.
Die Programme dieser Seite dürfen zu nichtkommerziellen privaten und unterrichtlichen Zwecken kostenlos benutzt werden, sofern dies auch für Produkte gilt, die diese bzw. Teile daraus verwenden, und die Quelle angegeben ist. Veröffentlichung und kommerzielle Nutzung auf Anfrage.
Die Programme auf dieser Seite sind aus einer Arbeit an der
Universität des Saarlandes entstanden.
Hier einige Auszüge aus der Arbeit (die komplette Arbeit ist
auf Anfrage erhältlich):
| Inhaltsverzeichnis | Einführung | Programminfos | Heuristiken |
TSP_ALG ist ein ohne Installation unter Windows (unter Linux mit Wine) lauffähiges Programm, das alle im Folgenden beschriebenen Traveling Salesman-Algorithmen enthält und es erlaubt, diese unter einer grafischen Benutzeroberfläche zu testen.
| Programm herunterladen |
Um die untenstehenden Quelltexte oder eigene TSP-Programme zu kompilieren, benötigen Sie den kostenloses Free Pascal-Compiler sowie die Units GRAFIK, MAUS und TSP. Legen Sie dazu die vorkompilierten Dateien aus dem linken ZIP-Archiv im gleichen Verzeichnis wie den zu kompilierenden Quelltext ab oder verwenden Sie die Sourcen aus dem rechten ZIP-Archiv (ebenfalls im gleichen Ordner abzulegen). Weitere Details finden Sie unter Programminfos.
| TSP-Units | Sourcen der Units |
Hier nun die Quelltexte der einzelnen Verfahren, jeweils mit einer kurzen Erläuterung.
Bei manchen Heuristiken hängen die Ergebnisse vom Startpunkt ab, in diesem Fall sind
jeweils zwei Quelltexte vorhanden, einmal mit vorangestelltem "a_", einmal ohne. Bei
der Version ohne kann der Benutzer die erste Stadt der Rundreise selbst auswählen, bei
der mit werden alle Möglichkeiten ausprobiert und die beste Variante angezeigt.
Sollten Sie eigene Verfahren implementieren, die in die Tabelle und TSP_ALG aufgenommen
werden sollen, so würde ich mich über eine Nachricht
freuen.
| Nr. | Verfahren | Quelltext | Erläuterungen |
|---|---|---|---|
| Verwandte Probleme und Permutationen | |||
| 3.1 | Kürzeste Wege | DIJKSTRA.PAS | Verwandte Probleme und Permutationen |
| 3.2 | Minimal Spanning Tree | MST.PAS | |
| 3.3 | 1-Bäume | EINBAUM.PAS | |
| 3.4 | Permutationen | PERM.PAS | |
| Konstruktive Heuristiken | |||
| 4.1 | Roulette | ROULETTE.PAS | Konstruktive Heuristiken I |
| 4.2 | Nearest Neighbour | NN.PAS / A_NN.PAS | |
| 4.3 | Nearest Addition | NA.PAS / A_NA.PAS | |
| 4.4 | Insertion | INSERT.PAS | |
| 4.5 | Cheapest Insertion | CI.PAS / A_CI.PAS | |
| 4.6 | Nearest Insertion | NI.PAS / A_NI.PAS | |
| 4.7 | Farthest Insertion | FI.PAS / A_FI.PAS | |
| 4.8 | Nearest Merger | NM.PAS | |
| 4.9 | Minimal-Spanning-Tree-Rundreise | MSTR.PAS / A_MSTR.PAS | |
| 4.10 | Start-Nachbar-Verfahren | SN.PAS / A_SN.PAS | Konstruktive Heuristiken II |
| 4.11 | Optimiertes Start-Nachbar-Verfahren | OSN.PAS / A_OSN.PAS | |
| 4.12a | Minimum-SN-Insertion | MINSNI.PAS / A_MINSNI.PAS | |
| 4.12b | Maximum-SN-Insertion | MAXSNI.PAS / A_MAXSNI.PAS | |
| 4.13a | Minimum-OSN-Insertion | MINOSNI.PAS / A_MINOSNI.PAS | |
| 4.13b | Maximum-OSN-Insertion | MAXOSNI.PAS / A_MAXOSNI.PAS | |
| 4.14a | Minimum-Sum-Insertion | MINSI.PAS / A_MINSI.PAS | |
| 4.14b | Maximum-Sum-Insertion | MAXSI.PAS / A_MAXSI.PAS | |
| 4.14c | Minimum-Product-Insertion | MINPI.PAS / A_MINPI.PAS | |
| 4.14d | Maximum-Product-Insertion | MAXPI.PAS / A_MAXPI.PAS | |
| 4.15 | Kürzeste-Wege-Rundreise 1 | KWR1.PAS / A_KWR1.PAS | |
| 4.16 | Kürzeste-Wege-Rundreise 2 | KWR2.PAS / A_KWR2.PAS | |
| 4.17 | Kürzeste-Wege-Rundreise 3 | KWR3.PAS / A_KWR3.PAS | |
| 4.18 | Kürzeste-Wege-Rundreise 4 | KWR4.PAS / A_KWR4.PAS | |
| 4.19 | Kürzeste-Wege-Rundreise 5 | KWR5.PAS / A_KWR5.PAS | |
| 4.20 | Kürzeste-Wege-Rundreise 6 | KWR6.PAS / A_KWR6.PAS | |
| Optimierende Heuristiken | |||
| 5.1 | 2-Städtetausch (steilster Abstieg) | STAUSCH1.PAS | Klassische optimierende Heuristiken |
| 5.2 | 2-Städtetausch (erster Schritt) | STAUSCH2.PAS | |
| 5.3 | 2-Kantentausch (steilster Abstieg) | KTAUSCH1.PAS | |
| 5.4 | 2-Kantentausch (erster Schritt) | KTAUSCH2.PAS | |
| 5.5 | 3-Kantentausch | DKTAUSCH.PAS | |
| 5.6a | 2+3-Kantentausch (steilster Abstieg) | ZDKT1.PAS | |
| 5.6b | 2+3-Kantentausch (erster Schritt) | ZDKT2.PAS | |
| 5.7 | Simulated Annealing | SIMANN.PAS | Moderne optimierende Heuristiken |
| 5.8 | Threshold Accepting | THRESACC.PAS | |
| Exakte Lösungen | |||
| 6.1 | Branch and Bound | BAB.PAS | Exakte Lösungen |
Zur TSP-Berechnung können von TSP_ALG auch externe Programme aufgerufen werden, so dass man Lösungsalgorithmen auch in anderen Programmiersprachen als Pascal erstellen kann. Dazu ist unter "Verfahren" der entsprechende Punkt auszuwählen und beim Starten der Berechnung das Kommando zum Aufruf des Programms anzugeben. Die notwendigen Daten werden diesem als Kommandozeilenparameter in der Reihenfolge Stadtanzahl - Werte der Entfernungstabelle - Städte des aktuellen Weges - Startpunkt übergeben, während die Lösung vom externen Programm in Form der Städtenummern (jeweils eine Nummer pro Zeile) auf die Standardausgabe zu schreiben ist (Hinweis: Bei großen Städtezahlen kann unter Umständen der Programmaufruf aufgrund des Überschreitens der vom Betriebssystem vorgegebenen maximalen Länge der Kommandozeile scheitern.).
| TSP.class / NN.class / STausch2.class | TSP.java / NN.java / STausch2.java |
In der obigen Tabelle finden Sie als Beispiel in Java implementierte Versionen des Nearest Neighbour-Verfahrens und des 2-Städtetauschs (erster Schritt). Die drei class-Dateien sind in das gleiche Verzeichnis wie TSP_ALG zu kopieren und können dann, sofern auf dem Rechner Java installiert ist, mit der Angabe "java NN" bzw. "java STausch2" bei der Frage nach dem (Start-)Kommando verwendet werden.
Die Originalversionen der Programme waren mit Turbo Pascal für DOS geschrieben worden. Aus "historischen Gründen" finden Sie diese hier:
| Bilder | TP 4.0-Units | TP 5.5-Units | TSP_ALG.EXE |
| HACKER.EXE | PAS_FORM.EXE | TSP_PROT.EXE | KURZPROT.EXE |