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 behaviour 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.

The Bike Sharing Rebalancing Problem: Mathematical formulations and benchmark instances / Dell'Amico, Mauro; Eleni, Hadjiconstantinou; Iori, Manuel; Novellani, Stefano. - In: OMEGA. - ISSN 0305-0483. - STAMPA. - 45:(2014), pp. 7-19. [10.1016/j.omega.2013.12.001]

The Bike Sharing Rebalancing Problem: Mathematical formulations and benchmark instances

DELL'AMICO, Mauro;IORI, MANUEL;NOVELLANI, STEFANO
2014

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 behaviour 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.
45
7
19
The Bike Sharing Rebalancing Problem: Mathematical formulations and benchmark instances / Dell'Amico, Mauro; Eleni, Hadjiconstantinou; Iori, Manuel; Novellani, Stefano. - In: OMEGA. - ISSN 0305-0483. - STAMPA. - 45:(2014), pp. 7-19. [10.1016/j.omega.2013.12.001]
Dell'Amico, Mauro; Eleni, Hadjiconstantinou; Iori, Manuel; Novellani, Stefano
File in questo prodotto:
File Dimensione Formato  
Bikes-Omega-Appeared.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 1.39 MB
Formato Adobe PDF
1.39 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/989310
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 207
  • ???jsp.display-item.citation.isi??? 184
social impact