The Traveling Salesman
Ein zentrales Problem der kombinatorischen Optimierung
 

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.

TSP-Screenshot

Grundlagen

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

Programm für Windows

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

TSP-Programme kompilieren/selbst erstellen

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

Traveling Salesman-Verfahren

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

Externe Programme

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.


DOS-Programme

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

TSP-Titelbild

HACKER.EXE PAS_FORM.EXE TSP_PROT.EXE KURZPROT.EXE

Home | Cat's Eye | Kimagure | Fotos | Computer | NiNuM | TSP | Kontakt