Das Rundreiseproblem mit Excel lösen, ohne Solver

Das „Travelling Salesman-Problem“, in deutsch kurz das Rundreiseproblem genannt, ist für Händler oder Spediteure ein altes Problem.

Worum geht es?

Es geht darum, ausgehend von einem Ausgangsort bestimmte Orte zu beliefern und danach wieder zuhause zu landen. Es wird also eine Rundreise durch die festgelegten Orte vorgenommen.

Ziel ist es, dabei so wenig Kilometer wie möglich zurückzulegen.

Die Orte können dazu in unterschiedlichen Reihenfolgen befahren werden.

Hierzu gibt es verschiedene Methoden. Eine davon habe ich in „Excel. Das Zauberbuch“ [1] gefunden. Hier gelingt es, ohne VBA und ohne den Excel-Solver einen kurzen Weg zu finden, mit dem der Händler / Spediteur (nachfolgend nur Händler genannt) leben kann. Vom Verlag des Buches und vom Verfasser habe ich freundlicherweise die Erlaubnis erhalten, danke dafür.

1. Modellierung der Aufgabenstellung

1.1 Der tabellarische Aufbau

Die Umgebung soll eine etwa 20 Quadratkilometer große Fläche sein, in der sieben zu besuchende Orte liegen.

Mittels x- / y-Koordinaten wird zunächst die Lage der Orte in einem Punkt (XY)-Diagramm dargestellt. Das Bild zeigt die Koordinaten. Ausgangspunkt ist der Punkt 0/0.

Dem Händler ist die Reihenfolge, in der er die Orte besucht, relativ egal. Er lässt daher den Zufall entscheiden, wie er zu fahren hat.

Im Bereich D5:D11 ermittelt er die Zufallszahlen mit

=ZUFALLSZAHL()

Darauf basierend wird im Bereich E5:E11 mit der Formel

=RANG(D5;$D$5:$D$11)

und Abschluss mit Strg + ENTER die Reihenfolge festgelegt.

Im Bereich F5:G11 lässt Du nun die Koordinaten der Orte entsprechend der in Spalte E berechneten Rangfolge der Zufallszahlen eintragen. Das geschieht mit den Formeln

F5: =INDEX($A$5:$A$11;E5)

G5: =INDEX($B$5:$B$11;E5)

In der Bereichen F4:G4 und F12:G12 bleiben die Koordinaten 0. Der Händler startet immer zuhause und kommt abends wieder dort an.

In Spalte H berechnest Du mit dem Satz des Pythagoras die Strecken zwischen den Orten. Zelle H5 erhält die Formel

=WURZEL((F5-F4)^2+(G5-G4)^2)

Diese wird bis H11 kopiert. In H13 errechnet schließlich die Formel

=SUMME(H5:H12)

die insgesamt zu fahrende Strecke. H14 zeigt das Ergebnis mit zwei Nachkommastellen.

Kopiere den Bereich E3:H14 nach J3:M14. Schreibe in J5 die Formel

=WENN($N$1=1;E6;WENN($H$13<$M$13;E6;J6))

und ziehe sie bis J11 herunter.

Schreibe in K5 die Formel

=INDEX($A$5:$A$11;J5)

und ziehe sie bis K11 herunter.

Schreibe schließlich in L5 die Formel

=INDEX($B$5:$B$11;J5)

und ziehe sie bis L11 herunter.

In M5 rechnest Du wieder die Strecke aus, diesmal mit der Formel

=WURZEL((K5-K4)^2+(L5-L4)^2)

Ziehe sie bis M12 herunter.

1.2 Erstellung des Punktdiagramms

Nun ist noch das Punktdiagramm zu erstellen. Dazu markierst Du der Bereich A4:B12 und wählst über Einfügen / Diagramme ein „Punktdiagramm mit geraden Linien und Datendarstellungen“. Ordne das Diagramm z. B. über B18 beginnend an.

2. Die Optimierung der Fahrstrecke

2.1 Die Optimierung „programmieren“

Die Abbildung zeigt die Ausgangssituation, mit der der Händler nicht zufrieden ist. Über dem Diagramm wird noch die Anzahl der Versuche ausgewiesen, dazu später mehr.

Für die km-Anzeige im Diagrammtitel wird der Diagrammtitel markiert. In die Bearbeitungszeile wird

=$H$14

eingetragen.

Die Zelle N1 erhält den Eintrag 1.

Schreibe in E16 nun die Formel zum Zählen der Versuche:

=WENN(N1=1;0;E16+1)

Füge unterhalb der Spalte K das Formularsteuerelement „Gruppenfeld“ ein und vergrößere es etwas.

Schiebe anschließend zwei Formularsteuerelemente „Optionsfeld“  in das Gruppenfeld ein.

Klicke mit der rechten Maustaste jeweils auf ein Optionsfeld und trage unter „Zellverknüpfung“ N1 ein.

Ist das Optionsfeld „neue Orte“ aktiv, bleibt in N1 der Eintrag 1.

Schaltest Du das Optionsfeld „Strecke optimieren“ aktiv, wird in N1 eine 2 eingetragen.

Der Eintrag in N1 wird im Bereich J5:J11 berücksichtigt, wie oben schon erwähnt.

Wie kannst Du nun die Fahrstrecke in Richtung Minimum optimieren?

Schalte das Optionsfeld „Strecke optimieren“ aktiv, in N1 steht die 2.

Drücke nun die Funktionstaste F9. Es wird neu gerechnet. Das Diagramm verändert sich, die km-Anzeige wird eine andere.

In Zelle E16 wird die Anzahl der bisherigen Optimierungsversuche gezählt.

Schaltest Du das Optionsfeld „neue Orte“ aktiv, steht in E16 wieder die 0 und Du kannst nach Umschalten des Optionsfeldes „Strecke optimieren“ mit dem Optimieren von vorn beginnen.

2.2 Ein Beispiel

Dies war die Ausgangssituation:

Durch Drücken der F9-Taste verändert sich das Bild im ersten Versuch so:

Nach 4 Versuchen ist die Fahrstrecke schon auf 74,08 km reduziert.

Versuch 119 führt schließlich zu nur 62,54 km. Damit kann der Händler sicherlich schon ganz gut leben.

Weitere Versuche bis Nr. 1000 haben keinen kürzeren Weg mehr ergeben. Aber es bleibt Dir überlassen, die Versuche bis ins Unendliche fortzuführen.

Bedenke dabei, dass in Deinem Modell die Ausgangssituation ganz anders aussehen kann. Schuld sind ganz einfach die Zufallszahlen in Spalte D.

3. Fazit

Das vorgestellte Modell macht schon beim Aufbauen Spaß. Interessant ist es, zu sehen, wie sich die möglichen Fahrstrecken bei jedem Versuch verändern.

Genial finde ich die Idee für das Modell.

Eine Sache ist allerdings zu beachten. Die Fahrstrecken zwischen den Orten entsprechen immer nur der Luftlinie. Das aber kann der Nutzer eventuell verkraften.

Quellen:

[1]

Fleckenstein, J./ Fricke, W./ Georgi, B.: Excel. Das Zauberbuch, Markt + Technik Verlag, München 2011, ISBN 978-3-8272-4695-0