An effective memetic algorithm for the generalized bike-sharing rebalancing problem

摘要

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 (ⅰ) a randomized greedy construction method for initial solution generation, (ⅱ) a route-copy-based crossover operator for solution recombination, and (ⅲ) 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.