T S P - Traveling Salesman Problem

Inhaltsverzeichnis

VORWORT

Abbildungsverzeichnis

Tabellenverzeichnis

Verzeichnis der Aufstellungen

1. Der bisherige Forschungsstand
1.1. Komplexitätstheorie und „Meilensteine“
1.2. Das Näherungsverfahren CONCORDE

2. Ergebnisse I Allgemeine Grundlagen
2.1. Die äußere Reihenfolge
2.2. Klassische und nichtklassische Traveling Salesman Probleme (TSP´s) , Kosten und Kausalität
2.3. Enumeration: die Wahl der minimalsten Struktur kann in die Irren führen
2.4. Aufwandsberechnung und die Ankerung von „Orten“
2.5. TSPLIB und CONCORDE

3. Ergebnisse II Geometrisch-geographische Systeme und das Gegenteil
3.1. Lösung euklidischer TSP`s
3.1.1. Das euklidische TSP als Naturgesetz
3.1.2. Die wahllose Veränderung der Grunddaten
3.2. Lösung allgemeiner TSP`s
3.2.1 TSP`s und reale Entfernungstabellen
3.2.2. Symmetrische und unsymmetrische Entfernungstabellen
3.3. Vergleich der Lösungen euklidischer und realer TSP`s
3.4. „Lösung“ allgemeiner TSP`s mit Wegekreuzungen
3.5. Chaotische Systeme

4. Ergebnisse III Verfahrensgrundlagen
4.1. Richtungen
4.2. Kommutativität
4.3. Parallelität
4.4. Zeitaspekte

Literaturhinweise

VORWORT

Dieses Buch über das Traveling Salesman Problem (TSP) (Problem des Handlungsreisenden, Rundreiseproblem) und dessen konkreter, zeitnaher und nachweisbarer Lösung entstand während der letzten 12 Monate innerhalb meiner Freizeit. Die Idee, zwei Bücher über das TSP-Lösungsverfahren zu veröffentlichen, entstand aus dem Wunsch heraus, die wichtigsten der nahezu unzähligen Details an Untersuchungen, Ergebnissen und Fakten während der Jahre 1995 bis heute in kompakter Form zusammenzustellen. In dieser Zeit ergab sich ein erheblicher Fundus an Wissen über das TSP und seine Anwendungen.

Ein solcher Wissensfundus fordert allerdings seinen Preis: Jahrelange Unsicherheiten über aufgeworfene Fragen, die sich dann im Laufe der Jahre beantworten ließen. Nicht zuletzt setzt ein gefundenes und genau erklärbares Lösungsverfahren voraus, sich im bekannten „stillen Kämmerlein“ über Jahre hinweg täglich 10 – 12 Stunden mit dem Problem auseinander gesetzt zu haben.

Ein weiterer in diesem Buch behandelter Aspekt ist die mittlerweile chaotische Informationsvielfalt über das TSP, wobei gerade in der Fachwelt in den letzten 30 Jahren Gedankenansätze entwickelt wurden, die uns nicht helfen, das TSP in den Griff zu bekommen.

Das Buch kommt nicht nur mit einem Beispiel aus. Euklidische, aber auch allgemeine TSP-Instanzen (u.a. in der Tourplanung) werden an Beispielen erörtert.

Das vorliegende Buch wendet sich nicht nur an die akademische Welt, vielmehr werden die einzelnen Vorgehensweisen zur Lösung von TSP`s in beiden Büchern für die Anwendungen der Praxis verfasst, so dass mathematische Grundlagenkenntnisse für das Verständnis ausreichend sind. Weiterhin werden die gesamten Erkenntnisse systematisch so aufbereitet, dass die Programmierung des Verfahrens auf eigener Hard- und Softwareplattform ohne Probleme möglich ist.

