Jahr der Mathematik/Graph
Der Graph für das TSP
Der Graph wird über die Entfernungen der einzelnen Städte bei Verwendung des Bahnstreckennetzes errechnet. Dieses bewirkt eine erheblich einfachere Struktur des Graphen. Da das TSP jedoch nur auf vollständigen Graphen definiert ist, muss aus einem Graphen des Streckennetzes ein vollständiger Graph berechnet werden auf dem TSP gelöst werden kann.
Lösungsvorgehen
Der Graph wird als eine Entfernungmatrix erstellt. Dabei sind stehts die minimalen Entfernungen von zwei unmittelbar verbundenen Städten die Kanten und die Kantengewichte die Entfernungen.
Durch Anwendung des APSP (All Pairs Shortest Path) kann daraus ein vollständiger Graph erstellt werden (z.B. Lösung durch Floyd-Warshall oder Johnson).
Auf dem so entstandenen Graph kann dann das TSP gelöst werden. Zur Lösung verwenden wir das Programm Concorde von William Cook ([1]).
Lösungen für einfaches Modell mit euklidischen Entfernungen
Der Graph ist sehr einfach zu erstellen, wenn nur euklidische Entfernungen betrachtet werden. Natürlich kann und wird sich vermutlich auch noch diese Lösung verändern, wenn die Bahnentfernungen als Entfernungskriterien verwendet werden. Als Lösung ergibt sich hierbei:
- Chemnitz
- Jena
- Halle
- Leipzig
- Magdeburg
- Braunschweig
- Hannover
- Hildesheim
- Kassel
- Göttingen
- Clausthal
- Ilmenau
- Bayreuth
- Passau
- Regensburg
- Eichstädt-Ingolstadt
- München
- Augsburg
- Erlangen
- Würzburg
- Ulm
- Konstanz
- Stuttgart
- Tübingen
- Karlsruhe
- Mannheim
- Heidelberg
- Darmstadt
- Mainz
- Frankfurt/Main
- Gießen
- Marburg
- Siegen
- Koblenz
- Saarbrücken
- Freiburg
- Kaiserslautern
- Trier
- Aachen
- Bonn
- Köln
- Wuppertal
- Düsseldorf
- Duisburg
- Bochum
- Dortmund
- Münster
- Osnabrück
- Paderborn
- Bielefeld
- Oldenburg
- Bremen
- Hamburg
- Flensburg
- Kiel
- Rostock
- Greifwald
- Berlin
- Potsdam
- Cottbus
- Zittau/Goerlitz
- Dresden
- Freiberg
- Mittweida
