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
- Vorwort
- Inhaltsverzeichnis
- 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. Aufwandberechnung 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.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
Zielsetzung und Themenschwerpunkte
Dieses Buch befasst sich mit dem Traveling Salesman Problem (TSP) und präsentiert ein neuartiges Lösungsverfahren, das die zeitnahe Berechnung der konkreten und beweisbaren Minimalstreihenfolge ermöglicht. Das Buch beleuchtet die Komplexität des TSP und analysiert dessen Anwendung in verschiedenen Bereichen, von euklidischen TSP-Instanzen bis hin zu allgemeinen TSP's in der Tourplanung.
- Komplexitätstheorie des TSP
- Entwicklung eines neuartigen Lösungsverfahren
- Untersuchung euklidischer und allgemeiner TSP-Instanzen
- Analyse von TSP-Anwendungen in der Praxis
- Bedeutung der Verfahrensgrundlagen und algorithmischen Eigenarten
Zusammenfassung der Kapitel
- Kapitel 1: Dieses Kapitel behandelt den bisherigen Forschungsstand zum TSP. Es beleuchtet die Komplexitätstheorie und die wichtigsten Meilensteine in der Forschung sowie das Näherungsverfahren CONCORDE.
- Kapitel 2: Dieses Kapitel fokussiert auf allgemeine Grundlagen des TSP. Es erläutert die äußere Reihenfolge, die Unterschiede zwischen klassischen und nichtklassischen TSP's, die Bedeutung von Kosten und Kausalität sowie die Herausforderungen der Enumeration und Aufwandberechnung.
- Kapitel 3: Dieses Kapitel beschäftigt sich mit geometrisch-geographischen Systemen und deren Anwendung auf das TSP. Es analysiert die Lösung euklidischer TSP's, darunter die Berücksichtigung von Naturgesetzen und die Auswirkungen von Datenveränderungen. Es untersucht auch die Anwendung des Verfahrens auf allgemeine TSP's mit realen Entfernungstabellen und vergleicht die Lösungen euklidischer und realer TSP's.
Schlüsselwörter
Traveling Salesman Problem (TSP), Rundreiseproblem, Lösungsverfahren, Minimalstreihenfolge, Komplexitätstheorie, Näherungsverfahren, CONCORDE, euklidische TSP-Instanzen, allgemeine TSP's, Tourplanung, Verfahrensgrundlagen, algorithmische Eigenarten.
- Citar trabajo
- Dipl. Inform. Wolfgang Oberstenfeld (Autor), 2007, T S P - Traveling Salesman Problem, Múnich, GRIN Verlag, https://www.grin.com/document/79575
