Sweep-Algorithmus

Der Sweep-Algorithmus wird zur Lösung von Tourenplanungsproblemen (z. B. beim Lieferverkehr) eingesetzt, insbesondere bei Varianten des Traveling Salesman Problems (TSP) mit Kapazitätsgrenzen (sog. CVRP – Capacitated Vehicle Routing Problem)

Ziel:

Ein Transportfahrzeug soll mehrere Kunden beliefern, ohne dass die maximale Kapazität überschritten wird. Dabei soll die Strecke möglichst kurz sein.

1. Kunden in Gruppen (Touren) einteilen: Stell dir vor, der zentrale Startpunkt (z. B. ein Lager) liegt in der Mitte eines Kreisdiagramms. Eine gedachte Linie (Sweep Line) dreht sich im Kreis – gegen den Uhrzeigersinn – und „wischt“ dabei über alle Kunden hinweg.

2. Sobald ein Kunde „berührt“ wird, wird geprüft, ob der LKW dessen Bestellung noch aufnehmen kann, ohne überladen zu werden:

   • ✅ Wenn ja: Der Kunde wird zur aktuellen Tour hinzugefügt.

   • ❌ Wenn nein: Die Tour ist voll. Es wird eine neue Tour begonnen.

3. Wenn eine Tour voll ist, wird die Distanz der Tour mit Hilfe der Distanzmatrix berechnet.

4. Wenn alle Kunden zu Touren zugeordnet sind, wird die Summe der Distanzen berechnet.

5. Die Ausgangslinie wird einen “Kunden” weiter vor gelegt

   • Prozess beginnt von vorne

   • Die Ausgangslinie wird nach einem Durchlauf immer einen Kunden weiter gelegt, bis alle Möglichkeiten einmal durchlaufen wurden

   • Die Gesamttour mit der niedrigsten Distanz wird als finale Tour gewählt

6. Wenn eine finale Tour zugeordnet ist, wird berechnet, in welcher Reihenfolge die Kunden am besten angefahren werden, damit die Strecke möglichst kurz ist.

Das gleiche Verfahren für die weiteren Kunden wiederholen…

Verfahren wiederholen…