Verbesserung von Bikesharing-Systemen mit Dual Policy Learning

Fahrradverleihsysteme (BSS) werden in Städten weltweit immer beliebter. Sie helfen, den Verkehr zu reduzieren und motivieren die Leute, aktiver zu sein, indem sie Fahrrad fahren statt zu fahren. Allerdings können diese Systeme Schwierigkeiten haben, die Fahrräder dort verfügbar zu halten, wo die Leute sie brauchen. Wenn zu viele Fahrräder an einer Station und zu wenige an einer anderen sind, kann das unzufriedene Nutzer zur Folge haben. Um das zu beheben, müssen die Betreiber regelmässig Fahrräder umstellen, ein Prozess, der als Neuausgleich bezeichnet wird.

#Der Bedarf an Echtzeit-Neuausgleich

BSS hängen davon ab, dass die Stationen zu jedem Zeitpunkt die richtige Anzahl an Fahrrädern für die Nutzer haben. Allerdings kann die Nutzernachfrage im Laufe des Tages je nach Wetter, Uhrzeit und anderen Faktoren schwanken. Hier kommt der Echtzeit-Neuausgleich ins Spiel. Es ist wichtig, dass die Betreiber Strategien haben, die sich an veränderte Bedingungen anpassen und die Stationen mit Fahrrädern versorgen.

#Das dynamische Neupositionierungsproblem (DBRP)

Die Herausforderung, Fahrräder in BSS umzuverteilen, wird als dynamisches Neupositionierungsproblem (DBRP) bezeichnet. Es geht darum, herauszufinden, wie viele Fahrräder bewegt werden müssen, wo sie hingebracht werden sollen und sicherzustellen, dass die Bewegung zur richtigen Zeit erfolgt. Die Betreiber haben normalerweise eine Flotte von Fahrzeugen, um diese Aufgabe zu unterstützen.

Im DBRP müssen Entscheidungen in zwei Hauptbereichen getroffen werden: Bestand (wie viele Fahrräder abgeholt oder abgestellt werden) und Routing (welche Station als nächstes besucht werden soll). Diese Entscheidungen gleichzeitig zu treffen, ist nicht immer effektiv, besonders da die Anzahl der verfügbaren Fahrräder und die Nachfrage der Nutzer sich schnell ändern kann.

#Die Rolle des Reinforcement Learning

Neuere Forschungen haben sich dem Reinforcement Learning (RL) zugewandt, um die Verwaltung der Fahrräder in BSS zu verbessern. RL ermöglicht es Systemen, optimale Strategien basierend auf Interaktionen mit ihrer Umgebung zu lernen und die Aktionen anzupassen, um die Belohnung zu maximieren. Durch den Einsatz von RL können Betreiber bessere Richtlinien entwickeln, die die sich ändernde Nachfrage und die Bedingungen an den Stationen berücksichtigen.

#Ein neuer Ansatz mit Dual Policy Reinforcement Learning

Diese Studie stellt eine neue Methode vor, die als Dual Policy Reinforcement Learning (DPRL) bezeichnet wird, um das DBRP anzugehen. Anstatt Bestands- und Routingentscheidungen gleichzeitig zu treffen, trennt DPRL die beiden. Das bedeutet, dass zuerst entschieden wird, wie viele Fahrräder an einer Station abgeholt oder abgestellt werden. Sobald das erledigt ist, kann das Fahrzeug dann entscheiden, wo es als nächstes hingehen soll.

Durch die Entkopplung dieser Entscheidungen erfasst das Framework die sich ändernden Bedingungen realistischer. Dies minimiert den Verlust an Nachfrage und sorgt dafür, dass Nutzer Fahrräder mieten können, wann immer sie sie wollen.

#Struktur der Studie

#Verwandte Arbeiten

Die meisten früheren Studien haben sich darauf konzentriert, Mixed Integer Programming (MIP) zur Lösung des DBRP zu verwenden. Während MIP gute Ergebnisse liefern kann, erfordert es oft die Vereinfachung des Problems, was möglicherweise die realen Bedingungen nicht genau widerspiegelt. Einige Forscher haben begonnen, Markov-Entscheidungsprozesse (MDP) anzuwenden, um die sequenziellen Entscheidungen in BSS zu skizzieren, aber diese Ansätze haben die Probleme nicht vollständig gelöst.

#Das Dual Policy Framework

Im vorgeschlagenen DPRL-Framework werden zwei verschiedene Netzwerke verwendet, um Entscheidungen zu Beständen und Routing zu treffen. Durch die separate Behandlung jedes Problems kann das System besser auf Echtzeitänderungen reagieren. Die sofortige Belohnung ist an den verlorenen Bedarf über die Stationen während der Betriebszeit des Fahrzeugs gebunden. Wenn ein Fahrzeug seine Bestandsentscheidung trifft, kann das die nächste Routingwahl beeinflussen.

#Simulations- und Lernprozess

