The bike sharing rebalancing problem: Mathematical formulations and benchmark instances |
| |
| Affiliation: | 1. School of Management, University of Bath, East Building, BA2 7AY, UK;2. School of Mathematics, University of Southampton, Highfield, Southampton, SO17 1BJ, UK;3. LIPN, CNRS (UMR7030), Université Paris, 13, Sorbonne Paris Citè, 99 av. J-B Clement, 93430 Villetaneuse, France;1. Instituto de Computação, Universidade Federal Fluminense, Rua Passo da Pátria 156, São Domingos, 24210-240 Niterói, RJ, Brazil;2. Departamento de Sistemas de Computação, Centro de Informática, Universidade Federal da Paraíba, Rua dos Escoteiros, Mangabeira, 58058-600 João Pessoa, PB, Brazil;3. School of Management, University of Bath, Bath BA2 7AY, UK;4. Canada Research Chair in Distribution Management, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montreal H3T 2A7, Canada;1. School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China;2. The University of Hong Kong Shenzhen Institute of Research and Innovation, Shenzhen, China;3. Department of Civil Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong;4. School of Automation and Transportation Engineering, Hefei University of Technology, Hefei 230009, China;1. Department of Economics and Business Economics, Aarhus University, Denmark;2. The University of Hong Kong Shenzhen Institute of Research and Innovation, Shenzhen, China;3. Department of Civil Engineering, The University of Hong Kong, Hong Kong |
| |
| Abstract: | Bike sharing systems offer a mobility service whereby public bicycles, located at different stations across an urban area, are available for shared use. These systems contribute towards obtaining a more sustainable mobility and decreasing traffic and pollution caused by car transportation. Since the first bike sharing system was installed in Amsterdam in 1965, the number of such applications has increased remarkably so that hundreds of systems are now operating all over the world.In a bike sharing system, users can take a bicycle from a station, use it to perform a journey and then leave it at a station, not necessarily the same one of departure. This behavior typically leads to a situation in which some stations become full and others are empty. Hence, a balanced system requires the redistribution of bicycles among stations.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. |
| |
| Keywords: | Integer programming Routing Traveling salesman Vehicle scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
