A destroy and repair algorithm for the Bike sharing Rebalancing Problem

• We present a new metaheuristic algorithm for BRP and 1-PDVRPD.
• We introduce new properties and speed-up techniques for local search operators.
• We present a new Savings based heuristic for BRP and 1-PDVRPD.
• We present a new time-packing inequality to be used in a B&C for 1-PDVRPD.
• Strong results improvement and new optima for BRP and 1-PDVRPD have been obtained.

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.