Tourenplanung Schritt für Schritt
Über diese App
Ein Lager, 16 Kunden, vier Lieferwagen mit je 40 Kisten: Aus Pendelfahrten werden mit dem Savings-Verfahren von Clarke und Wright vier Touren, abgelehnte Paare leuchten mit Grund auf, danach verkürzt 2-opt jede Tour. Ladebalken je Wagen, fallende Gesamtstrecke und das Sweep-Verfahren zum Vergleich.
Worum es geht
Beim Tourenplanungsproblem (Vehicle Routing Problem, VRP) beliefern Fahrzeuge mit begrenzter Kapazität Q mehrere Kunden von einem Lager aus, und die Gesamtstrecke soll möglichst kurz sein. Das Savings-Verfahren von Clarke und Wright startet mit Pendelfahrten Lager → Kunde → Lager. Für jedes Kundenpaar berechnet es die Ersparnis s_ij = d_0i + d_0j − d_ij, also die Strecke, die ein Wagen spart, wenn er i und j nacheinander anfährt. Die Paare werden absteigend abgearbeitet: Zwei Touren werden verbunden, wenn i und j jeweils am Tourende liegen und die Summe der Ladungen Q nicht überschreitet. Das Ergebnis ist eine Heuristik, keine garantiert optimale Lösung.
Was die App zeigt
Ein Lager, 16 Kunden mit ihren Liefermengen und vier Wagen mit je 40 Kisten. Die App geht in Phasen vor: Pendeltouren, Ersparnisse für alle 120 Kundenpaare, Zusammenlegen nach Clarke-Wright, danach 2-opt je Tour. Jede abgelehnte Zusammenlegung leuchtet rot und nennt ihren Grund, etwa „Kapazität“ oder „nicht am Tourende“. Ladebalken zeigen die Füllung jedes Wagens, eine Kurve die fallende Gesamtstrecke. Als Vergleich lässt sich das Sweep-Verfahren wählen, bei dem ein Strahl um das Lager kreist und die Kunden nach Winkel auf die Wagen verteilt.
Selbst ausprobieren
Geh mit „Weiter“ Schritt für Schritt durch die Savings-Liste oder lass sie abspielen; mit den Pfeiltasten springst du vor und zurück. Zeig mit der Maus auf eine Zeile der Liste, dann erscheint auf der Karte das Dreieck Lager–i–j, an dem sich die Ersparnis ablesen lässt. Achte darauf, dass nicht jede große Ersparnis genommen wird. Vergleiche am Ende beide Verfahren: In diesem Beispiel kommt Sweep mit 2-opt auf 97,53 km, Savings mit 2-opt auf 91,21 km. Koordinaten und Mengen sind ein festes, erfundenes Beispiel.
Häufige Fragen
- Wie funktioniert das Savings-Verfahren von Clarke und Wright?
- Zuerst bekommt jeder Kunde eine eigene Pendeltour vom Lager aus. Dann wird für jedes Kundenpaar die Ersparnis s_ij = d_0i + d_0j − d_ij berechnet und die Liste absteigend sortiert. Der Reihe nach werden zwei Touren über die Kante i–j verbunden, sofern beide Kunden am Ende ihrer Tour liegen und die Kapazität des Fahrzeugs reicht.
- Was ist der Unterschied zwischen Savings- und Sweep-Verfahren?
- Das Savings-Verfahren legt Touren nach der größten Streckenersparnis zusammen. Das Sweep-Verfahren dreht einen Strahl um das Lager, ordnet die Kunden nach ihrem Winkel und füllt die Fahrzeuge der Reihe nach, bis die Kapazität erreicht ist. Sweep teilt das Gebiet damit in Sektoren auf; welches Verfahren kürzere Touren liefert, hängt von der Lage der Kunden ab.
- Was macht 2-opt bei der Tourenplanung?
- 2-opt ist ein Verbesserungsverfahren für eine einzelne Tour. Es entfernt zwei Kanten, kehrt das Teilstück dazwischen um und fügt zwei neue Kanten ein, wenn die Tour dadurch kürzer wird. Das wird wiederholt, bis keine solche Umkehr mehr eine Verbesserung bringt. Kreuzungen in einer Tour verschwinden dabei.
- Kann ich in der App eigene Kunden oder Mengen eingeben?
- Nein, die App arbeitet mit einem festen Beispiel aus 16 Kunden, vier Wagen und einer Kapazität von 40 Kisten. Die Koordinaten und Mengen kannst du im Datenpanel nachlesen. So lassen sich alle Schritte und Zwischenergebnisse genau nachvollziehen.
Fach: Operations Research
Mehr aus Operations Research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra-Algorithmus
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Lineare Probleme anschaulich
- Nebenbedingungen verschärfen (Tightening)
- Simplex im Raum
- Simplex-Algorithmus
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps