💻 computer science

Meeting equity requirements in shared micromobility rebalancing: a constrained Markov decision process with a case study in The Hague

Dieses Paper schlägt ein Framework für einen eingeschränkten Markov-Entscheidungsprozess (Constrained Markov Decision Process, CMDP) unter Verwendung von faktorisierter Lagrangian-Q-Learning vor, um das gemeinschaftliche Micromobility-Rebalancing zu optimieren, indem explizit Schwellenwerte für die Gerechtigkeit bei Serviceausfallraten erzwungen werden, was sowohl durch synthetische Netzwerke als auch durch eine reale Fallstudie in Den Haag validiert wurde.

Ursprüngliche Autoren: Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Veröffentlicht 2026-07-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Originalarbeit lizenziert unter CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Stadt voller Leihräder oder E-Scooter vor. Im Moment verhalten sich diese Fahrzeuge oft wie eine beliebte Party: Alle wollen dorthin, wo der Spaß ist (das Stadtzentrum), sodass sich die Fahrzeuge dort stapeln. Währenddessen bleiben die ruhigeren Viertel am Stadtrand leer zurück. Wenn Sie in diesen Außenbezirken leben, benötigen Sie vielleicht eine Fahrt, finden aber keine verfügbaren Fahrzeuge vor.

Die Betreiber dieser Fahrradsysteme versuchen meist, die Fahrzeuge so zu bewegen, dass sie den Gewinn maximieren. Das macht das Problem von Natur aus noch schlimmer, da sie ständig Fahrräder in die belebten, wohlhabenden Zentren schicken und die ärmeren Außenbezirke ignorieren.

Städte beginnen nun zu sagen: „Stopp! Wir brauchen Fairness.“ Sie wollen sicherstellen, dass auch die Viertel am Stadtrand über genügend Fahrräder verfügen. Aber hier liegt das Problem: Einem Computer zu sagen: „Sei fair“, ist vage. Wenn man einem Computer nur sagt: „Versuche, fair zu sein“, muss er raten, wie stark er sich bemühen soll. Es ist, als würde man einem Koch sagen: „Mach die Suppe ein bisschen weniger salzig“, ohne genau zu sagen, wie viel Salz man entfernen soll. Der Koch könnte falsch raten, die Suppe entweder zu fad oder immer noch zu salzig machen, und er muss immer wieder probieren und nachjustieren, bis er es richtig hinbekommt.

Die Lösung des Papers: Das „Tempolimit“ für Fahrräder

Die Autoren dieses Papers haben einen klügeren Weg gefunden, mit dem Computer zu kommunizieren. Anstatt ihn zu bitten, zu „raten“, wie Fairness aussieht, gaben sie ihm eine strikte Regel, ähnlich einem Tempolimit.

Der alte Weg (Reward Shaping): Der Computer erhält für jede Bewegung eine Punktzahl. Wenn er ein Fahrrad in ein armes Viertel bewegt, bekommt er ein paar Extrapunkte. Aber der Computer muss raten, wie viele Punkte nötig sind, damit sich der Aufwand lohnt. Es ist ein Spiel aus Versuch und Irrtum.
Der neue Weg (Constrained Decision Making): Die Stadt setzt die Regel: „In keinem Viertel darf die Quote der Fahrgäste, die kein Fahrrad finden können, über 5 % liegen.“ Der Computer rät nicht. Er muss den kostengünstigsten Weg finden, um Fahrräder zu bewegen, während er diese Regel strikt einhält. Wenn er die Regel bricht, erhält er eine schwere Strafe. Wenn er die Regel befolgt, kann er seine Kosten niedrig halten.

Wie es funktioniert: Der Verkehrspolizist und die Zonen

Die Forscher unterteilten die Stadt in verschiedene Arten von Vierteln (Zonen), vom Stadtzentrum bis zu den fernen Außenbezirken. Sie erstellamen für jeden Typ von Viertel einen „Verkehrspolizisten“.

