A destroy and repair algorithm for the Bike sharing Rebalancing Problem

Mauro Dell'Amico, Manuel Iori, Stefano Novellani, Thomas Stützle

Research output: Contribution to journalArticlepeer-review

118 Scopus citations

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.

Original languageEnglish
Pages (from-to)149-162
Number of pages14
JournalComputers and Operations Research
Volume71
DOIs
StatePublished - 1 Jul 2016
Externally publishedYes

Keywords

  • Bike sharing
  • Branch-and-cut
  • Destroy and repair
  • Rebalancing
  • Speed-up techniques

Fingerprint

Dive into the research topics of 'A destroy and repair algorithm for the Bike sharing Rebalancing Problem'. Together they form a unique fingerprint.

Cite this