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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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).
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
Transportplanung optimiert Routen einzelner Fahrzeuge (TSP) oder ganzer Flotten (VRP) — beide NP-schwer, daher in der Praxis Heuristiken wie Nearest-Neighbor oder Savings.
Setup: 1 Fahrzeug, n Städte besuchen, kürzeste Rundreise mit Rückkehr zum Start.
Klassisches Beispiel: Handlungsreisender, der mehrere Städte besucht.
Mathematik:
Komplexität: NP-schwer ab n > ~10 (Karp 1972 zeigte Reduktion auf Hamilton-Cycle).
Setup: mehrere Fahrzeuge mit Kapazitätsbeschränkung, n Kunden mit Bedarf, Touren vom/zum Depot.
Erweiterungen:
Auch NP-schwer. Praxis: kombinierte Probleme (CVRPTW etc.) extrem komplex.
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).
Konstruktions-Heuristiken (bauen Tour von Grund auf):
Verbesserungs-Heuristiken (verbessern bestehende Tour):
Meta-Heuristiken:
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:
Komplexität: O(n² log n). Liefert typisch 5-10% über Optimum.
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.
Erweiterungs-Topic: wo platziere ich Depots/Lager?
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.
Minimiere Σ_i w_i · d(x, c_i) wobei d = euklidische Distanz.
Iterative Lösung (Kuhn 1962, Weiszfeld-Algorithmus).
LP/MILP-Formulierungen für mehrere Lager.
❌ "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).
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).
6 Aufgaben zu TSP, VRP und Heuristiken.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.
6 Klausur-Fragen mit Komplexität + VRP-Erweiterungen + Standortplanung.
Klausurfragen mit Lösungen (6)
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.
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.
Lösungen pro Lücke:
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
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).
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
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.