Die Regel: Die Stadt legt eine Grenze für die „Ausfallrate“ fest (z. B. „In den Außenbezirken dürfen nur 5 % der Menschen kein Fahrrad finden“).
Das Preisschild: Der Computer verwendet ein spezielles Werkzeug namens „Lagrange-Methode“. Stellen Sie sich dies als ein dynamisches Preisschild vor.
- Wenn in den Außenbezirken die Fahrräder knapp werden und Menschen keine Fahrt finden können, steigt der „Preis“ für das Versagen an. Der Computer sieht diesen hohen Preis und denkt: „Oh nein, ich muss mehr Fahrräder dorthin bewegen, um diese teure Strafe zu vermeiden!“
- Wenn die Viertel über genügend Fahrräder verfügen, sinkt der Preis, und der Computer hört auf, Geld mit dem Verschieben von Fahrrädern dorthin zu verschwenden.
Das Ergebnis: Der Computer lernt die exakte Strategie, um die Ausfallrate unter dem Limit zu halten und gleichzeitig so wenig wie möglich Geld auszugeben.

Was sie herausgefunden haben

Die Forscher testeten dies auf zwei Arten:

Eine fiktive Stadt (Synthetisches Netzwerk): Sie erstellten eine Computersimulation einer Stadt. Sie fanden heraus, dass diese neue Methode exakt die Ziele der Stadt bei der „Ausfallrate“ erreichen konnte. Wenn die Stadt sagte: „Wir wollen 5 % oder weniger“, lieferte das System 5 % oder weniger.
- Die Kosten: Wenn die Stadt strengere Regeln forderte (z. B. die Senkung der Ausfallrate von 10 % auf 5 %), stiegen die Kosten für das Bewegen der Fahrräder. Das ist logisch: Es kostet mehr Geld, sicherzustellen, dass jeder ein Fahrrad hat, als einfach nur die belebten Gebiete zu bedienen.
- Die Metrik: Sie entdeckten auch, dass ein gängiges Maß für Fairness (der sogenannte „Gini-Index“) eigentlich ein schlechtes Werkzeug für diese Aufgabe ist. Es ist, als würde man Fairness dadurch messen, wie gleich alle sind. Aber das Ziel ist hier nicht, alle gleich zu machen; das Ziel ist es, sicherzustellen, dass die am schlechtesten Gestellten genug haben. Die neue Methode verbesserte die Situation in den am schlechtesten gestellten Gebieten, ohne die wohlhabenderen Gebiete zu benachteiligen, was tatsächlich den „Gleichheitswert“ schlechter aussehen ließ, obwohl die Situation für die Armen besser wurde.
Echte Stadt (Den Haag, Niederlande): Sie wandten dies auf echte Daten aus Den Haag an, unter Verwendung tatsächlicher Fahrradstationen und Reiseumfragen.
- Sie bauten ein Modell des Fahrradnetzes der Stadt.
- Sie zeigten, dass das System selbst mit den unordentlichen Echtzeitdaten der realen Welt in der Lage war, die Regeln zu lernen und eine Strategie zu entwickeln.
- Der Haken: Wenn sie die Regeln extrem eng fassten (wie eine Ausfallrate von 0,5 %), hatte das System in den kleinsten, volatilsten Vierteln leichte Schwierigkeiten. Es ist schwer, in jedem einzelnen winzigen Ort Perfektion zu garantieren, wenn man eine einzige Strategie für eine ganze Gruppe von Vierteln verwendet. Für vernünftige Regeln funktionierte es jedoch gut.

Das Fazit

Dieses Paper zeigt, dass Städte nicht raten müssen, wie sie das Teilen von Fahrrädern fair gestalten. Anstatt den Betreibern vage Anweisungen zu geben, können sie eine klare, harte Grenze setzen, wie viele Menschen ohne Fahrt bleiben dürfen. Der Computer kann dann den kosteneffizientesten Weg finden, um dieses Limit einzuhalten. Dies verwandelt ein vages Ziel wie „Fairness“ in einen konkreten, erreichbaren Plan mit einem bekannten Preis.

Technische Zusammenfassung: Anforderungen an die Gerechtigkeit bei der Begegnung von Equity-Anforderungen in der gemeinsamen Mikromobilität-Rebalancing

