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
;
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
DELL'AMICO, Mauro; IORI, MANUEL; NOVELLANI, STEFANO; Stützle, Thomas
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/896926
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 107
  • ???jsp.display-item.citation.isi??? 92
social impact