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:
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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?
Tourenplanung – Sweep-Verfahren — häufigste Fragen
(ausklappen)
Tourenplanung – Sweep-Verfahren — häufigste Fragen
(ausklappen)-
Was ist Tourenplanung in der Logistik?Tourenplanung in der Logistik bedeutet, Liefer- oder Abholfahrten so zu planen, dass alle Kunden bedient werden und die Fahrten als Touren (Rundfahrten ab Lager und zurück) festgelegt sind. Dabei werden typischerweise Kunden zu Touren zusammengefasst und die Reihenfolge der Stopps sowie die Gesamtlängen der Touren bestimmt.
-
Was ist der Unterschied zwischen Routenplanung und Tourenplanung?Tourenplanung entscheidet, welche Kunden zu welcher Tour bzw. zu welchem Fahrzeug gehören und wie viele Touren gefahren werden. Routenplanung beschreibt dagegen die konkrete Reihenfolge der „Stopps“ innerhalb einer bereits festgelegten Tour, also den Weg „Stopp für Stopp“ (zum Beispiel als Rundfahrt vom Lager zu den Kunden und zurück).
-
Wie bestimmt man beim Sweep-Verfahren die Reihenfolge der Kunden?Beim Sweep-Verfahren bestimmt man die Reihenfolge, indem man die Kunden nach ihrer Lage „im Kreis“ um das Lager ordnet und eine Sweepline um das Lager dreht. Man startet bei einem gewählten Startkunden (oft „auf 3 Uhr“) und nimmt die Kunden dann der Reihe nach entlang der Drehung in die Tour auf.
-
Wie liest man eine Distanzmatrix ab, um die Länge einer Tour zu berechnen?Eine Tourlänge berechnet man, indem man in der Distanzmatrix für jede aufeinanderfolgende Kante der Tour den passenden Eintrag
abliest und alle Teilstrecken addiert. Bei der Tour „Lager (0) → Kunde 1 → Kunde 2 → Lager (0)“ ist das zum Beispiel 
.
Nach Beantwortung speichern wir deine Antwort, um Studyflix zu verbessern. Mehr dazu erfährst du in unserer Datenschutzerklärung.
Tourenplanung verstehen
Das Sweep-Verfahren ist eine bekannte Heuristik in der Tourenplanung und gehört damit zur Logistik. Wer sich mit Tourenplanung beschäftigt, plant Lieferwege so, dass Zeiten, Kosten und Kapazitäten im Ablauf passen. So erkennst du, warum eine Reihenfolge im Netz aus Lager und Kunden die Strecke stark verändern kann. Weitere Videos dazu findest du in unserem Wirtschaftsbereich.