In 2 Bänden präsentiert der Autor erstmalig sein Wissen für die konkrete, beweisbare und zeitnahe Lösung eines Optimierungsklassikers: das Traveling Salesman Problem (TSP), Rundreiseproblem, Problem des Handlungsreisenden).
Bis heute existiert für die Lösung dieses Problems kein konkretes, zeitnah arbeitendes und beweisbares Lösungsverfahren; trotz jahrzehntelanger Forschung zahlreicher Fachleute von Universitäten, Instituten und Unternehmen. In den letzten 15 Jahren ist der Autor intensivst in die Problematik des TSP „eingetaucht“: mit vollem Erfolg. Gleichzeitig präsentiert er auch die Herangehensweise nichtklassischer Varianten des Traveling Salesman Problems, was bis heute innerhalb der Graphentheorie immense Schwierigkeiten bereitet.
Im Bereich der kombinatorischen Optimierung ist das neue Lösungsverfahren für die Lösung von TSP`s das erste seiner Art: die Beweisbarkeit der ermittelten Lösung, dass es keine bessere geben kann. Innerhalb der kombinatorischen Optimierung eine Einzigartigkeit. Weiterhin ist das Lösungsverfahren ein konkretes Verfahren, welches mit seinen Qualitäten jedes Näherungsverfahren (Heuristik) in den Schatten stellt.
Die Früchte seiner Arbeit erscheinen in 2 Bänden: Band 1 enthält die wesentlichen Forschungsergebnisse in kompakter Form zuzüglich wichtiger Verfahrensgrundlagen (Herbst 2007). Der 2. Band enthält das Lösungsverfahren in detaillierter Beschreibung.
Der Bedarf an diesem Lösungsverfahren ist in Wissenschaft und Wirtschaft enorm, so dass der Autor das kompakte Wissen beider Bände für relativ wenig Geld einem breiten Publikum präsentieren kann.
Das TSP findet sich in zahlreichen Varianten innerhalb der Tourplanung, der Lagerhaltung, der Produktion, der Biologie, der Astronomie etc.
Beide Bände enthalten zahlreiche Beispiele, deren Daten im Netz heruntergeladen werden können.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Das Ziel der Arbeit ist die kritische Auseinandersetzung mit der gängigen Forschung zum Traveling Salesman Problem (TSP), um aufzuzeigen, dass bisherige Näherungsverfahren oft keine beweisbaren Optima liefern. Der Autor leitet ein eigenes, algorithmisch exaktes Lösungsverfahren her, das geometrisch-geografische Kausalitäten nutzt, um das Problem effizienter und nachvollziehbarer zu lösen als bestehende Ansätze.
- Kritische Analyse der Komplexitätstheorie und etablierter Näherungsverfahren
- Unterscheidung zwischen euklidischen (kausalen) und chaotischen Systemen
- Einführung einer Aufwandsberechnung zur Ankerung von „Orten“
- Methodische Einordnung von Symmetrie und Parallelität bei der Lösungsfindung
- Mathematischer Nachweis der Ineffizienz bisheriger "Meilensteine"
Auszug aus dem Buch
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.
Zusammenfassung der Kapitel
1. Der bisherige Forschungsstand: Diskutiert die Grenzen der klassischen Komplexitätstheorie und die methodischen Schwächen bekannter Näherungsverfahren wie CONCORDE.
2. Ergebnisse I Allgemeine Grundlagen: Führt die methodischen Grundlagen ein, insbesondere die Bedeutung der äußeren Reihenfolge und die neue Aufwandsberechnung.
3. Ergebnisse II Geometrisch-geographische Systeme und das Gegenteil: Analysiert den Unterschied zwischen euklidisch-kausalen Systemen und realen, oft unsymmetrischen Entfernungstabellen.
4. Ergebnisse III Verfahrensgrundlagen: Erläutert die mathematischen Anforderungen an das Lösungsverfahren, wie Richtungsabhängigkeiten, Kommutativität und Parallelität.
Schlüsselwörter
Traveling Salesman Problem, TSP, Kombinatorische Optimierung, Minimalstreihenfolge, Aufwandsberechnung, Euklidische Metrik, CONCORDE, TSPLIB, Geometrische Systeme, Rundreiseproblem, Enumeration, Algorithmen, Praxisrelevanz, Kausalität, Komplexitätstheorie
Häufig gestellte Fragen
Was ist das zentrale Anliegen dieser Arbeit?
Die Arbeit hinterfragt die Unlösbarkeits-Dogmen der modernen Informatik zum TSP und präsentiert ein eigenes Verfahren zur exakten und beweisbaren Lösung des Problems.
Welche Themenfelder stehen im Mittelpunkt?
Die Arbeit behandelt die mathematische Optimierung von Routen unter Berücksichtigung von euklidischen Distanzen sowie realen, oft komplexeren infrastrukturellen Anforderungen.
Was ist die primäre Forschungsfrage?
Die Arbeit fragt, ob das TSP trotz der geltenden Komplexitätstheorie mit einem beweisbaren Verfahren effizient gelöst werden kann, sofern man die geometrisch-geografischen Strukturen korrekt analysiert.
Welche wissenschaftliche Methode wird primär eingesetzt?
Der Autor verwendet eine deduktive Herleitung mittels "Aufwandsberechnung" und "Minimal-Ankerung" von Orten, anstatt sich auf rein heuristische Schätzverfahren zu verlassen.
Welche Inhalte werden im Hauptteil vertieft?
Der Hauptteil unterscheidet detailliert zwischen euklidischen "Naturgesetzen" in der Geometrie und chaotischen Systemen, die in praxisfernen akademischen Modellen entstehen.
Welche Schlagworte charakterisieren die Arbeit am besten?
Praxisrelevanz, Beweisbarkeit des Minimums, euklidische Kausalität und die Kritik an einer "chaotischen Informationsvielfalt" der Forschung.
Was ist das Problem mit dem "Weihnachtsrätsel"?
Das Problem über 26 europäische Städte konnte bisher mathematisch nicht exakt bewiesen werden; der Autor kritisiert die existierenden Lösungsversuche als geographisch inkonsistent.
Warum hält der Autor die CONCORDE-Lösungen oft für fehlerhaft?
Laut Autor liefern diese Programme oft "Ankerfehler" und Wegekreuzungen, die in einer euklidisch-geometrischen, minimalen Lösung nicht existieren dürften.
- Quote paper
- Dipl. Inform. Wolfgang Oberstenfeld (Author), 2007, T S P - Traveling Salesman Problem, Munich, GRIN Verlag, https://www.grin.com/document/79575
