Das „Travelling Salesman-Problem“, in Deutsch kurz das Rundreiseproblem genannt, war bereits vor Kurzem Gegenstand eines Blogbeitrages.
Die Lösung wurde nach der Trial-Error-Methode ohne Nutzung des Excel-Solvers gesucht.
Dieser Beitrag dagegen zeigt einen möglichen Weg zur Lösung des Problems mit dem Excel-Solver.
Grundlage dafür war das Beispiel aus einem Artikel von Rasmus Rasmussen [1], das ich versucht habe, nachzugestalten.
1. Modellierung der Aufgabenstellung
1.1 Der tabellarische Aufbau
Die Umgebung soll eine Fläche von ca. 30 x 31 km sein, in der zehn Orte zu befahren sind.
Auch hier wird mittels x- / y-Koordinaten wird die Lage der Orte in einem Punkt (XY)-Diagramm dargestellt. Das Bild zeigt die Koordinaten. Ausgangs- und Endpunkt ist der Punkt 0/0.
In einer Hilfstabelle werden nun alle Entfernungen von jedem Ort zu jedem Ort berechnet.
Gib dazu in G3 die Formel
=WURZEL((INDEX($C$3:$D$13;$F3+1;1)-INDEX($C$3:$D$13;G$2+1;1))^2+(INDEX($C$3:$D$13;$F3+1;2)-INDEX($C$3:$D$13;G$2+1;2))^2)
ein und kopiere sie bis Q13. Die Entfernungen zwischen den Orten werden mittels des Satzes des Pythagoras errechnet.
In einer weiteren Hilfstabelle hältst Du die geplante Fahrstrecke fest.
Ausgangspunkt soll dabei die Reihenfolge 0-1-2 …. -9-10-0 sein.
Die Entfernungswerte werden mit der Formel
=INDEX($G$3:$Q$13;$C16+1;$C17+1)
aus der Entfernungstabelle übernommen. Der Wert 27,17 ist z.B. die Entfernung von Ort 0 zu Ort 1 aus der Entfernungstabelle Zeile 0 / Spalte 1.
In D28 ergibt sich die bei dieser gewählten Route gesamt zu fahrende Strecke, Formel
=SUMME(D17:D27)
Diesen Wert willst Du optimieren, d.h. auf ein Minimum bringen.
Eine letzte Hilfstabelle musst Du noch erstellen.
Trage in G16 diese Formel ein:
=INDEX($B$3:$D$13;$C16+1;2)
Kopiere sie bis G27
Trage in H16 dann noch diese Formel ein:
=INDEX($B$3:$D$13;$C16+1;3)
Kopiere sie bis H27.
1.2 Erstellung des Punktdiagramms
Nun ist noch das Punktdiagramm zu erstellen. Dazu markierst Du der Bereich G16:H27, Deine letzte Hilfstabelle, und wählst über Einfügen / Diagramme ein „Punktdiagramm mit geraden Linien und Datendarstellungen“. Kennzeichne die einzelnen Orte im Diagramm z.B. mit einer in ein Textfeld eingetragenen Ziffer.
Die anfängliche Strecke über 205,67 km stellt sich so dar:
2. Die Optimierung der Fahrstrecke
Die Optimierung soll mit dem Solver erfolgen. Klicke dazu auf die Summenzelle D28.
Rufe nun im Menü Daten / Analyse den Solver auf.
Lege als Zielzelle die Zelle D28 fest und bestimme, dass der Wert ein Minimum werden soll.
Dazu sollen sich die Zellen C17:C26 ändern können.
Als Nebenbedingungen legst due fest, dass die Werte in C17:C26 unterschiedlich und ganzzahlig sein sollen.
Wähle als Lösungsmethode zunächst „GRG-Nichtlinear“.
Gehe schließlich noch auf „Optionen“ und lege als Anzahl der Iterationen „1“ fest.
Setze den Prozess durch Klick auf „Lösen“ in Gang.
Der Solver wirft ein Ergebnis aus, dass Du akzeptieren kannst.
Mit 159,48 km ist der Weg schon um einiges kürzer, aber das reicht Dir noch nicht.
Du veränderst die Anzahl der Iterationen in den Optionen auf „10“ und startest erneut „Lösen“.
Das Ergebnis ist wieder etwas besser, 146,18 km.
Du unternimmst noch einen weiteren Versuch und wählst dazu die Methode „EA (Evolutionärer Algorithmus)“. Bleibst bei 10 Iterationen und übernimmst die Optionen für die Methode EA.
Klicke wieder auf „Lösen“.
Mit 122,77 km erhältst Du nun ein akzeptables Ergebnis.
Weitere Versuche haben mit den gegebenen Einstellungen zu keinem besseren Ergebnis geführt.
Quellen:
[1]
Rasmussen, Rasmus: TSP in Spreadsheets – a Guided Tour,
veröffentlicht:
Travelling Salesman Problem in Spreadsheets – a Guided Tour (economicsnetwork.ac.uk)
Entdecke mehr von Clevercalcul
Subscribe to get the latest posts sent to your email.