Den kürzesten Weg mit dem Excel-Solver finden

Manchmal gibt es mehrere Möglichkeiten, von einem Ort zum anderen zu fahren. Das ist vor allem dann wichtig, wenn man in der Arbeit sehr viel auf den Straßen unterwegs ist, z.B. als Warenlieferant, als Postzusteller oder auch als Taxifahrer.

Längere Strecken bedeuten mehr Fahrzeit, aber auch einen höheren Treibstoffverbrauch und damit höhere Kosten.

Es wird daher immer im Interesse des Fahrers sein, den kürzesten Weg zu finden. Heutzutage wirst du dazu ein Navigationsgerät nutzen. Als Excel-Freund kannst du aber auch so vorgehen, wie der Beitrag es zeigt.

1. Die Ausgangsdaten

Als Erstes brauchst du eine Skizze oder auch richtiges Kartenmaterial, worauf du die infrage kommenden Strecken einschließlich der Orte einzeichnest. Das könnte etwa so aussehen:

Die mit Buchstaben gekennzeichneten Orte werden im Weiteren als Knoten bezeichnet.

Erstelle dir nun daraus eine Tabelle, in der du alle möglichen Teilstrecken inkl. der Entfernungen eingibst.

Erfasse dabei alle Strecken vor und zurück von einem Knoten. Vom Start allerdings geht es nur nach vorn, vom Ziel geht es gar nicht mehr weiter.

Vom Start aus hast du drei Möglichkeiten, nach A, nach B oder nach C.
Vom Knoten C aus kannst du nach A, nach B, nach D oder direkt ins Ziel gehen. Zurück zum Start geht es nicht.

In der Spalte „Route“ trägst du bei den Knoten, die du befahren willst, eine „1“ ein, ansonsten eine „0“.

In der Tabelle steht bei Start, B und E eine „1“, du fährst z.Zt. demnach die Strecke Start-B-E-Ziel.

Vergib für die entsprechenden Bereiche die Namen „Von“, „Nach“, „Entfernung“ und “Route“. Vergib für die Zelle E33 den Namen „Totale_Entfernung“.

2. Erste Berechnungen

Erstelle neben der obigen Tabelle eine zweite:

Vergib auch hier für die zutreffenden Bereiche die Namen „Ist“ und „Soll“.

In der Spalte „Ist“ berechnest du den sogenannten Nettostrom.

Formeln:

H15 =SUMMEWENN(Von;G15;Route)
H16 =SUMMEWENN(Von;G16;Route)-SUMMEWENN(Nach;G16;Route)
H17 =SUMMEWENN(Von;G17;Route)-SUMMEWENN(Nach;G17;Route)
H18 =SUMMEWENN(Von;G18;Route)-SUMMEWENN(Nach;G18;Route)
H19 =SUMMEWENN(Von;G19;Route)-SUMMEWENN(Nach;G19;Route)
H20 =SUMMEWENN(Von;G20;Route)-SUMMEWENN(Nach;G20;Route)
H21 =SUMMEWENN(Von;G21;Route)-SUMMEWENN(Nach;G21;Route)

Was bedeuten die Ergebnisse?

In H15 erhältst du als Ergebnis eine 1. Vom Start aus gibt es nur Ausgänge. Du summierst mit der Formel die Werte in E15:E17.

Von A aus gibt es auch nur Ausgänge, nach C und nach D. Zurück nach Start geht nicht.
Du summierst mit der Formel in H16 alle Werte in Spalte E, wenn in Spalte B ein A steht (Summe = 0) und subtrahierst davon die Summe aller Werte in Spalte E, wenn in Spalte C ein A steht (Summe = 0).

So verfährst du bis H21. Beim Start muss in der Spalte H eine 1 stehen, beim Ziel eine -1. Alle anderen Knoten werden eine 0 erhalten.

In der Modellierung im Solver wirst du eine Nebenbedingung stellen, nämlich die, dass die Werte in Spalte H den Werten in Spalte J entsprechen. Dazu schreibst du in J15:J21 die Werte, wie in obiger Tabelle ersichtlich.

In Zelle E33 schließlich berechnest du mit der Formel

=SUMMENPRODUKT(Entfernung;Route)

Die zu fahrende Gesamtstrecke, im Beispiel zunächst noch 16 km.

3. Das Problem mit dem Solver optimieren

Die Gesamtstrecke, noch 16 km, willst du minimieren. Dazu verwendest du die lineare Optimierung.

„Die lineare Optimierung oder lineare Programmierung ist eines der Hauptverfahren des Operations Research und beschäftigt sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist.“ [1]

In Excel gibt es zu diesem Zweck den Solver, den du über das Menü Daten / Analyse aufrufen kannst.

Lege die Zielzelle fest. Im Beispiel ist es die Zelle E33, benannt mit „Totale_Entfernung“.

Durch die Optimierung soll hier ein minimaler Wert erreicht werden, klicke dazu „Min.“ an.

Bestimme die Nebenbedingungen. Weiter vorher hast du diese schon erfahren. Die berechneten Werte in Spalte H müssen mit den vorgegebenen Werten in Spalte J übereinstimmen.

Setze den Haken bei „Nicht eingeschränkte Variablen als nicht-negativ festlegen“.

Wähle letztlich noch die Lösungsmethode „Simplex-LP“.

Bestätige dann mit OK. Excel schlägt dir nun vor, die Solver-Lösung zu akzeptieren. Gefällt dir das Ergebnis nicht, klicke auf „Ursprüngliche Werte wiederherstellen“. Klicke nach deiner Entscheidung auf „OK“.

Die Tabelle weist nun nach der Akzeptierung diese Werte aus:

Die optimale Fahrstrecke wird danach von Start über A und D zum Ziel führen. In Spalte E steht neben Start-A, A-D und neben D-Ziel jeweils eine 1.

Die Werte in den Spalten H und J sind identisch.

Die Gesamtstrecke beträgt jetzt nur noch 13 km.

Quellen:

[1] https://de.wikipedia.org/wiki/Lineare_Optimierung