The bike sharing rebalancing problem: Mathematical formulations and benchmark instances

Mauro Dell’Amico(a), Eleni Hadjicostantinou(b,c), Manuel Iori(a) and Stefano Novellani(a,d)

(a) DISMI, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy.
(b) Business School, Imperial College London, South Kensington Campus, London SW7 2AZ, UK.
(c) School of Engineering, Frederick University, 7 Y. Frederickou Str., 1036 Nicosia, Cyprus.
(d) DEI - "Guglielmo Marconi", University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy.

Abstract

In this paper, we address the Bike sharing Rebalancing Problem (BRP), in which a fleet of capacitated vehicles is employed in order to re-distribute the bikes with the objective of minimizing total cost. This can be viewed as a special one-commodity pickup-and-delivery capacitated vehicle routing problem. We present four mixed integer linear programming formulations of this problem. It is worth noting that the proposed formulations include an exponential number of constraints, hence, tailor-made branch-and-cut algorithms are developed in order to solve them.

The mathematical formulations of the BRP were first computationally tested using data obtained for the city of Reggio Emilia, Italy. Our computational study was then extended to include bike sharing systems from other parts of the world. The information derived from the study was used to build a set of benchmark instances for the BRP which we made publicly available on the web. Extensive experimentation of the branch-and-cut algorithms presented in this paper was carried out and an interesting computational comparison of the proposed mathematical formulations is reported. Finally, several insights on the computational difficulty of the problem are highlighted.

Key words

Bike sharing, Bike repository, Integer programming, Routing, Traveling salesman, Vehicle scheduling

Bibtex entry

@ARTICLE{DHIN14, AUTHOR = "Dell'Amico, M. and Hadjicostantinou, E. and Iori, M., and Novellani, S.", TITLE = The bike sharing rebalancing problem: Mathematical formulations and benchmark instances", JOURNAL = "Omega", YEAR = 2014, VOLUME = 45, PAGES = "7--19"}

To download the related paper click here.

To download the Instances click here.