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.
Original language | English |
---|---|
Article number | 106241 |
Journal | Computers and Industrial Engineering |
Volume | 142 |
DOIs | |
Publication status | Published - Apr 2020 |
Keywords
- Hybrid heuristics
- Learning mechanisms
- Memetic algorithms
- Pickup and delivery problem
- Routing
- Traveling salesman
ASJC Scopus subject areas
- General Computer Science
- General Engineering