- Was Tourenplanung und das Traveling-Salesman-Problem sind
- Visuelle Karte der Tourenplanung
- Beispieldaten: Depot und 5 Kunden
- Nächster Nachbar: die Tour aufbauen
- 2-opt-Verbesserung: zwei Kanten tauschen
- Vom Rundreiseproblem zur Fahrzeugeinsatzplanung
- Wo die Tourenplanung im Betrieb ansetzt
- Häufige Fehler und Grenzen
- Häufige Fragen
Was Tourenplanung und das Traveling-Salesman-Problem sind
Die Tourenplanung legt fest, in welcher Reihenfolge ein Fahrzeug eine Menge von Stopps anfährt, damit Strecke oder Zeit möglichst gering sind. Muss ein einzelnes Fahrzeug alle Punkte besuchen und zum Start zurückkehren, spricht man vom Traveling-Salesman-Problem (TSP, Rundreiseproblem).
Mit mehreren Fahrzeugen, Ladekapazität und Zeitfenstern wird daraus das Vehicle Routing Problem (VRP). Das ist Alltag für alle, die Fertigware ausliefern, Teile bei Lieferanten abholen oder die Linie per Milk Run versorgen.
Das TSP ist schwer, weil die Zahl der Touren explodiert. Bei 5 Kunden gibt es 5! = 120 mögliche Reihenfolgen, bei 10 Kunden 10! = 3.628.800. Deshalb nutzt die Praxis Heuristiken: einfache Regeln, die in Sekunden eine gute Tour liefern, ohne die beste zu garantieren.
Visuelle Karte der Tourenplanung
Die Karte fasst das Beispiel dieses Artikels zusammen: die Tour nach dem Nächster-Nachbar-Verfahren und ihre Verbesserung mit 2-opt.
Beispieldaten: Depot und 5 Kunden
Fiktives Beispiel, nur zur Veranschaulichung der Rechnung. Das Depot D liegt im Ursprung, jede Rastereinheit entspricht 1 km. Koordinaten (x, y): D (0, 0), F (1, 3), A (2, 6), B (5, 1), C (6, 5) und E (9, 2).
d = √[(x₂ − x₁)² + (y₂ − y₁)²]
Beispiel: von D nach F gilt d = √(1² + 3²) = √10 = 3,16 km. Die Tabelle zeigt alle Entfernungen zwischen den Punkten in km.
| D | F | A | B | C | E | |
|---|---|---|---|---|---|---|
| D | – | 3,16 | 6,32 | 5,10 | 7,81 | 9,22 |
| F | 3,16 | – | 3,16 | 4,47 | 5,39 | 8,06 |
| A | 6,32 | 3,16 | – | 5,83 | 4,12 | 8,06 |
| B | 5,10 | 4,47 | 5,83 | – | 4,12 | 4,12 |
| C | 7,81 | 5,39 | 4,12 | 4,12 | – | 4,24 |
| E | 9,22 | 8,06 | 8,06 | 4,12 | 4,24 | – |
Im realen Betrieb ersetzen Sie die Luftlinie durch eine Entfernungs- oder Fahrzeitmatrix des Straßennetzes. Die Heuristiken funktionieren genauso.
Nächster Nachbar: die Tour aufbauen
Das ist die einfachste Heuristik. Starten Sie am Depot und fahren Sie in jedem Schritt zum nächstgelegenen noch nicht besuchten Kunden. Sind alle besucht, geht es zurück zum Depot.
- Von D ist F am nächsten (3,16 km), gegenüber A (6,32), B (5,10), C (7,81) und E (9,22).
- Von F ist A am nächsten (3,16 km).
- Von A ist C am nächsten (4,12 km).
- Von C ist B (4,12 km) kürzer als E (4,24 km), also weiter zu B.
- Von B bleibt nur noch E (4,12 km).
- Von E zurück zu D (9,22 km).
| Schritt | Von | Nach | Entfernung (km) |
|---|---|---|---|
| 1 | D | F | 3,16 |
| 2 | F | A | 3,16 |
| 3 | A | C | 4,12 |
| 4 | C | B | 4,12 |
| 5 | B | E | 4,12 |
| 6 | E | D | 9,22 |
| Summe | 27,91 |
Die Tour D–F–A–C–B–E–D summiert sich auf 27,91 km. Man sieht den typischen Schwachpunkt des Verfahrens: In den letzten Schritten bleiben die entfernten Kunden übrig, und allein die Rückfahrt E–D mit 9,22 km macht ein Drittel der Tour aus.
2-opt-Verbesserung: zwei Kanten tauschen
2-opt geht von einer fertigen Tour aus und prüft, ob sich zwei Kanten durch zwei andere ersetzen lassen, wobei das Stück dazwischen umgekehrt wird. Sinkt die Summe, wird der Tausch übernommen; das wiederholt sich, bis kein Tausch mehr hilft.
Gewinn = (Kante 1 + Kante 2) entfernt − (Kante 3 + Kante 4) neu
In der Tour D–F–A–C–B–E–D entfernen Sie C–B und E–D. Verbinden Sie C mit E und B mit D und kehren Sie das Stück B–E um. Die Reihenfolge lautet nun D–F–A–C–E–B–D.
| Tour | Reihenfolge | Getauschte Kanten | Summe (km) |
|---|---|---|---|
| Vorher (Nächster Nachbar) | D–F–A–C–B–E–D | C–B (4,12) + E–D (9,22) = 13,34 | 27,91 |
| Nachher (2-opt) | D–F–A–C–E–B–D | C–E (4,24) + B–D (5,10) = 9,34 | 23,91 |
Der Gewinn beträgt 13,34 − 9,34 = 4,00 km, also 14,3% weniger (von 27,91 auf 23,91 km). Nach Prüfung aller übrigen Tauschmöglichkeiten bringt keine mehr eine Verbesserung. Das Ergebnis wurde durch Auflisten aller 120 Reihenfolgen kontrolliert: 23,91 km ist tatsächlich die kürzeste Strecke dieses Beispiels. 2-opt erreicht nicht immer das Optimum, kommt ihm aber meist nahe.
Vom Rundreiseproblem zur Fahrzeugeinsatzplanung
Das TSP setzt ein Fahrzeug ohne Ladegrenze voraus. Die Realität in Fertigung und Distribution bringt Nebenbedingungen:
- Kapazität: Das Fahrzeug nimmt nicht alle Aufträge auf einmal mit; die Kunden müssen auf mehrere Touren verteilt werden.
- Zeitfenster: Der Kunde nimmt zum Beispiel nur zwischen 8 und 11 Uhr an.
- Gemischte Flotte: Fahrzeuge unterschiedlicher Größe und Kosten.
- Servicezeit: Entladen, Wareneingangsprüfung und maximale Lenkzeit des Fahrers.
- Abholung und Lieferung: Stopps, die empfangen, und Stopps, die versenden.
Ein klassisches Verfahren zur Aufteilung der Kunden auf Touren ist das Savings-Verfahren von Clarke und Wright (1964), das Touren verbindet, wenn dadurch die Gesamtstrecke sinkt. Größere oder stark eingeschränkte Probleme erfordern ganzzahlige lineare Optimierung oder Tourenplanungssoftware.
Wo die Tourenplanung im Betrieb ansetzt
- Externer Milk Run: Abholung bei mehreren Lieferanten auf einer Fahrt, wie in der Versorgungslogistik.
- Distribution: Auslieferung an Kunden, bei der die Fracht einen relevanten Teil der Herstellkosten ausmacht; siehe auch Cross-Docking.
- Lager: Die Besuchsreihenfolge der Lagerplätze beim Kommissionieren ist ein kleines TSP.
- Instandhaltung und Prüfung: Rundgang von Technikern über mehrere Anlagen.
- Lieferkette: Die Tour ist ein Baustein der Supply Chain, der Lieferzeit und Logistikkosten bestimmt.
Häufige Fehler und Grenzen
- Den nächsten Nachbarn für optimal halten. Er ist nur ein Startpunkt; im Beispiel lag er 17% über dem Besten (27,91 gegenüber 23,91 km).
- Luftlinie statt Straßennetz verwenden. Flüsse, Bahnlinien und Einbahnstraßen ändern die ideale Reihenfolge.
- Die Zeit ignorieren. Die kürzeste Strecke ist nicht immer die kürzeste Zeit; Verkehr und Zeitfenster zählen.
- Nebenbedingungen vergessen. Kapazität, Anlieferzeiten und Lenkzeiten müssen vor dem Vergleich der Touren feststehen.
- Nicht mit dem Fahrer abstimmen. Fahrer kennen Sperrungen, Rampen und Wartezeiten, die die Karte nicht zeigt.
- Nur einmal rechnen. Ändern sich die Aufträge, ändert sich die Tour; planen Sie in jedem Lieferzyklus neu.
Häufige Fragen
Was ist das Traveling-Salesman-Problem?
Es ist die Aufgabe, die kürzeste Tour zu finden, die jeden Punkt einer Liste genau einmal besucht und zum Startpunkt zurückkehrt.
Was ist Tourenplanung?
Sie legt die Touren einer Flotte zur Belieferung von Kunden fest, unter Beachtung von Kapazität und Zeitfenstern bei minimaler Strecke oder Zeit.
Wie funktioniert das Nächster-Nachbar-Verfahren?
Man startet am Depot und fährt in jedem Schritt zum nächsten unbesuchten Kunden, bis alle besucht sind, und kehrt dann zurück.
Was ist 2-opt?
Eine Verbesserung, die zwei Kanten der Tour durch zwei andere ersetzt und das Stück dazwischen umkehrt, wenn die Gesamtstrecke dadurch sinkt.
Liefert der nächste Nachbar die beste Tour?
Nicht garantiert. Im Beispiel ergab er 27,91 km, 2-opt erreichte 23,91 km, das unter den 120 Reihenfolgen geprüfte Minimum.
Wie viele Touren gibt es bei 10 Kunden?
10! = 3.628.800 Reihenfolgen ab einem Depot; deshalb nutzt man Heuristiken, statt alle zu testen.
Quellen
- APPLEGATE, D. L. et al. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
- TOTH, P.; VIGO, D. (Hrsg.). The Vehicle Routing Problem. SIAM, 2002.
- CROES, G. A. A method for solving traveling-salesman problems. Operations Research, Bd. 6, 1958.
- CLARKE, G.; WRIGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, Bd. 12, 1964.
- DOMSCHKE, W.; DREXL, A. Einführung in Operations Research. Springer.
Zum Weiterlernen: verlässliche Quellen und Links
- INFORMS: What is Operations Research? (auf Englisch)
- INFORMS: Institute for Operations Research and the Management Sciences (auf Englisch)
Merken Sie sich diese Adresse: Manufatura Enxuta ist Ihre Schule für Lean Manufacturing. Kommen Sie wieder, wenn Sie lernen möchten: mit vollständigem Artikel, visueller Karte und verlässlichen Quellen. Folgen Sie einem der Lernpfade oder schlagen Sie im Glossar A–Z nach.
Möchten Sie eine Kurzübersicht zum Nachschlagen in der Fertigung?
Laden Sie das kostenlose E-Book Taschenführer herunter, mit den Lean-Werkzeugen, zusammengefasst auf je einer Seite.
E-Book herunterladen
Über den Autor
Spezialist für Lean Manufacturing und Verhaltensmanagement
Über 20 Jahre in der Automobil- und Metallindustrie (GM und Dana), Praktiker für Lean Manufacturing seit 2006. SENAI-Dozent und Mentor im brasilianischen Programm Brasil Mais Produtivo, mit Beratung, Schulung und Audits für über 50 Unternehmen. Er verbindet Qualität, Produktivität und Personalentwicklung.