Um das DPRL-Modell zu trainieren, wird ein umfassender Simulator eingesetzt. Dieser Simulator läuft nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“ und simuliert, wie Nutzer Fahrräder mieten und zurückgeben. Die Umgebung hält fest, wie viele Fahrräder in jeder Station verfügbar sind und wo sich jedes Fahrzeug befindet.

Der Trainingsprozess beinhaltet, den Simulator mit Daten zu füttern, sodass die Netzwerke lernen und ihre Richtlinien basierend auf den erhaltenen Belohnungen anpassen. Das hilft, die Genauigkeit der Entscheidungen im Laufe der Zeit zu verbessern.

#Experimenteller Aufbau

Die Studie testete das DPRL-Framework gegen verschiedene Benchmarks. Es wurden zwei Datensätze erstellt, die unterschiedliche Bedingungen widerspiegeln. Jeder Datensatz enthielt Fahrten, die verschiedene Nachfrageszenarien zeigten. Die Ergebnisse helfen zu veranschaulichen, wie DPRL in realen Situationen abschneidet.

Die Studie nutzte vier Fahrzeuge, um die Neuausgleichsoperationen zwischen mehreren Stationen durchzuführen. Verschiedene Modelle wurden zum Vergleich eingesetzt, darunter statische und dynamische Methoden sowie andere RL-Ansätze.

#Benchmark-Modelle

1. Statischer Neuausgleich (SR): Diese Methode optimiert die Anfangsbestände der Stationen ohne weitere Anpassungen im Laufe des Tages.
2. Dynamischer Neuausgleich (DR): Diese Methode verwendet MIP, um die Fahrradverteilung kontinuierlich basierend auf der prognostizierten Nachfrage anzupassen.
3. RL-Bestandsverwaltung mit heuristischem Routing (RIHR): Dieser Ansatz kombiniert eine Bestandsrichtlinie mit einer heuristischen Routingmethode.
4. RL-Routing mit heuristischer Bestandsverwaltung (RRHI): Die Routingrichtlinie entscheidet, welche Station als nächstes besucht wird, während die Bestandsrichtlinie einem heuristischen Modell folgt.
5. RL mit gleichzeitigen Bestands- und Routingentscheidungen (RSIR): Dieses Modell kombiniert die Bestands- und Routingentscheidungen gleichzeitig.

#Ergebnisse und Diskussion

#Gesamtleistung

Bei der Analyse der Ergebnisse hat das DPRL-Modell durchgängig besser abgeschnitten als die anderen Ansätze. Es erzielte die niedrigsten Werte für verlorene Nachfrage und verbesserte sich signifikant gegenüber sowohl statischen als auch dynamischen Modellen. Insbesondere konnte DPRL die verlorene Nachfrage um 48,4 % im Vergleich zu einem dynamischen Modell und um 34,2 % im Vergleich zu einem anderen RL-Modell reduzieren.

#Lernprozess

Im Verlauf des Trainings zeigte das Modell eine allgemeine Verbesserung seiner Entscheidungsfähigkeit, was sich in höheren Rückflüssen aus episodischen Belohnungen widerspiegelt. Dieser Aufwärtstrend deutet darauf hin, dass das DPRL-Modell effektiv lernt, seine Strategien im Laufe der Zeit zu optimieren.

#Analyse der heuristischen Methoden

Die Studie untersuchte auch, wie sich verschiedene Initialisierungsmethoden auf die Leistung des Modells auswirkten. Die Verwendung einer zufälligen Auswahl für das Routing führte zu gemischten Ergebnissen. Während es Flexibilität bot, war es auch weniger robust. Im Gegensatz dazu führte ein strukturierterer Ansatz für das Routing zu einer besseren Leistung hinsichtlich verlorener Nachfrage.

#Fazit

Die Einführung der DPRL-Methode bringt eine erhebliche Verbesserung dafür, wie Fahrradverleihsysteme ihre Ressourcen verwalten. Durch die Trennung der Entscheidungen beim Neuausgleich berücksichtigt die Methode die dynamische Natur der Nutzernachfrage effektiver. Das stellt sicher, dass die Nutzer besseren Zugang zu Fahrrädern haben, was letztendlich mehr Menschen ermutigt, Fahrradverleihdienste für ihren täglichen Arbeitsweg zu nutzen.

#Zukünftige Forschungsrichtungen

Es gibt viele Möglichkeiten für weitere Untersuchungen in Bezug auf diese Arbeit. Zukünftige Forschungen könnten die Modelle auf grössere Fahrradverleihnetze skalieren oder sich auf E-Bike-Systeme konzentrieren, die zusätzliche Überlegungen wie das Aufladen erfordern. Es besteht auch Potenzial für die Integration von Echtzeit-Verkehrsdaten und die Entwicklung komplexerer Modelle des Nutzerverhaltens.

Die aus dieser Studie gewonnenen Erkenntnisse könnten auch auf andere Bereiche angewendet werden, die sich mit Echtzeit-Balancierungsproblemen befassen, wie z. B. Mitfahrdienste oder Lieferdienste. Die Prinzipien der Trennung von Bestands- und Routingrichtlinien bieten wertvolle Einblicke in die Optimierung der Ressourcenallokation in verschiedenen Bereichen.