An effective memetic algorithm for the generalized bike-sharing rebalancing problem. (October 2020)

• Record Type: Journal Article
• Authors: Lu, Yongliang; Benlic, Una; Wu, Qinghua
• Is Part Of: Engineering applications of artificial intelligence. Volume 95(2020)
• Publication Date: 2020-10
• Subjects: Heuristics -- Bike-sharing rebalancing -- Memetic algorithm -- Evolutionary local search; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2020.103890
• Languages: English
• ISSNs: 0952-1976

Abstract

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.