The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station must be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.

A heuristic algorithm for a single vehicle static bike sharing rebalancing problem / Cruz, Fábio; Subramanian, Anand; Bruck, Bruno P.; Iori, Manuel. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 79:(2017), pp. 19-33. [10.1016/j.cor.2016.09.025]

A heuristic algorithm for a single vehicle static bike sharing rebalancing problem

IORI, MANUEL
2017

Abstract

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station must be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.
2017
1-ott-2016
79
19
33
A heuristic algorithm for a single vehicle static bike sharing rebalancing problem / Cruz, Fábio; Subramanian, Anand; Bruck, Bruno P.; Iori, Manuel. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 79:(2017), pp. 19-33. [10.1016/j.cor.2016.09.025]
Cruz, Fábio; Subramanian, Anand; Bruck, Bruno P.; Iori, Manuel
File in questo prodotto:
File Dimensione Formato  
A heuristic algorithm for a single vehicle static bike sharing rebalancing problem.pdf

Accesso riservato

Descrizione: Articolo principale
Tipologia: Versione pubblicata dall'editore
Dimensione 1.5 MB
Formato Adobe PDF
1.5 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Preprint-on-Arxiv.pdf

Open access

Descrizione: versione pre-print
Tipologia: Versione originale dell'autore proposta per la pubblicazione
Dimensione 844.1 kB
Formato Adobe PDF
844.1 kB Adobe PDF Visualizza/Apri
POST_j.cor.2016.09.025.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 1.06 MB
Formato Adobe PDF
1.06 MB Adobe PDF Visualizza/Apri
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/1110922
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 107
  • ???jsp.display-item.citation.isi??? 98
social impact