A Destroy and Repair Algorithm for the Bike sharing Rebalancing Problem

Mauro Dell’Amico(a), Manuel Iori(a), Stefano Novellani(a,b) and Thomas Stuetzle(c)

(a) DISMI, University of Modena and Reggio Emilia, Via Amendola 2, 42122 Reggio Emilia, Italy.
(b) DEI - "Guglielmo Marconi", University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy.
(c) IRIDIA, Université Libre de Bruxelles, 50, Av. F. Roosevelt, CP 194/6 B-1050 Brussels, Belgium.

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, 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.

Key words

bike sharing, rebalancing, destroy and repair, speed-up techniques, branch-and-cut

 

Bibtex entry

@ARTICLE{DINS16, AUTHOR = "Dell'Amico, M. and Iori, M. and Novellani, S. and St\"utzle, T.", TITLE = A Destroy and Repair Algorithm for the Bike sharing Rebalancing Problem", JOURNAL = "Computers \& Operations Research", YEAR = 2016, VOLUME = 71, PAGES = "149--162" ISSN = "0305-0548", DOI = "http://dx.doi.org/10.1016/j.cor.2016.01.011", URL = "http://www.sciencedirect.com/science/article/pii/S0305054816300016", }

 

To download the related paper click here.

To download the instances click here.