In beiden Bänden erhält der Leser nicht nur die Information darüber, wie bestimmte Vorgehensweisen funktionieren, sondern auch, warum eine bestimmte Herangehensweise bzw. algorithmische Vorgehensweise notwendig ist.

Das zu beschreibende Lösungsverfahren ist somit kein Näherungsverfahren (Heuristik), sondern in seinen algorithmischen Eigenarten einmalig: Die zeitnahe Berechnung der konkreten und beweisbaren Minimalstreihenfolge.

Nahezu alle in diesem Band verwendeten Daten (Entfernungstabellen, Koordinaten) können unter http://www.chiemseeforum.de kostenlos heruntergeladen werden. Bei Angabe von Koordinaten sind lediglich teilweise die dazugehörigen Entfernungstabellen selbst zu berechnen.

Die Daten der TSPLIB-Instanzen können an der Universität Heidelberg unter http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ heruntergeladen werden.

Im 2. Band dieses Buches erfolgt die ausführliche algorithmische Beschreibung des Lösungsverfahrens zuzüglich Implementierungshinweisen.

Abbildungsverzeichnis

Abbildung 1 CONCORDE-Lösung eines euklidischen TSP n = 50 (pla.tsp)

Abbildung 2 Verfahrenslösung eines euklidischen TSP n = 50 (pla.tsp)

Abbildung 3 Bildung der äußeren Reihenfolge eukl. TSP n = 11 (koord.11c)

Abbildung 4 Bildung der äußeren Reihenfolge eukl. TSP n = 11 (koord.11c)

Abbildung 5 Eingetragene äußere Reihenfolge eukl. TSP n = 11 (koord11.c)

Abbildung 6 Eingetragenes Fadenkreuz eukl. TSP n = 11 (koord.11c)

Abbildung 7 Eingetragene Lösung eukl. TSP n = 11 (koord.11c)

Abbildung 8 Euklidisches Ausgangs-TSP n = 11 (koord.11c)

Abbildung 9 Modifizierte äußere Reihenfolge eukl. TSP n = 11 (koord.11c)

Abbildung 10 Modifizierte äußere Reihenfolge eukl. TSP n = 11 (koord.11c)

Abbildung 11 Eukl. TSP n = 11 mit eingetragener äußerer Reihenfolge (koord.11)

Abbildung 12 „Befahren“ des „Ortes“ 8 im eukl. TSP n = 11 (koord.11c)

Abbildung 13 „Befahren“ des „Ortes“ 6 im eukl. TSP n = 11 (koord.11c)

Abbildung 14 Eingetragene falsche Lösung im eukl. TSP n = 11 (koord.11c)

Abbildung 15 Falsche Lösung ohne Ankerfehler im eukl. TSP n = 11 (koord.11c)

Abbildung 16 TSPLIB-Lösung eil51 n = 51 euklidisch

Abbildung 17 CONCORDE-Lösung eil51 n = 51 euklidisch

Abbildung 18 Verfahrenslösung eil51 n = 51 euklidisch

Abbildung 19 1. CONCORDE-Lösung eukl. TSP n = 50 (concorde50)

Abbildung 20 2. Lösung CONCORDE platine.tsp

Abbildung 21 CONCORDE-Lösung eukl. TSP n = 50 (pl2.tsp)

Abbildung 22 Verfahrens-Lösung eukl. TSP n = 50 (pl2.tsp)

Abbildung 23 Eukl. Europa-TSP n = 11 (koord11.eur)

Abbildung 24 Lösung eukl. TSP n = 11 (koord.11c)

Abbildung 25 Eukl. Europa-TSP n = 11 (koord11.eur)

Abbildung 26 Real TSP n = 26 (Jochen Pleines) (mindkm.26b)

Abbildung 27 Real TSP n = 26 Lösung Jochen Pleines (mindkm.26b)

Abbildung 28 Real TSP n = 26 (Jochen Pleines) Modifiz. Lösung (mindkm.26c)

