[Back]

A. Pinter:
"Balancing bike sharing systems";
Supervisor: G. Raidl; Institut für Computergraphik and Algorithmen, 2013; final examination: 2013-12.

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.

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.

http://publik.tuwien.ac.at/files/PubDat_224709.pdf