Tourenplanung – Sweep-Verfahren
Du hast noch Schwierigkeiten mit dem Sweep-Verfahren ? Dann ist dieser Beitrag genau das Richtige für dich!
Inhaltsübersicht
Anwendung des Sweep-Algorithmus
Im letzten Video haben wir uns das einstufige Savings-Verfahren angeschaut. In diesem Video befassen wir uns mit dem zweistufigen Sweep-Verfahren. Das Sweep-Verfahren verfährt nach dem Schema „Cluster first, route second“. Cluster first ist die Stufe 1. Hier erfolgt die Gruppierung der Kunden zu Touren. Das bedeutet, dass jedem Kunden eine Tour zugeordnet wird. Die Tour 1 enthält zum Beispiel die Kunden 1 bis 
. Route second ist die Stufe 2, hier wird das Travelling Salesmann Problem für jede Tour gelöst. Es werden also Knotenpunkte zusammengefasst bis die vorgegebenen Grenzen erreicht sind. In unserem Fall entsprechen die Kunden den Knotenpunkten.
Erklärung anhand eines Beispiels
Allerdings müssen hierbei Restriktionen beachtet werden. Diese können zum Beispiel Kapazitätsgrenzen des LKWs, Fahrtzeiten oder ähnliches sein. Wie die Kunden zusammengefasst werden hängt davon ab, wer als Kunde 1 definiert wurde. Je nachdem mit welchem Kunden wir beginnen, ergeben sich n Varianten für Tourenpläne. Aus diesen wird dann die beste Variante ausgesucht. Schauen wir uns das an einem Beispiel an:
Gegeben ist ein Lager und 7 Kunden mit einem jeweiligen Bedarf 
. Die Kapazität deines LKWs ist Q=100 ME. Außerdem ist die zugehörige Distanzmatrix bekannt. In der Distanzmatrix werden die Entfernungen zwischen den einzelnen Kunden und dem Lager sowie die Entfernungen der Kunden untereinander angegeben.
Um das Sweep-Verfahren zu starten, legen wir eine Sweepline an. Für gewöhnlich fängt man „auf 3 Uhr damit an“. In unserem Fall also mit Kunde Nummer 1.
Ausgehend vom Lager fahren wir Kunde 1 an und prüfen dann, wie viel Kunden wir abfahren können, ohne dass unsere Kapazitätsbeschränkung von Q = 100 Mengeneinheiten überschritten wird. In unserem Fall können wir die Kunden 1 und 2 zusammen anfahren. Die Wegstrecke, die wir fahren, berechnen wir mit Hilfe der Distanzmatrix. Wir addieren hierfür die Fahrtstrecken „Lager bis Kunde 1“, „Kunde 1 bis Kunde 2“ und von „Kunde 2 zum Lager“ zurück:
Berechnung der zweiten Tour
Als nächstes überprüfen wir, wie viele Kunden wir anfahren können, wenn wir nach der Tour „Lager Kunde 1 Kunde 2 Lager“ wieder aufladen. Die Bedarfe der Kunden 3 bis 6 sind 30 ME, 20 ME, 30 ME und 20 ME. Also gleich 100 Mengeneinheiten. Wir können sie also alle in einer Tour anfahren. Somit ergibt sich die Strecke der zweiten Tour aus der Distanz „Lager Kunde 3“ plus Distanz „Kunde 3 Kunde 4“ plus Distanz „Kunde 4 Kunde 5“ plus Distanz „Kunde 5 und 6“ plus Distanz „Kunde 6 Lager“.
Somit bleibt noch die Tour Lager Kunde 7 Lager mit der Länge 65 + 65 gleich 130 LE übrig:
Jetzt addieren wir die Länge der drei Touren und erhalten eine Gesamtlänge von 545 LE.
Festlegung des Tourenplans
Das ist also unsere Lösung für den Tourenplan, der bei Kunde 1 startet. Im nächsten Schritt verschieben wir die Sweepline gegen den Uhrzeigersinn um einen Kunden weiter. Nun erstellen wir wieder einen Tourenplan, der dieses Mal bei Kunde 2 startet. Wir überprüfen zunächst wieder anhand der Bedarfe, wie viele Kunden wir hintereinander anfahren können. Es ergeben sich die Tour 1 „Kunde 2 Kunde 3 Kunde 4“, Tour 2 „Kunde 5 Kunde 6“ und die Tour 3 „Kunde 7 Kunde 1“.
Die entsprechenden Längen der Touren bestimmen wir wieder anhand der Distanzmatrix. Tour 1 hat eine Länge von 210 LE, Tour 2 eine Länge von 176 LE und Tour 3 eine Länge von 182 LE.
Wie du vielleicht schon erkannt hast, ist die Gesamtlänge der Variante „Start bei Kunde 2 mit einer Gesamtstrecke von 568 LE“ deutlich länger als die Variante „Start bei Kunde 1“.
Das Verfahren hast du jetzt vermutlich verstanden. Um zu bestimmen welcher Tourenplan optimal ist, müssen wir n Tourenpläne, also so viele Tourenpläne wie es verschiedene Lager gibt – überprüfen. Das sparen wir uns an dieser Stelle, in einer Klausur wirst du aus Zeitgründen auch nie alle Touren ausrechnen müssen. Am Ende wählst du dann natürlich den Tourenplan aus, der die kürzeste Gesamtstrecke hat. Eigentlich ganz einfach oder?