Abbildung 29 Real TSP n = 26 (Jochen Pleines) eukl. Lösung (koord.26)

Abbildung 30 Allgemeines TSP n = 11 (mindkm.alg)

Abbildung 31 Allgemeines TSP n = 11 und äußere Reihenfolge (mindkm.alg)

Abbildung 32 Allgemeines TSP n = 11 und äußere Reihenfolge (mindkm.alg)

Abbildung 33 Eukl. TSP n = 11 und äußere Reihenfolge (koord.11c)

Abbildung 34 Eukl. Ausgangsproblem n = 11 (koord.11)

Abbildung 35 Eukl. TSP n = 11 und äußere Reihenfolge (koord.11)

Abbildung 36 Vergleich Kurvenverläufe n! und 25n4 - 78n3 + 59n2 – 6n

Tabellenverzeichnis

Tabelle 1 Eukl. Entfernungstabelle zu koord.11c (mindkm.11c)

Tabelle 2 Eukl. Entfernungstabelle zu koord.11c (mindkm.11c)

Tabelle 3 Modifizierte eukl. Entf.-Tabelle zu koord.11c (mindkm.11m)

Tabelle 4 Symm. Entf.-Tabelle real z. koord11.eur (mindkm11.r02)

Tabelle 5 Unsymm. Entf.-Tabelle real z. koord11.eur (mindkm.11r)

Tabelle 6 Unsymm. Entf.-Tabelle real z. koord11.eur (mindkm11.r2)

Tabelle 7 Symm. Entf.-Tabelle real z. koord11.eur (mindkm11.r02)

Tabelle 8 Eukl. Entf.-Tabelle z. koord11.eur (mind11.eur)

Tabelle 9 Entf.-Tabelle symmetrisch-real z. allgemeinen TSP (mindkm.alg)

Tabelle 10 Eukl. Entfernungstabelle z. koord.11 (mindkm.11)

Tabelle 11 Zeitangaben n = 50 bis n = 30.0000

Tabelle 12 Zeitangaben n = 30 bis n = 100

Verzeichnis der Aufstellungen

Aufstellung 1 Koordinaten zu Abb. 1,2 (pla.tsp)

Aufstellung 2 Prüfung der Ankerung zu Abb. 1 (pla.tsp, mindkm.pla)

Aufstellung 3 Die Koordinaten koord.11 (koord.11, mindkm.11)

Aufstellung 4 Ergebnisse der Enumeration entspr. koord.11, mindkm.11

Aufstellung 5 Überprüfung der Ankerung koord.11c

Aufstellung 6 Auflistung der Städtereihenfolge eil51 entspr. TSPLIB

Aufstellung 7 Speicherung der Koordinaten concorde50 entspr. platine.tsp

Aufstellung 8 Auflistung der Koordinaten entspr. pl2.tsp

Aufstellung 9 Auflistung der Koordinaten entspr. koord11.eur

Aufstellung 10 Auflistung der Koordinaten entspr. koord.11c

1. Der bisherige Forschungsstand

1.1. Komplexitätstheorie und „Meilensteine“

Die zweifelsohne bekannteste Aufgabenstellung innerhalb der kombinatorischen Optimierung ist das Traveling Salesman Problem (TSP)(Problem des Handlungsreisenden, Rundreiseproblem). Dabei soll ein Handlungsreisender eine bestimmte Anzahl anzufahrender Städte so miteinander verbinden, dass die abgefahrene Gesamtstrecke die minimalste überhaupt ist. Der Handlungsreisende beginnt seine Fahrt an seinem Ausgangsort, besucht die anderen Orte genau einmal und kehrt dann wieder zu seinem Ausgangsort zurück. Die vorstehende klassische Definition bzw. Problembeschreibung des TSP wurde bewußt als Minimierungsaufgabe und unter Hinzuziehung von Entfernungen gewählt. Denkt man beispielsweise an die Maximierung z.B. von Gewinneinheiten statt der Minimierung von Entfernungen, so - dies wird in diesem Buch beschrieben - reicht das Herumdrehen der Kleiner-Bedingung nicht aus.

