Balancing a dynamic public bike-sharing system

Contardo, Claudio, Catherine Morency, and Louis-Martin Rousseau

CIRRELT 2012

https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2012-09.pdf

Used by the Quanticol project

In this paper, a set of mathematical formulations and solution methodologies are provided for a dynamic public bike-sharing balancing problem arising from the daily operations. They first propose an arc-flow formulation on a space-time network. In their space-time network, the time horizon is discrete into indexed short periods, each node on the network represents the state of a station at time t: S(v,t), where v is the station id, t is the time index. The arcs indicate vehicles’ direct trips between a pair of states or the action of waiting at a station for a period. The goal of the arc-flow formulation is to minimize the value of the total shortage and excess of bikes at all states in the space-time network. As a solution of the arc-flow formulation may not be feasible, they further introduced a heuristic procedure based on the solution of two different decompositions(Dantzig-Wolfe decomposition and Benders decomposition) of the problem. They first apply Dantzig-Wolfe decomposition to the arc-flow formulation which allows them to obtain a lower bound of the problem. Then, they apply Benders decomposition to another reformulation of the problem and use the information provided by the first solution so as to obtain an upper bound of the problem. In their experiments, we test their algorithm in the setting of different number of stations and time periods, and different topology of stations(clustered, randomly distributed). It shows that their method can provide solution in reasonable time in different settings.