Many cities around the world are making investments in innovative public transportation infrastructure. Bike-sharing systems (BSS) are one example of this. One key recurring BSS operation problem is the rebalancing of bikes at regular intervals. This redistribution of bikes from full stations to empty stations is required to meet expected demand patterns. Rebalancing entails finding the shortest Hamiltonian cycle in a graph that has the minimal residual. This is an NP-hard problem, and there are a number of algorithms that can be used to find optimal tours, but none are feasible for large instances, since they all grow exponentially. In this paper, we propose a new rebalancing algorithm based on the deferred acceptance algorithm, a well-known game theory algorithm consisting of two phases: tour construction and tour improvement. The proposed algorithm models the rebalancing problem as two disjoint sets of players. Each player in these sets has their own objective function, which is used to build the preference list for players on the other side. Experimental results for the proposed algorithm are promising.
A heuristic for rebalancing bike sharing systems based on a deferred acceptance algorithm
2017-06-01
355965 byte
Conference paper
Electronic Resource
English
Study on Bike Sharing Rebalancing: Evidence from Kunming
ASCE | 2020
|Study on Bike Sharing Rebalancing: Evidence from Kunming
TIBKAT | 2021
|