Bislang mußte das TSP - trotz jahrzehntelanger Erforschung durch Fachleute an Universitäten, Instituten und Firmen - als ungelöst betrachtet werden, wobei sich die Unlösbarkeit genau genommen auf die Zeit bezieht, ein TSP überhaupt lösen zu können. Je größer die Aufgabenstellung, desto unmöglicher war die Berechnung der konkreten Lösung mittels der Aufzählung aller Kombinationsmöglichkeiten (vollständige Enumeration). Auch mit den leistungsfähigsten Rechnern weltweit war und ist dies in nur einem extrem kleinen Rahmen möglich.

Man behalf und behilft sich daher mit Näherungsverfahren, welche allerdings nicht in der Lage sind, die berechnete Minimalstreihenfolge nachzuweisen. Bei zahlreichen Näherungsverfahren wird zudem darauf hingewiesen, dass die mit diesen Verfahren erzeugten Lösungen nur um einige Prozent schlechter sind als das wirkliche Optimum (Minimum). Es dürfte ausreichend sein festzustellen, dass derartige Aussagen den Bereich der Spekulation betreten. Es ergibt sich von selbst, dass konkrete Aussagen über die Güte einer Lösung nur dann zuverlässig sind, wenn das Optimum tatsächlich bekannt ist. Tatsächlich wiederum heißt, dass das Optimum nachzuweisen ist.

In den Anfängen der TSP-Untersuchung bestand die Hoffnung, dass das Finden eines Lösungsverfahrens für das TSP vielleicht sogar auch für die Lösung anderer kombinatorischer Optimierungsprobleme heranzuziehen wäre oder wenigstens Erkenntnisse zur Angehung dieser Probleme lieferte.

Diese durchaus natürliche Hoffnung auf Übertragbarkeit eines vermeintlichen Lösungsverfahrens wurde dann Anfang der 70er des 20. Jahrhunderts bei weitem in den Schatten gestellt: die Komplexitätstheorie. Sie besteht nicht aus natürlichem Hoffen, sondern aus Übertreibungen und Behauptungen en mass:

Wenn das TSP (in sog. polynomialer Zeit) lösbar ist, dann sind auch andere kombinatorische Optimierungsprobleme, die zur selben Klasse wie das TSP gehören, ebenfalls lösbar.

Es ist mehr als verwunderlich, dass es so zahlreiche Menschen gibt, die diese Haltung annehmen und das kritische Hinterfragen aufgegeben haben. Sie nehmen es einfach hin. Tatsächlich wird das TSP als geometrisch-geografische Aufgabenstellung gleichgesetzt mit beispielsweise dem sog. Stundenplanproblem, bei dem es um die Zuordnung von Objekten zu Raum- und Zeitressourcen geht. Hierbei muss dann eine möglichst große Anzahl von Nebenbedingungen erfüllt sein. Die einzige Verwandtschaft beider Aufgaben besteht darin, dass sie als kombinatorische Optimierungsprobleme nur mit der (unmöglichen) Aufzählung aller Kombinationen der jeweiligen Elemente theoretisch lösbar wären. Weitere Verwandtschaften gibt es nicht.

Während der vergangenen etwa 30 Jahre wurden zahlreiche TSP-Instanzen insbesondere durch amerikanische und deutsche Universitäten bzw. Fachleute „gelöst“. Auch hierbei war und ist festzustellen, dass diese „Lösungen“ als die tatsächlichen Lösungen der jeweiligen Systeme verkauft wurden und werden. Es erfolgte – mit Ausnahme der TSP-Instanz von Dantzig 1954 – kein Nachweis der minimalsten Lösung sowie selten Angaben über Zeitdauer der Berechnung dieser „Lösungen“.

