Optimierung elektrischer autonomer Ride-Sharing-Flotten, 31× schneller als die publizierte Branch-and-Price-Baseline mit bis zu 11× engeren Lücken
Ein ereignisbasiertes MILP, neu zentriert auf Abholungen und Abgaben (nicht Geographie), plus eine Adaptive-Large-Neighborhood-Search-Heuristik — auf 38 Standard-e-ADARP-Instanzen gegen Su (2023) Branch-and-Price gebenchmarkt
On-Demand-Ride-Sharing mit elektrischen autonomen Flotten ist die urbane Mobilitäts-Frontier. Das Optimierungsproblem ist brutal: Abhol-/Abgabe-Zeitfenster, Batteriedynamik, Umwege zur Ladestation, Fairness bei Fahrzeiten, alles zusammen, auf Instanzen mit Dutzenden Nutzern und mehreren Ladestationen.
Unsere mitbetreute Masterarbeit hat eine ereignisbasierte Graph-Formulierung entworfen, die das Modell um Abhol- und Abgabe-Ereignisse statt Standorte herum baut (Kapazitäts- und Pairing-Constraints implizit in der Topologie kodiert), plus eine Adaptive-Large-Neighborhood-Search-Heuristik, die auf Instanzgrössen skaliert, an denen exakte Methoden aufgeben.
Die Herausforderung
Das elektrische autonome Dial-A-Ride-Problem (e-ADARP) erweitert das klassische DARP um Batterie-State-of-Charge-Dynamik, freie Besuche von Ladestationen und eine gewichtete Mehrziel-Kostenfunktion, die Gesamtfahrstrecke gegen Excess-Fahrzeit der Nutzer abwägt. Bogenbasierte Formulierungen (Bongiovanni et al. 2019, Su 2023) bewältigen die Modellgrösse mit Column Generation, aber die Per-Knoten-Kombinatorik, Fahrzeugkapazität, Zeitfenster, Pairing von Abholungen und Abgaben, erzeugt riesige LP-Relaxierungen, die Branch-and-Price an jedem Knoten lösen muss.
Praktiker brauchen sowohl ein Modell, das die echte Physik erfasst, als auch eine Heuristik, die innerhalb von Sekunden auf grösseren Instanzen, wo exakte Methoden ins Stocken geraten, einsetzbare Pläne zurückgibt.
Unser Vorgehen
Wir haben die ereignisbasierte Graph-Formulierung von Gaul et al. (2022), von Stallhofer (2023) für Elektrofahrzeuge erweitert, aber auf Einmal-Laden beschränkt, auf den unbeschränkten-Besuche-Fall von Su (2023) adaptiert. Die Schlüsselidee: Knoten sind Q-Tupel, die kodieren, welche Nutzer im Fahrzeug sind, aufsteigend sortiert; Kanten sind zulässige Ereignisübergänge. Fahrzeugkapazität und Pairing von Abholung mit Abgabe sind in der Graphtopologie selbst kodiert, nicht als explizite lineare Constraints, was die LP-Relaxierung dramatisch schrumpfen lässt.
Wir haben die Formulierung weiter verschärft mit reisezeit-bewussten Zeitfenster-Kompatibilitätsprüfungen (ein Fortschritt gegenüber Stallhofers Kompatibilität-ohne-Reisezeit-Pruning), wodurch wir viele unzulässige Ereignisknoten a priori entfernen können. Kombiniert mit gültigen Ungleichungen für unzulässige Mehr-Stopp-Pfade löst das resultierende MILP type-a-Instanzen in zehn Sekunden und type-r-Instanzen in wenigen Stunden auf Gurobi.
Auf der Heuristik-Seite haben wir eine Adaptive Large Neighborhood Search mit einem Portfolio von Entfernungs-Operatoren (zufällig, schlechteste Distanz, verwandt), Insertion-Operatoren (greedy, regret-k), adaptiver Gewichts-Justierung und einem Simulated-Annealing-artigen Akzeptanzkriterium gebaut. Die Initialisierungsstrategie nutzt den einfacheren γ = 0,1-zulässigen-Bereich-Pre-Solve als Warmstart für die schwierigeren γ = 0,4- und γ = 0,7-Fälle.
Wir haben gegen das exakte Branch-and-Price-Baseline und die Deterministic-Annealing-Heuristik von Su (2023) auf den Standard-Bongiovanni-und-Ropke-Instanzensets benchmarkt (type-a urbane Szenarien, type-r realistische Instanzen, type-u urban mit Ladestations-Umzug).
Das Ergebnis
Deliverable: eine ereignisbasierte MILP-Formulierung für das elektrische autonome Dial-A-Ride-Problem (e-ADARP) plus eine Adaptive-Large-Neighborhood-Search-Heuristik, gegen die publizierte Branch-and-Price-Baseline von Su (2023) auf 38 Standard-Test-Instanzen (type-a, type-r, type-u) bei drei End-of-Day-Batterieverhältnissen (γ = 0,1, 0,4, 0,7) gebenchmarkt.
Ergebnisse der exakten Methode: 31× durchschnittliche Beschleunigung gegenüber B&P bei γ = 0,4 auf type-a (28,82 s vs. 910,33 s); 11× engere durchschnittliche Optimalitätslücke auf type-r γ = 0,1 (0,27 % vs. 3,02 %); 5× engere Lücke auf den schwierigsten type-r γ = 0,7 (1,24 % vs. 6,44 %); löst 35 / 38 Instanzen bei γ = 0,1 zur zertifizierten Optimalität vs. 33 / 38 für B&P. ALNS-Heuristik-Ergebnisse: 10× durchschnittliche Beschleunigung gegenüber der exakten Methode bei weniger als 1 % Zielfunktionsverlust, und auf r8-96 (der grössten type-r-Instanz, 96 Nutzer) findet die ALNS 1’026,08 in 2’058 s, wo die exakte ereignisbasierte Methode 18’000 s für ein leicht schlechteres 1’026,44 braucht — bessere Lösung in 9× weniger Zeit.
Technischer Deep Dive
Das Modell hinter dem Ergebnis.
Das Modell
Das e-ADARP ist ein Mehrziel-Routenproblem mit Batterie-Physik, die über ein klassisches Abhol-und-Abgabe-Problem gelegt ist. Die ereignisbasierte Reformulierung ist das Herzstück: Statt einer Entscheidungsvariable pro (Fahrzeug, Standort, Standort)-Tripel, was ein bogenbasiertes Modell ergäbe, haben wir eine Variable pro Kante in einem Ereignis-Graphen, in dem jeder Knoten bereits kodiert, wer im Fahrzeug ist. Fahrzeugkapazität (höchstens Q Nutzer) und Abholung-vor-Abgabe-Pairing werden strukturelle Eigenschaften des Graphen statt linearer Constraints. Das MILP behandelt dann nur noch das Globale: Zeit, Batterie und die Mehrziel-Kosten.
Ereignisknoten-Kodierung. Jeder Knoten v im Ereignisgraphen ist ein Q-Tupel, das das jüngste Abhol-/Abgabe-Ereignis in Slot 1 und die übrigen im Fahrzeug befindlichen Passagiere (aufsteigend sortiert) in den Slots 2..Q festhält. Nullen füllen leere Plätze; eine abschliessende −1 markiert Ladestations-Zustände. Konstruktiv kann das Tupel keinen Passagier enthalten, der bereits abgegeben wurde, Fahrzeugkapazität (höchstens Q Passagiere) und Abholung-vor-Abgabe-Pairing sind strukturell in V kodiert, nicht als Constraints.
Mehrziel-Kosten und Flusserhaltung. Die Zielfunktion tariert Fahrzeug-Routenkosten (∝ Reisezeit) gegen Excess-Fahrzeit R_i der Nutzer, mit Gewichten w_1, w_2 vom Betreiber gewählt. Flusserhaltung: An jedem Nicht-Depot-Ereignisknoten wird jede eingehende Kante von einer ausgehenden gedeckt. Zusammen mit dem expliziten ‘jeder Nutzer wird genau einmal bedient’ (Σ_{δ^in(v), v ∈ V_i} x_a = 1) ergibt das ein Minimum-Cost-Flow-Problem auf dem Ereignisgraphen.
Zeit-Constraints. Servicestartzeit T_w am nächsten Ereignis muss mindestens die Startzeit des vorherigen Ereignisses plus Servicezeit plus Reisezeit sein, mit Big-M (Horizont H), das die Constraint deaktiviert, wenn die Kante nicht genutzt wird. Die Fahrzeitschranke erzwingt Nutzerfairness: Für jeden Nutzer i darf die Zeit zwischen Abholung und Abgabe nicht die maximale Fahrzeit p_i überschreiten (das System darf jemanden nicht endlos im Fahrzeug halten, nur um die Route zu optimieren).
Batterie-State-of-Charge-Dynamik. Zwischen Nicht-Lade-Ereignissen ist der SoC am nächsten Knoten B_w gleich B_v minus der Entladung β_{(v,w)} = µ · t_{(v,w)} entlang der Kante. An Ladestations-Knoten (V_z) wird die Batterie um α · E_v aufgefüllt, wobei α die Laderate und E_v die Ladedauer ist. Symmetrische ≥-Versionen beider Constraints (ausgelassen) pinnen die Gleichheit, wenn die Kante benutzt wird. Die End-of-Day-Constraint B_v ≥ γG zwingt Fahrzeuge, mit mindestens einem γ-Anteil der Kapazität ins Depot zurückzukehren (der Headline-Parameter im Benchmark, γ = 0,7 ist der harte Fall).
Excess-Fahrzeit. R_i ist das Nutzerfairness-Mass: die Differenz zwischen der tatsächlichen Fahrzeit (T_Abgabe − T_Abholung − Servicezeit) und der minimalen direkten Fahrzeit t_{(i, n+i)}. Die Minimierung der Gesamt-Σ R_i ist die zweite Zielfunktion, ohne sie würde der Optimierer Nutzer stundenlang im Fahrzeug halten, um Fahrten zu konsolidieren.
Warum die ereignisbasierte Formulierung gewinnt. Das bogenbasierte Modell (Bongiovanni 2019, Su 2023) hat eine Variable pro (Fahrzeug, Standort, Standort)-Tripel, aber die meisten dieser Tripel sind unzulässig (falscher Kapazitätszustand, Zeitfenster-Verletzung, Pairing-Verletzung), und der Solver muss das während Branch-and-Bound entdecken. Der Ereignisgraph prunt unzulässige Zustände bei der Konstruktion: Die Zeitfenster-und-Reisezeit-Kompatibilitätsprüfungen entfernen Knoten, die ein bogenbasiertes Modell behalten würde. Für type-a-Instanzen bei Q = 6 erhalten wir ~150–1 500 Knoten und ~1 500–16 000 Kanten, beherrschbar für Gurobis Branch-and-Cut.
Gültige Ungleichung für unzulässige Pfade. Für jeden Nutzer i und jeden Zwei-Kanten-Pfad P = (a, b) im Ereignisgraphen, in dem i im Fahrzeug ist und die kombinierte Fahrzeit p_i überschreitet, können höchstens |P| − 1 = 1 der Kanten aktiv sein. Diese Ungleichungen vorne einzufügen (statt darauf zu warten, dass Branch-and-Bound sie über Cuts entdeckt) verschärft die LP-Relaxierung auf type-r- und type-u-Instanzen spürbar.
Die ereignisbasierte Formulierung ist die strukturelle Innovation; die ALNS ist die einsatzbereite Engineering-Schicht darüber. Auf kleinen bis mittleren Instanzen (16–48 Nutzer, 2–5 Fahrzeuge) löst das ereignisbasierte MILP zur nachgewiesenen Optimalität schneller als das publizierte B&P-Baseline. Auf den grössten Instanzen (96 Nutzer auf type-r, 50 Nutzer auf type-u) beginnt das MILP bei γ = 0,7 ins Zeitlimit zu laufen, und die ALNS übernimmt mit nahezu optimalen Lösungen in Sekunden bis Minuten. Im Vergleich zum Deterministic-Annealing-Baseline von Su (2023) findet die ALNS in den meisten Fällen gleichwertige oder bessere Zielfunktionswerte, zum Preis etwas mehr Wall-Clock-Zeit. Das Ergebnis ist ein Zwei-Tier-System: das exakte ereignisbasierte MILP nutzen, wo es geht; auf die ALNS zurückfallen, wo nicht.
Benchmark
Ereignisbasiertes MILP vs. Su (2023) Branch-and-Price auf type-r-Benchmark-Instanzen (Bongiovanni-Ropke realistisches Testbett, End-of-Day-Batterieverhältnis γ = 0,7, das schwierigste Setting). Jede Zeile ist eine (Fahrzeuge, Nutzer)-Instanz. Zielfunktionswerte in gewichteten Einheiten (Routenkosten + Excess-Fahrzeit); Lücken in % vs. nachgewiesener unterer Schranke. Zeitlimit 18 000 s. Niedrigere Zielfunktion ist besser; niedrigere Lücke ist besser.
| Instanz | Ereignisbasiert Obj. | EB Lücke (%) | EB Zeit (s) | Su (2023) B&P Obj. | B&P Lücke (%) | B&P Zeit (s) |
|---|---|---|---|---|---|---|
| r5-60 | 686,36 | 0,10 | 18 000 | 688,84 | 0,70 | 18 000 |
| r6-48 | 508,10 | 0,00 | 2 364 | 508,10 | 0,00 | 2 028 |
| r6-60 | 689,55 | 0,00 | 1 703 | 689,55 | 0,00 | 6 605 |
| r6-72 | 765,25 | 0,41 | 18 000 | 788,83 | 4,96 | 18 000 |
| r7-56 | 615,86 | 0,52 | 18 000 | 616,16 | 0,00 | 14 247 |
| r7-70 | 756,31 | 0,04 | 18 000 | 765,49 | 1,48 | 18 000 |
| r7-84 | 891,38 | 2,39 | 18 000 | 1 004,81 | 21,65 | 18 000 |
| r8-64 | 632,61 | 0,00 | 2 493 | 632,61 | 0,00 | 18 000 |
| r8-80 | 806,87 | 2,19 | 18 000 | 794,41 | 0,00 | 15 051 |
| r8-96 | 1 064,86 | 6,74 | 18 000 | 1 174,49 | 35,68 | 18 000 |
| Ø | - | 1,24 | 13 256 | - | 6,44 | 14 593 |
Zwei Muster. Erstens: Das ereignisbasierte MILP erreicht eine 5× engere durchschnittliche Optimalitätslücke (1,24 % vs. 6,44 %) auf diesen harten γ = 0,7-Instanzen, und auf der grössten (r8-96) beträgt die Lückendifferenz 6,74 % vs. 35,68 %, wobei der ereignisbasierte Lösungswert 9,3 % besser ist. Zweitens: Auf den Instanzen, die beide Methoden zur Optimalität lösen (r6-48, r6-60, r8-64), ist das ereignisbasierte MILP konsistent schneller, manchmal um Faktor 7 (r8-64: 2 493 s vs. 18 000 s für B&P). Das strukturelle Pruning bei Graph-Konstruktion zahlt sich am meisten auf Instanzen mit engen Zeitfenstern und vielen Nutzern aus, genau dort, wo das bogenbasierte B&P kämpft. Auf einfacheren γ = 0,1-Instanzen (nicht gezeigt) ist die Lücke noch lopsidiger: ereignisbasiert 0,27 % Ø vs. B&P 3,02 %, eine 11× engere Lücke.
Aus den Unterlagen
Techniken
- Ereignisbasierte Graph-Formulierung
- Gemischt-ganzzahlige lineare Programmierung (B&C über Gurobi)
- Adaptive Large Neighborhood Search
- Entfernungs-/Insertion-Operator-Portfolio
- Simulated-Annealing-Akzeptanz
- Gültige Ungleichungen für unzulässige Pfade
Stack
- Julia
- Gurobi
- Bongiovanni-Ropke-Instanz-Benchmarks
Ein Problem wie dieses?