Problemstellung
Systeme der geteilten Mikromobilität reproduzieren oft urbane Ungleichheiten, indem sie Fahrzeuge in Gebieten mit hoher Nachfrage, im Zentrum und in wohlhabenden Vierteln konzentrieren, während periphere und einkommensschwache Zonen unterversorgt bleiben. Standardmäßige Rebalancing-Strategien, die typischerweise den Umsatz maximieren, verstärken diesen „Splintering Urbanism“ (fragmentierte Urbanität). Während Städte zunehmend Gerechtigkeitsanforderungen stellen – wie etwa Mindestfahrzeuganteile in bestimmten Zonen –, haben aktuelle operative Methoden Schwierigkeiten, diese Vorgaben effizient zu erfüllen. Bestehende Reinforcement Learning (RL)-Ansätze versuchen, Fairness durch das Hinzufügen eines gewichteten Strafwertes zur Belohnungsfunktion zu integrieren. Diese Methode beruht jedoch auf einer Trial-and-Error-Abstimmung des Strafgewichts, bietet keine direkte Garantie, dass ein regulatorischer Schwellenwert (z. B. eine maximale Service-Ausfallrate) eingehalten wird, und ermöglicht zudem keine klare Kosten-Nutzen-Analyse für die Verschärfung solcher Regeln.

Methodik
Die Autoren formulieren das Problem des Flotten-Rebalancings als ein Constrained Markov Decision Process (CMDP) um. Anstatt Fairness implizit über Reward Shaping zu kodieren, behandelt die Methode Gerechtigkeit als explizite Nebenbedingung für die Service-Ausfallrate (den Anteil der Nutzer, die kein Fahrzeug vorfinden).

Formulierung: Das Einsatzgebiet wird in Zonen unterteilt, die in Kategorien gruppiert sind (von peripher bis zentral). Das Problem wird als MDP modelliert, wobei der Zustand die Zeitperiode, die Zonenkategorie und den Fahrzeugbestand umfasst. Das Ziel ist die Maximierung der langfristigen Belohnung (Minimierung der Rebalancing-Kosten und Fahrzeugstrafen) unter der Bedingung, dass die erwartete Service-Ausfallrate für jede Zonenkategorie und Zeitperiode einen von der Stadt definierten Schwellenwert ( $r_{max}$ ) nicht überschreitet.
Lösungsalgorithmus: Das CMDP wird mittels Factorized Lagrangian Q-learning gelöst.
- Lagrange-Relaxierung: Die Nebenbedingung wird durch die Einführung eines adaptiven Strafwertes (eine duale Variable $\lambda$ ) für jede Kategorie und Periode dualisiert. Diese Variable fungiert als Preis für Service-Ausfälle und steigt an, wenn Ausfälle das Ziel überschreiten, und sinkt, wenn sie darunter fallen.
- Faktorisierung: Unter der Annahme einer unabhängigen Nachfrage über die Zonen hinweg wird das Problem in pro-Zone Subprobleme zerlegt, die von einem Agenten pro Kategorie verwaltet werden. Alle Zonen innerhalb einer Kategorie teilen sich eine einzige Q-Tabelle, die durch die kombinierte Erfahrung aller Zonen dieser Kategorie aktualisiert wird.
- Primal-Dual-Updates: Der Algorithmus wechselt zwischen der Aktualisierung der Q-Werte (Primal), um die modifizierte Belohnung (Basisbelohnung abzüglich $\lambda \times$ Ausfälle) zu optimieren, und der Aktualisierung der dualen Variablen (Dual) basierend auf der durchschnittlichen Verletzung der Ausfall-Nebenbedingung über ein gleitendes Zeitfenster.
Reale Anpassung: Für die Fallstudie in Den Haag passten die Autoren das Modell an, um Zonen mit ungleichen Kapazitäten zu handhaben, indem sie den Fahrzeugbestand zu einem Belegungsanteil (0 bis 1) normalisierten. Sie konstruierten Servicezonen mittels gewichteter k-Means-Clustering von Stationstandorten und schätzten die Nachfrage anhand nationaler Reiseumfragen (ODiN) und Adressregister.

Wesentliche Beiträge