Vielfach wurden und werden diese „Lösungen“ als „Meilensteine“ der TSP-Forschung verkauft, während gleichzeitig postuliert wird, dass das TSP auch für kleinere Instanzen ab etwa n = 30 nicht mehr in vernünftiger Zeit lösbar sei. Hier ergibt sich eine deutliche Widersprüchlichkeit. Man hat manchmal den Eindruck, dass gerade große „gelöste“ Instanzen (USA, Deutschland, Schweden) lediglich durch ihre Größe beeindrucken sollen.

1.2. Das Näherungsverfahren CONCORDE

Zur Aufstellung obiger „Meilensteine“ wurde das in den 90ern des 20. Jahrhunderts am Georgia Institute of Technology entwickelte Programm „CONCORDE“ eingesetzt. Seit einiger Zeit ist das Programm unter www.tsp.gatech.edu/concorde.html herunterladbar.

Das folgende euklidische TSP (Bohrung einer Platine) ist mittels des konkreten Verfahrens und mittels CONCORDE berechnet worden:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 CONCORDE-Lösung pla.tsp

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2 Verfahrenslösung pla.tsp

Bei der CONCORDE-Lösung (Abb. 1) fallen die für euklidische TSP unüblichen Wegekreuzungen auf. Diese sind im Rahmen der Euklidischen Geometrie nie optimal (minimal). Gleichzeitig ist die CONCORDE-Lösung noch erheblich verbesserbar, da einige „Orte“ (Markierungen) noch minimaler in die behauptete Reihenfolge einfügbar sind (Ankerfehler). Sehr häufig wird bei CONCORDE-Lösungen eine Gütegarantie von weit unter 3% gegeben (< 3% Abweichung vom Optimum (Minimum)). In diesem kleinen Beispiel ist nachweisbar, dass die Abweichung zum Minimum rund 9% beträgt, was nach erheblichen Einsparungspotentialen verlangt. Die Abb. 2 zeigt die minimalste Reihenfolge des Bohrer-Fahrweges.

Aufstellung 1

Nachfolgend die Koordinaten der Aufgabenstellung im TSPLIB-Format:

Abbildung in dieser Leseprobe nicht enthalten

Aufstellung 2

Im Folgenden der Bericht über die falschen Ankerungen einiger „Orte“:

Hinweis: Die folgenden Berechnungen wurden nicht mittels Streckenberechnung erzeugt, sondern mittels Aufwandsberechnung. Diese ist der Streckenberechnung äquivalent und gleichzeitig flexibler. Die Aufwandsberechnung wird in Kapitel 2.4 erläutert. Hier ist darüber hinaus von Bedeutung, dass Fehler in der CONCORDE-Lösung vorzufinden sind und deren Anzahl (Aufstellung 2).

Abbildung in dieser Leseprobe nicht enthalten

Die behauptete Reihenfolge ist fehlerhaft.

Sie beinhaltet 15 Fehler- und Folgefehler in den Ankerungen.

Vergl. obige Ankerungen mit den Minimaleinfügungen.

Die Überprüfung der äußeren Orte ist nicht erforderlich, da sie immer

minimal geankert sind.

2. Ergebnisse I Allgemeine Grundlagen

2.1. Die äußere Reihenfolge

Es sei bereits vorweggenommen, dass jedes klassische TSP, das als geometrisch-geographisches System zu minimieren ist, über eine äußere Reihenfolge (konvexe Hülle), die dem Verfahren als Minimalreihenfolge vorgegeben wird, verfügen muß.

Beispiel:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: TSP n = 11 koord.11c

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: TSP n = 11 koord.11c

