A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with LIFO loading. (April 2020)

• Record Type: Journal Article
• Authors: Peng, Bo; Zhang, Yuan; Lü, Zhipeng; Cheng, T.C.E.; Glover, Fred
• Is Part Of: Computers & industrial engineering. Volume 142(2020)
• Publication Date: 2020-04
• Subjects: Pickup and delivery problem -- Routing -- Traveling salesman -- Memetic algorithms -- Hybrid heuristics -- Learning mechanisms; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.106241
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A learning-based memetic algorithm for multiple vehicle pickup and delivery problem. A reward and punishment mechanism to manage multiple neighborhood moves. A longest common subsequence-based strategy for updating the population. Previous best known results are improved for 132 out of 158 public instances. Analysis shows the importance of several key components in the algorithm. Abstract: The multiple vehicle pickup and delivery problem is a generalization of the traveling salesman problem that has many important applications in supply chain logistics. One of the most prominent variants requires the route durations and the capacity of each vehicle to lie within given limits, while performing the loading and unloading operations by a last-in-first-out (LIFO) protocol. We propose a learning-based memetic algorithm to solve this problem that incorporates a hybrid initial solution construction method, a learning-based local search procedure, an effective component-based crossover operator utilizing the concept of structured combinations, and a longest-common-subsequence-based population updating strategy. Experimental results show that our approach is highly effective in terms of both computational efficiency and solution quality in comparison with the current state-of-the-art, improving the previous best-known results for 132 out of 158 problem instances, while matching the best-known results for all but three of the remaining instances.