An effective memetic algorithm for the generalized bike-sharing rebalancing problem. (October 2020) - Lu, Yongliang; Benlic, Una; Wu, Qinghua
Abstract: The generalized bike-sharing rebalancing problem (BRP) entails driving a fleet of capacitated vehicles to rebalance bicycles among bike-sharing system stations at a minimum cost. To solve this NP-hard problem, we present a highly effective memetic algorithm that combines (i) a randomized greedy construction method for initial solution generation, (ii) a route-copy-based crossover operator for solution recombination, and (iii) an effective evolutionary local search for solution improvement integrating an adaptive randomized mutation procedure. Computational experiments on real-world benchmark instances indicate a remarkable performance of the proposed approach with an improvement in the best-known results (new upper bounds) in more than 46% of the cases. In terms of the computational efficiency, the proposed algorithm shows to be nearly two to six times faster when compared to the existing state-of-the-art heuristics. In addition to the generalized BRP, the algorithm can be easily adapted to solve the one-commodity pickup-and-delivery vehicle routing problem with distance constraints, as well as the multi-commodity many-to-many vehicle routing problem with simultaneous pickup and delivery. Highlights: A highly effective memetic algorithm (MA) for the bike-sharing rebalancing problem. MA combines evolutionary local search with a route-copy-based crossover. Improved best upper bounds are reported for 42 medium and large instances. Adaptations of MA are able to provide competitive results for the related 1-PDVRPD and M-M-VRPSPD problems.