Video

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 i_{t1}. 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.

Cluster first, route second   Travelling-Salesman-Problem  Sweep-Verfahren
direkt ins Video springen
Cluster first, route second

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 \ D_j. 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.

Distanzmatrix  Sweep-Verfahren
direkt ins Video springen
Distanzmatrix

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.

Sweepline
direkt ins Video springen
Anlegen der Sweepline

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:

E(T1)= d_{01} +d_{12} + d_{20}

Wegstrecke berechnen  Sweep-Verfahren
direkt ins Video springen
Berechnung der Wegstrecke

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“.

Wiederbeladung  Formel  Sweep-Verfahren
direkt ins Video springen
Wiederbeladung nach Kunde 1 und Kunde 2

Somit bleibt noch die Tour Lager Kunde 7 Lager mit der Länge 65 + 65 gleich 130 LE übrig:

E(T3)= d_{07} +d_{70}

Jetzt addieren wir die Länge der drei Touren und erhalten eine Gesamtlänge von 545 LE.

Gesamtlänge Berechnung  Sweep-Verfahren
direkt ins Video springen
Berechnung der Gesamtlänge

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.

Tourenplan  Sweep-Verfahren
direkt ins Video springen
Auswahl des Tourenplans

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?

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .