Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Welche Route ist die kürzeste? Wie liefere ich mehrere Kunden mit der Flotte? Klausurpflicht in 3/5 Produktions-Modulen und Standard in Logistik-Modulen.
Die Idee in einem Satz
Transportplanung optimiert Routen einzelner Fahrzeuge (TSP) oder ganzer Flotten (VRP), beide NP-schwer, daher in der Praxis Heuristiken wie Nearest-Neighbor oder Savings.
Klassische Probleme
TSP, Traveling Salesman Problem
Setup: 1 Fahrzeug, n Städte besuchen, kürzeste Rundreise mit Rückkehr zum Start.
Klassisches Beispiel: Handlungsreisender, der mehrere Städte besucht.
Mathematik:
- n Städte → (n-1)!/2 mögliche Touren
- Bei n=10: ~181.000 Touren
- Bei n=20: ~6×10^16 Touren
- Bei n=50: praktisch unberechenbar mit Brute Force
Komplexität: NP-schwer ab n > ~10 (Karp 1972 zeigte Reduktion auf Hamilton-Cycle).
VRP, Vehicle Routing Problem
Setup: mehrere Fahrzeuge mit Kapazitätsbeschränkung, n Kunden mit Bedarf, Touren vom/zum Depot.
Erweiterungen:
- CVRP (Capacitated VRP): Kapazitäts-Constraints
- VRPTW (mit Zeitfenstern): Lieferung in [a_i, b_i]
- MDVRP (Multi-Depot)
- HVRP (Heterogeneous Fleet): unterschiedliche Fahrzeug-Typen
- OVRP (Open VRP): kein Rückweg zum Depot
Auch NP-schwer. Praxis: kombinierte Probleme (CVRPTW etc.) extrem komplex.
TSP-Lösungs-Verfahren
Exakte Algorithmen
Brute Force: alle (n-1)!/2 Touren prüfen. Praktisch nur bis n=12.
Branch-and-Bound: systematisch durchsuchen mit Schranken-Schätzung. Praktisch bis n~40.
Dynamische Programmierung (Held-Karp 1962): O(n² × 2^n). Bis n~25.
Linear Programming + Cutting Planes: moderne LP-Relaxationen + Subtour-Elimination-Constraints. Concorde-Solver löst Instanzen mit n=85.900 Städten (USA-Beispiel 2006).
Heuristiken
Konstruktions-Heuristiken (bauen Tour von Grund auf):
- Nearest-Neighbor: Wähle wiederholt nächstliegende Stadt. O(n²). 15-25% über Optimum.
- Nearest-Insertion: Beginne mit kleinem Sub-Tour, füge wiederholt nächstliegende Stadt an günstigste Position. Etwa 10-15% über Optimum.
- Cheapest-Insertion: Füge Stadt an Position mit kleinstem Einfügekosten. Etwa 5-15%.
- Christofides (1976): O(n³). Garantiert ≤ 1.5 × Optimum für metrische TSPs.
Verbesserungs-Heuristiken (verbessern bestehende Tour):
- 2-opt: vertausche 2 Kanten. Einfach + sehr verbreitet.
- 3-opt: vertausche 3 Kanten. Besser, aber langsamer.
- Lin-Kernighan (LKH 1973/2000): variable Kanten-Vertauschung. State-of-the-Art-Heuristik, oft <1% über Optimum.
Meta-Heuristiken:
- Simulated Annealing: akzeptiert auch schlechtere Lösungen mit Wahrscheinlichkeit
- Tabu-Search: verbietet kürzlich besuchte Lösungen
- Genetische Algorithmen: Population + Crossover + Mutation
- Ant Colony Optimization: simulierte Ameisen + Pheromon-Spuren
VRP-Lösungs-Verfahren
Savings-Algorithmus (Clarke/Wright 1964)
Idee: Berechne Einsparung für jedes Kunden-Paar (i, j):
Savings(i, j) = d(0, i) + d(0, j) - d(i, j)
(d(0, x) = Distanz Depot zu x)
Vorgehen:
- Initialisiere: jeder Kunde = eigene Tour (Depot → Kunde → Depot)
- Berechne Savings für alle Paare
- Sortiere absteigend nach Savings
- Iteriere durch Liste: wenn beide Kunden in verschiedenen Touren UND Kapazität reicht → Touren zusammenfügen
- Stoppe wenn keine Merges mehr möglich
Komplexität: O(n² log n). Liefert typisch 5-10% über Optimum.
Sweep-Algorithmus (Gillett/Miller 1974)
Idee: Polarkoordinaten um Depot, sweep mit Strahl. Kunden in Reihenfolge des Sweeps in Touren clustern (bis Kapazität voll), dann innerhalb jeder Tour TSP lösen.
Komplexität: O(n log n) für Cluster + TSP pro Cluster.
Moderne Solver
- VROOM (Open-Source, C++)
- OR-Tools (Google): CP-SAT für VRP-Varianten
- PTV Route Optimiser: kommerzieller Standard
- Routific, OptimoRoute: SaaS-Lösungen
Standortplanung (Vorlauf zu Tourenplanung)
Erweiterungs-Topic: wo platziere ich Depots/Lager?
Schwerpunkt-Methode (Centroid)
x^* = (Σ_i w_i · x_i)/(Σ_i w_i)
mit w_i = Gewicht (Nachfrage) Kunde i, (x_i, y_i) Position.
Schnell + intuitiv für gewichteten Mittelpunkt. NICHT optimal bei mehreren Lägern.
Weber-Modell (Median in der Ebene)
Minimiere Σ_i w_i · d(x, c_i) wobei d = euklidische Distanz.
Iterative Lösung (Kuhn 1962, Weiszfeld-Algorithmus).
Set-Covering / p-Median
LP/MILP-Formulierungen für mehrere Lager.
Praxis-Komplikationen
- Zeitfenster (Pakete vor 12 Uhr)
- Mitarbeiter-Schichten + Pausen
- Fahrzeug-Beschränkungen (Brücken-Höhe, Innenstadt-Verbote)
- Dynamische Aufträge während des Tages
- Pickup-and-Delivery (PDP)
- Echtzeit-Verkehrsdaten (Google Maps API)
- Last-Mile-Delivery (Stadt-Logistik, Lieferzonen)
DACH-Praxis
- DHL: weltweit größte Routen-Optimierung, Brief + Paket. Eigene Algorithmen + KI.
- DPD, GLS, Hermes: ähnliche Algorithmen + Sub-Unternehmer.
- Amazon: über 30 Fulfillment-Center in DE, eigene Letzte-Meile-Logistik.
- Lieferando, Wolt: Echtzeit-Tourenplanung für Lebensmittel.
Klausur-Faustregeln
- TSP: 1 Fahrzeug + alle Städte + kürzeste Rundreise. NP-schwer ab n>10
- VRP: mehrere Fahrzeuge + Kapazität. Auch NP-schwer
- Nearest-Neighbor: O(n²), schnell aber 15-25% über Optimum
- Christofides: garantiert ≤ 1.5 × Optimum
- Savings-Algorithmus (Clarke/Wright 1964): Standard für CVRP
- Savings-Formel: s(i,j) = d(0,i) + d(0,j) − d(i,j)
- Schwerpunkt für 1 Standort: gewichteter Mittelpunkt
- Erweiterungen: VRPTW, MDVRP, HVRP, OVRP
Stolpersteine
❌ "TSP kann optimal in polynomialer Zeit gelöst werden", FALSCH. NP-schwer (Karp 1972). Concorde löst große Instanzen, aber nur durch raffinierte LP-Relaxationen + Branch-and-Cut.
❌ "Nearest-Neighbor ist optimal", FALSCH. Heuristik. 15-25% über Optimum typisch.
❌ "Savings funktioniert ohne Kapazitäts-Constraint", Vereinfachung. Original Clarke/Wright nutzt Kapazitäts-Constraints. Ohne wäre TSP ein Sonderfall.
❌ "Schwerpunkt ist optimal für Standortwahl", Vereinfachung. Schwerpunkt minimiert quadratische Distanzen. Weber-Modell minimiert SUMME der Distanzen (anderes Ziel).
❌ "VRPTW ist nur kleine Erweiterung", FALSCH. Mit Zeitfenstern wird VRP dramatisch komplexer (häufig 10-100× rechenintensiver).
Quellen
- Clarke, G.; Wright, J. W. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points", Operations Research 1964. Savings-Klassiker.
- Christofides, N. "Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem", Carnegie Mellon Tech Report 1976. 1.5-Approximations-Garantie.
- Lin, S.; Kernighan, B. W. "An Effective Heuristic Algorithm for the Traveling Salesman Problem", Operations Research 1973. Lin-Kernighan.
- Karp, R. M. "Reducibility Among Combinatorial Problems", IBM Symposium 1972. NP-Härte des TSP.
- Domschke, W. Logistik: Transport, 5. Aufl., Oldenbourg 2007. DACH-Standard.
- Domschke, W.; Scholl, A. Logistik: Rundreisen und Touren, 5. Aufl., Oldenbourg 2010.
- Toth, P.; Vigo, D. Vehicle Routing: Problems, Methods, and Applications, 2. Aufl., SIAM 2014.
- Pfohl, H.-C. Logistikmanagement, 3. Aufl., Springer 2016. DACH-Lehrbuch.
Interaktiv verstehen
Transport + Tourenplanung, TSP/VRP-Visualizer
Zwei Toggle-Ansichten: 1) TSP (Traveling Salesman Problem) mit Nearest-Neighbor-Heuristik, 7 Städte rund um ein Depot, klickbare Tour-Berechnung. 2) VRP (Vehicle Routing Problem) mit Savings-Algorithmus (Clarke/Wright 1964), Kapazität max. 3 Kunden pro Tour, mehrere Touren in unterschiedlichen Farben.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Savings-Formel s(i,j) = d(0,i) + d(0,j) − d(i,j) auswendig. Bei TSP-Aufgaben: NP-Härte erwähnen + Heuristiken nennen (Nearest-Neighbor schnell aber suboptimal / Christofides garantiert 1.5×OPT / Lin-Kernighan State-of-the-Art).
Praxis-Übung
Transport + Tourenplanung, Praxis-Übung
6 Aufgaben zu TSP, VRP und Heuristiken.
Klausurfragen mit Lösungen (6)
- F1.Was beschreibt das TRAVELING SALESMAN PROBLEM (TSP)?
Antwort: 1 Fahrzeug muss alle Städte besuchen und in kürzester Rundreise zum Start zurück. NP-schwer ab n>10
Erklärung: TSP: klassisches Routenplanungs-Problem. 1 Handlungsreisender + n Städte + kürzeste Rundreise + Rückkehr zum Start. NP-schwer (Karp 1972). Anzahl Touren = (n-1)!/2 → bei n=20 schon 6×10^16. Daher in Praxis Heuristiken wie Nearest-Neighbor (15-25% über Optimum), Christofides (≤1.5×OPT), Lin-Kernighan (oft <1%). Klausur-Pflicht-Definition.
- F2.Was unterscheidet VRP von TSP?
Antwort: VRP: mehrere Fahrzeuge mit Kapazitätsbeschränkung, Touren vom/zum Depot. TSP: nur 1 Fahrzeug
Erklärung: VRP (Vehicle Routing Problem) erweitert TSP: mehrere Fahrzeuge + Kapazitäts-Constraint pro Fahrzeug + alle Touren starten/enden am Depot. Erweiterungen: CVRP (capacitated), VRPTW (mit Zeitfenstern), MDVRP (Multi-Depot), HVRP (heterogene Flotte). NP-schwer. Praxis: Clarke/Wright Savings + moderne Solver (OR-Tools, VROOM). Klausur-Pflicht-Unterscheidung.
- F3.Ordne TSP-Algorithmus der Eigenschaft zu.
Zuordnungen:
- Nearest-Neighbor → O(n²), schnell, 15-25 % über Optimum, einfachste Heuristik
- Christofides (1976) → O(n³), GARANTIERT ≤ 1.5 × Optimum für metrische TSPs
- Lin-Kernighan (LKH) → State-of-the-Art-Heuristik, oft < 1 % über Optimum, variable Kanten-Vertauschung
- Concorde (Branch-and-Cut) → EXAKT, löst Instanzen mit 85.900 Städten (USA 2006)
Erklärung: Algorithmus-Hierarchie nach Qualität + Komplexität: Nearest-Neighbor (schnell/grob) → Christofides (Garantie) → Lin-Kernighan (sehr gut) → Concorde (exakt). Klausur-Pflicht-Tabelle für TSP-Verfahren.
Typ: Zuordnung
- F4.Wie berechnet sich die Savings im Clarke/Wright-Algorithmus?
Antwort: s(i,j) = d(0,i) + d(0,j) − d(i,j)
Erklärung: Savings-Formel (Clarke/Wright 1964): s(i,j) = d(0,i) + d(0,j) − d(i,j). Bedeutung: 'wie viel sparen wir, wenn wir i und j in einer Tour zusammenführen statt 2 separate Hin-/Rückwege ab Depot'. Höchste Savings → höchste Priorität für Merge. O(n² log n). Klausur-Pflicht-Formel.
- F5.Der Christofides-Algorithmus (1976) garantiert, dass die gefundene Lösung höchstens 1.5-mal so lang wie das Optimum ist, gilt nur für metrische TSPs (Dreiecks-Ungleichung erfüllt).
Antwort: Wahr
Erklärung: RICHTIG. Christofides-Algorithmus (Carnegie Mellon Tech Report 1976): nutzt Minimum Spanning Tree + Matching + Eulerkreis + Shortcuts. GARANTIERT 1.5-Approximation für metrische TSPs (Dreiecks-Ungleichung d(x,z) ≤ d(x,y) + d(y,z)). O(n³). Lange Zeit das beste Approximations-Verhältnis. 2020 von Karlin/Klein/Oveis Gharan auf 1.5−ε verbessert. Klausur-Pflicht-Garantie.
Typ: Wahr/Falsch
- F6.Welcher Solver löst auch sehr große TSP-Instanzen (>50.000 Städte) optimal?
Antwort: Concorde (Branch-and-Cut mit LP-Relaxation + Cutting Planes), löste USA 85.900-Städte-Instanz 2006
Erklärung: Concorde (Applegate/Bixby/Chvátal/Cook): state-of-the-art TSP-Solver. Kombiniert LP-Relaxation + Cutting Planes (Subtour-Elimination, 2-Matching, Comb-Inequalities) + Branch-and-Bound. Beweisbar OPTIMAL für 85.900-USA-Städte-Instanz 2006 (Pla85900). Brute Force unmöglich (84.000! Touren). Praktischer Beweis, dass NP-schwere Probleme oft konkret lösbar sind. Klausur-Wissen für moderne Optimierung.
Klausur-Quiz
Transport + Tourenplanung, Klausur-Quiz
6 Klausur-Fragen mit Komplexität + VRP-Erweiterungen + Standortplanung.
Klausurfragen mit Lösungen (6)
- F1.Wie viele mögliche Touren gibt es bei einem TSP mit n = 5 Städten?
Antwort: (n-1)!/2 = 12 Touren (wegen Symmetrie + Rotation)
Erklärung: Anzahl Touren bei TSP = (n-1)!/2. Erklärung: erste Stadt fixiert (Rotation reduziert um Faktor n), Richtung kann gedreht werden (Faktor 2). Bei n=5: 4!/2 = 12. Bei n=10: 181.440. Bei n=20: 6×10^16. Begründet die Exponentialität des Brute-Force-Ansatzes. Klausur-Pflicht-Formel.
- F2.Was ist eine 2-OPT-Verbesserung in TSP-Heuristiken?
Antwort: Vertausche 2 Kanten in der aktuellen Tour, wenn das die Gesamtdistanz verbessert. Einfach + sehr verbreitete Verbesserungs-Heuristik.
Erklärung: 2-opt (Croes 1958, Lin 1965): wähle zwei Kanten in der aktuellen Tour, kehre den Teilpfad zwischen ihnen um, wenn das die Distanz verbessert. Wiederhole bis lokal optimal. Einfach + viel verwendet. 3-opt vertauscht 3 Kanten (besser, langsamer). Lin-Kernighan ist generalisierte Variante. Klausur-Heuristik-Standard.
- F3.Vervollständige die Savings-Formel: s(i, j) = d(0, i) + d(0, {{1}}) − d({{2}}, j). Im Algorithmus iteriert man absteigend nach {{3}}.
Lösungen pro Lücke:
- {{1}}: j
- {{2}}: i
- {{3}}: Savings / s(i,j) / Einsparungen / savings
Erklärung: Clarke/Wright Savings-Algorithmus: s(i,j) = d(0,i) + d(0,j) − d(i,j). Höchste Savings → höchste Priorität für Tour-Merge. Iteration: 1) alle Savings berechnen, 2) absteigend sortieren, 3) durchgehen + mergen wenn Kapazität reicht. O(n² log n) Komplexität. Klausur-Pflicht-Verfahren.
Typ: Lückentext
- F4.Welche VRP-Erweiterung modelliert Lieferungen mit ZEITFENSTERN (Kunde kann nur in [a_i, b_i] empfangen)?
Antwort: VRPTW (Vehicle Routing Problem with Time Windows)
Erklärung: VRPTW: VRP mit Zeitfenstern. Jeder Kunde i hat Zeitfenster [a_i, b_i]. Fahrzeug muss Kunden in diesem Fenster bedienen, sonst Strafe oder Verbot. Sehr realistisch (Pakete vor 12 Uhr / Lieferzonen Innenstadt). Macht VRP 10-100× rechenintensiver. Erweiterungen: CVRPTW (kapazitätsbeschränkt + Zeitfenster), MDVRPTW (Multi-Depot). Standard-Bibliothek für Last-Mile-Delivery (DHL, Amazon).
- F5.Das Standortwahl-Problem mit SCHWERPUNKT-Methode liefert den OPTIMALEN Standort, der die SUMME der Distanzen minimiert.
Antwort: Falsch
Erklärung: FALSCH. Die Schwerpunkt-Methode (Centroid, gewichteter Mittelpunkt) minimiert die SUMME der QUADRIERTEN Distanzen (L²-Norm), NICHT die Summe der Distanzen (L¹-Norm). Für L¹-Minimierung braucht es das Weber-Modell mit iterativer Lösung (Weiszfeld-Algorithmus 1937, Kuhn 1962). Klausur-Stolperstein: Schwerpunkt ist schnell + intuitiv, aber das falsche Ziel für klassische Standortwahl.
Typ: Wahr/Falsch
- F6.Welche Komplexität hat der CLARKE/WRIGHT-Savings-Algorithmus?
Antwort: O(n² log n), n² Paare berechnen, dann sortieren
Erklärung: Savings: O(n² log n). Begründung: 1) n²/2 Kunden-Paare berechnen (Savings) = O(n²). 2) Sortieren nach Savings = O(n² log n). 3) Iteration durch sortierte Liste + Merge-Operationen = O(n² × α(n)) mit Union-Find. Dominante Komplexität: O(n² log n). Praktisch sehr schnell für n bis ~1000 Kunden. Klausur-Komplexitäts-Wissen.