Direkte Einhaltung von Nebenbedingungen: Die Methode ermöglicht es einer Stadt, eine maximale Service-Ausfallrate direkt anzugeben, was die Trial-and-Error-Abstimmung von Fairness-Gewichten überflüssig macht. Der Algorithmus passt die Rebalancing-Strategie automatisch an, um die Grenze einzuhalten.
Kostentransparenz: Der Ansatz quantifiziert die operativen Kosten zur Erfüllung spezifischer Gerechtigkeitsziele. Er zeigt auf, dass mit dem Verschärfen der Ausfallraten-Grenze die Rebalancing-Kosten steigen, was Städten erlaubt, die Kosten strengerer Regeln vor deren Einführung zu bewerten.
Metrikwahl: Das Paper argumentiert, dass der Gini-Index ungeeignet ist, um einen „Service-Boden“ durchzusetzen. Während Reward Shaping (das die Raten angleicht) den Gini-Index reduziert, hält der eingeschränkte Ansatz einen hohen Service in zentralen Zonen aufrecht, während er die peripheren Zonen verbessert. Dies kann dazu führen, dass der Gini-Index stagniert oder sogar leicht ansteigt, während die Worst-Case-Ausfallrate sinkt, was die Worst-Case-Ausfallrate zu einer angemesseneren Metrik für dieses spezifische Ziel macht.
Praxisrelevanz: Eine Fallstudie in Den Haag demonstriert, dass die Methode unter Verwendung öffentlich verfügbarer Daten (Stations-Feeds, Adressregister und Reiseumfragen) angewendet werden kann, um eine trainierte Rebalancing-Strategie zu generieren.

Ergebnisse

Synthetisches Netzwerk: In einem synthetischen Netzwerk mit fünf Kategorien erfüllte die Methode die spezifizierten Ausfallraten-Schwellenwerte erfolgreich über alle Zonenkategorien und Zeitperioden hinweg. Als die Grenze ( $r_{max}$ ) von 100 % auf 5 % verschärft wurde, sank die Worst-Case-Ausfallrate monoton, während die Rebalancing-Kosten etwa verdoppelt wurden. Die zentralen Zonen blieben von den Nebenbedingungen unbeeinflusst, während die peripheren Zonen signifikante Verbesserungen in der Verfügbarkeit erfuhren.
Vergleich mit Reward Shaping: Im Vergleich zur Reward-Shaping-Baseline verschlechterte der eingeschränkte Ansatz den Service in gut versorgten zentralen Zonen nicht, um die Lücke zu schließen. Stattdessen konzentrierte er die Ressourcen auf die unterversorgten Zonen, um den absoluten Schwellenwert einzuhalten.
Fallstudie Den Haag: Wendete man das System auf reale Daten an, performte es bereits gut (ca. 2,8 % Ausfallrate im Worst Case ohne Nebenbedingungen). Bei Tests mit strengeren Grenzen reagierte die Methode durch Erhöhung der Flottengröße und der Rebalancing-Operationen. Bei den engsten Grenzen (0,5 % und 0,75 %) überschritten die periphersten Zonen jedoch leicht das Limit aufgrund der pro-Kategorie Faktorisierung (die eine Strategie für Zonen unterschiedlicher Größe teilt), was den Trade-off zwischen Recheneffizienz und granularer Kontrolle verdeutlicht.

Bedeutung und Behauptungen
Die Autoren behaupten, dass diese Arbeit die Lücke zwischen regulatorischen Gerechtigkeitsanforderungen und operativer Entscheidungsfindung schließt. Durch die Formulierung des Rebalancings als CMDP transformiert die Methode ein Gerechtigkeitsziel in einen Planungsinput mit bekanntem Preis. Sie ermöglicht es Städten, ergebnisbasierte Regeln (Servicelevel) statt präskriptiver Inputs (Fahrzeuganzahl) durchzusetzen, was den Empfehlungen von Gremien wie der Internationalen Transportforum entspricht. Das Paper schließt mit dem Hinweis, dass dieser Ansatz einen gangbaren Weg zur Erreichung der Ziele des UN-Nachhaltigkeitsziels 11.2 darstellt, indem er einen Mechanismus bietet, um einen Service-Boden in unterversorgten Gebieten zu halten, ohne die Effizienz des restlichen Netzwerks zu gefährden. Die Autoren bleiben bescheiden und merken an, dass das aktuelle Modell eine unabhängige Nachfrage und feste Rebalancing-Zeitpunkte annimmt und dass zukünftige Arbeit notwendig ist, um Korrelationen in der Nachfrage, Rebalancing innerhalb von Zeitintervallen und die Online-Adaption an driftende Nachfragemuster zu adressieren.

Mehr davon