In geometrisch-geographischen Systemen ist die Geometrie Stellvertreterin der Geographie und umgekehrt. Die äußere Reihenfolge (Drei- bzw. Vieleck) ergibt sich durch Festlegung der sie bildenden äußeren „Orte“. Abb. 3 zeigt ein kleines klassisches TSP mit insgesamt n = 11 „Orten“. Wir können uns vorstellen, dass das Rundreiseproblem - wie in der Tourplanung - auf einer massstäblichen Karte eingetragen ist, indem die „Orte“ mit Nadeln markiert sind (Abb. 4). Nun wird ein z.B. Bindfaden um das System gelegt (Uhrzeiger oder Gegenuhrzeiger). Alle „Orte“, die durch diesen Bindfaden berührt werden, sind die äußeren „Orte“ des Systems.

Die Anzahl der äußeren „Orte“ beträgt somit 5.

Abb. 5 zeigt das fertige Ergebnis:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: TSP n = 11 koord.11c

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: TSP n = 11 koord.11c

Abb. 6 zeigt, warum das Festlegen der äußeren Reihenfolge notwendig ist. Wir legen den geometrisch-geographischen Mittelpunkt der Rundreise fest und legen auf diesen ein Fadenkreuz. Da jeder „Ort“ besucht werden muß, müssen bei einem klassischen TSP zwangsläufig alle geografischen Richtungen „befahren“ werden. Die Konsequenz aus dem Vorhandensein der äußeren Reihenfolge ist damit, dass diese als Minimalreihenfolge und Grobrichtung bereits Teil der späteren Lösung ist, was die Reihenfolge - nicht zwangsläufig die Stellung - der äußeren „Orte“ anbetrifft. Diese Reihenfolge der äußeren „Orte“ verändert sich nicht mehr.

Damit ergeben sich die äußeren Reihenfolgen 0-1-2-3-4-0 oder 1-2-3-4-0-1 oder 2-3-4-0-1-2 oder 3-4-0-1-2-3 oder 4-0-1-2-3-4 und jeweils umgekehrt als geschlossene Streckenzüge. Ein geschlossener Streckenzug entsteht, sobald Ausgangs- und Endeort identisch sind. Die Gesamtsumme dieser Streckenzüge ist dann immer identisch. Bei unsymmetrischen Entfernungstabellen erfolgt dann die entgegengesetzte Bewertung dieser Streckenzüge. Optimale und nichtoptimale Lösungen eines klassischen TSP besitzen dieselbe Eigenschaft, da sie ebenfalls geschlossene Streckenzüge bilden.

Die „Orte“ 5,6,7,8,9,10 sind die inneren „Orte“.

Abb. 7 zeigt die Lösung des obigen (klassischen) Rundreiseproblems. Wählt man nun den „Ort“ 0 als Ausgangsort und den Uhrzeigersinn, so „fährt“ man zunächst von West in Richtung Nord, dann von Nord nach Ost. Weiterhin von Ost nach Süd und von Süd zurück nach West. In den vom Autor produzierten Beispielen beginnt und endet die Rundreise stets am „Ort“ 0 (Numerierung der „Orte“ von 0 bis (n - 1)). Die TSPLIB-Instanzen sind jeweils von 1 bis n numeriert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: TSP n = 11 koord.11c

Benennt man die Anzahl aller „Orte“ als n = 11 und die Anzahl der äußeren „Orte“ als k = 5, dann sind die (n – k) = 6 inneren „Orte“ (5,6,7,8,9,10) berechnungsrelevant. Der Wert für k liegt mindestens bei 3, wenn die äußere Reihenfolge einem Dreieck entspricht. Ansonsten erhöht sich der Wert für k entsprechend der Anzahl äußerer „Orte“ im Rahmen eines Vielecks. Erfahrungsgemäß liegt der maximale Wert für k bei etwa 11 - 12.

2.2. Klassische und nichtklassische Traveling Salesman Probleme (TSP´s) , Kosten und Kausalität

Greifen wir nochmals auf das Ausgangsbeispiel aus Kapitel 2.1 zurück:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: TSP n = 11 koord.11c

[...]