In this paper, we deal with the Bike sharing Rebalancing Problem (BRP), which is the problem of driving a fleet of capacitated vehicles to redistribute bicycles among the stations of a bike sharing system. We tackle the BRP with a destroy and repair metaheuristic algorithm, which makes use of a new effective constructive heuristic and of several local search procedures. The computational effort required for the neighborhood explorations is reduced by means of a set of techniques based on the properties of feasible BRP solutions. In addition, the algorithm is adapted to solve the one-commodity Pickup and Delivery Vehicle Routing Problem with maximum Duration (1-PDVRPD), which is the variant of the BRP in which a maximum duration is imposed on each route. Extensive computational results on instances from the literature and on newly-collected large-size real-world instances are provided. Our destroy and repair algorithm compares very well with respect to an exact branch-and-cut algorithm and a previous metaheuristic algorithm in the literature. It improves several best-known solutions, providing high quality results on both problem variants.

A destroy and repair algorithm for the Bike sharing Rebalancing Problem / Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Stützle, Thomas. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 71:(2016), pp. 149-162. [10.1016/j.cor.2016.01.011]

A destroy and repair algorithm for the Bike sharing Rebalancing Problem

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

Abstract

In this paper, we deal with the Bike sharing Rebalancing Problem (BRP), which is the problem of driving a fleet of capacitated vehicles to redistribute bicycles among the stations of a bike sharing system. We tackle the BRP with a destroy and repair metaheuristic algorithm, which makes use of a new effective constructive heuristic and of several local search procedures. The computational effort required for the neighborhood explorations is reduced by means of a set of techniques based on the properties of feasible BRP solutions. In addition, the algorithm is adapted to solve the one-commodity Pickup and Delivery Vehicle Routing Problem with maximum Duration (1-PDVRPD), which is the variant of the BRP in which a maximum duration is imposed on each route. Extensive computational results on instances from the literature and on newly-collected large-size real-world instances are provided. Our destroy and repair algorithm compares very well with respect to an exact branch-and-cut algorithm and a previous metaheuristic algorithm in the literature. It improves several best-known solutions, providing high quality results on both problem variants.
2016
71
149
162
A destroy and repair algorithm for the Bike sharing Rebalancing Problem / Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Stützle, Thomas. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - STAMPA. - 71:(2016), pp. 149-162. [10.1016/j.cor.2016.01.011]
Dell'Amico, Mauro; Iori, Manuel; Novellani, Stefano; Stützle, Thomas
File in questo prodotto:
File Dimensione Formato  
VOR_DellAmico-Iori-Novellani-Stuetzle-CandOR-2016.pdf

Open access

Descrizione: Articolo principale
Tipologia: Versione pubblicata dall'editore
Dimensione 388.27 kB
Formato Adobe PDF
388.27 kB 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/1102691
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 129
  • ???jsp.display-item.citation.isi??? 109
social impact