A Learning-based Memetic Algorithm for the Multiple Vehicle Pickup and Delivery Problem with LIFO Loading

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.