In order to meet the users' demand, bike sharing systems must be regularly rebalanced. The problem of balancing bike sharing systems (BBSS) is concerned with designing optimal tours and operating instructions for relocating bikes among stations to maximally comply with the expected future bike demands. In this paper, we tackle the BBSS by means of Constraint Programming: first, we introduce two novel constraint models for the BBSS including a smart branching strategy that focusses on the most promising routes. Second, in order to speed-up the search process, we incorporate both models in a Large Neighborhood Search (LNS) approach that is adapted to the respective CP model. Third, we perform a computational evaluation on instances based on real-world data, where we see that the LNS approach outperforms the Branch & Bound approach and is competitive with other existing approaches.

Constraint-Based Approaches for Balancing Bike Sharing Systems

DI GASPERO, Luca;URLI, Tommaso
2013-01-01

Abstract

In order to meet the users' demand, bike sharing systems must be regularly rebalanced. The problem of balancing bike sharing systems (BBSS) is concerned with designing optimal tours and operating instructions for relocating bikes among stations to maximally comply with the expected future bike demands. In this paper, we tackle the BBSS by means of Constraint Programming: first, we introduce two novel constraint models for the BBSS including a smart branching strategy that focusses on the most promising routes. Second, in order to speed-up the search process, we incorporate both models in a Large Neighborhood Search (LNS) approach that is adapted to the respective CP model. Third, we perform a computational evaluation on instances based on real-world data, where we see that the LNS approach outperforms the Branch & Bound approach and is competitive with other existing approaches.
2013
9783642406263
9783642406270
File in questo prodotto:
File Dimensione Formato  
cp2013.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 615.56 kB
Formato Adobe PDF
615.56 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/873853
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? 39
social impact