Balancing bike sharing systems : a hybrid metaheuristic approach for the dynamic case

Abstract

Bike Sharing Systeme wurden in den letzten Jahren zunehmend beliebter um das öffentliche Verkehrsnetz von Städten oder ganzen Regionen zu bereichern. Die meisten Forschungen in dem Gebiet zielten deshalb auf die optimale Positionierung von entsprechenden Stationen ab. Allerdings wurden ebenso unterschiedliche Forschungen zum effizienten Betrieb eines solchen Systems durchgeführt. Die Sinnhaftigkeit eines Bike Sharing Systems ist allerdings nur dann gegeben, wenn es von den Kunden auch genutzt wird. Dies wiederum hängt direkt damit zusammen ob zum gewünschten Zeitpunkt am gewünschten Ort ein Fahrrad bzw. ein Fahrradabstellplatz verfügbar ist. Um dies zu erreichen wird eine Flotte von Fahrzeugen (üblicherweise PKWs mit Anhängern) eingesetzt, um Fahrräder von einer Station zur anderen zu bewegen. Diese Arbeit stellt einen Algorithmus vor, der effiziente Fahrzeugrouten berechnet um solch ein Bike Sharing System auszubalancieren und damit die Kundenzufriedenheit zu erhöhen. Grundsätzlich lässt sich das Problem in einen statischen und einen dynamischen Fall aufteilen. Im statischen Fall befindet sich das System in Ruhe, d.h es finden keine Benutzerinteraktionen statt oder die stattfindenden Benutzerinteraktionen können vernachlässigt werden (zum Beispiel in der Nacht, wenn Fahrradnutzung verboten ist). In dieser Arbeit wird der dynamische Fall betrachtet, in dem das Ausbalancieren während des Systembetriebs stattfindet. Der vorgestellte Algorithmus selbst teilt sich ebenfalls in zwei Teile: Lösungsfindung und Lösungsbewertung. Für die Lösungsfindung werden zwei Varianten einer Variable Neighborhood Search (VNS) mit integrierter Variable Neighborhood Descent (VND) eingesetzt. Beide Varianten verwenden ein identes Set an Nachbarschaften für die VNS, unterscheiden sich allerdings bei den VND Nachbarschaften. Bei der Lösungsbewertung wird ein Linear Programming (LP) Ansatz verfolgt um die optimalen Be- und Entladeanweisungen zu berechnen. Zusätzlich wird ein Greedy Ansatz zur Berechnung dieser Ladeanweisungen vorgestellt. Schließlich wurden die Ergebnisse dreier Varianten (D: vollständiger VND+LP;W: VND(mit lediglich zwei Nachbarschaften)+LP; G: vollständiger VND+Greedy) von drei Testsets mit 60, 90 und 120 Stationen verglichen, um die Effizienz des Algorithmus zu beurteilen. Als eine intiale Beobachtung konnte festgestellt werden, dass die LP Berechnung einen Großteil der CPU Zeit verbraucht. Vergleicht man Variante D und W miteinander entsteht der Eindruck, dass D bessere Ergebnisse liefert. Allerdings konnte kein statistischer Beweis für diese Hypothese gefunden werden. Verglichen mit Variante D und W sind die Ergebnisse von Variante G zwischen 0.5% und 5% schlechter. Allerdings wurden mit der Greedy Berechnung etwa doppelt so viele Lösungen in der gleichen Zeit evaluiert. Für einen Anwendungsfall in der realen Welt ist Variante G wohl am besten geeignet. Obwohl sie keine optimalen Lösungen garantiert, finden sich gute Lösungen relativ schnell.

Bike Sharing Systems became popular in recent years to extend the public transportation network of cities or regions. Most research in this area focuses on finding the optimal locations for bike sharing stations. Still various approaches on how to operate such a system efficiently exist. The usefulness of a bike sharing system strongly depends on the user convenience which is directly connected to the availability of bikes and parking slots when and where they are needed. To increase user convenience a fleet of vehicles (usually cars with a trailer) are used to move bikes between different stations to avoid empty or full stations. The goal of this thesis is to provide an algorithm to efficiently calculate transportation routes for balancing such a bike sharing system to improve user convenience. This problem can be seperated into two different scenarios. The static case focuses on rebalancing the system while there is no user activity or the user activity is negligible (e.g. during night time if users are only allowed to rent bikes during the day time). This thesis is considering the dynamic case, in which the system is still online during the rebalancing process. The proposed algorithm is divided into two parts: solution search and solution evaluation. The first part is implemented using two different variants of a Variable Neighborhood Search (VNS) with an embedded Variable Neighborhood Descent (VND). While the set of neighborhood structures for the VNS variants is equal they differ in the neighborhood structures used for the VND. The solution evaluation part incorporates a Linear Programming (LP) approach to calculate the optimal set of loading instructions for a solution found by the first part. In addition a greedy approach is constructed to calculate a set of loading instructions. Finally three variants (D: complete VND+LP;W: VND(with only two neighborhoods structures used)+LP; G: complete VND+Greedy) are tested on three different sets of test instances with 60, 90 and 120 stations to evaluate the performance of the algorithm. One initial conclusion is that nearly all the given computation time is used to calculate optimal loading instructions with LP. Comparing variant D and W gives the impression that D is performing better although no strong statistical evidence was found. Compared to variant D and W the solutions found by variant G are between 0.5% and 5% worse. On the other hand the greedy approach evaluates about twice as much solutions than the other two methods in the same amount of time. For real world applications the greedy approach may be the better one. Although it is not guaranteed to find the optimal solution it will find good solutions relatively fast.