A learning-based memetic algorithm for the multiple vehicle pickup and delivery problem with LIFO loading

Bo Peng, Yuan Zhang, Zhipeng Lü, T. C.E. Cheng, Fred Glover

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

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 languageEnglish
Article number106241
JournalComputers and Industrial Engineering
Volume142
DOIs
Publication statusPublished - Apr 2020

Keywords

  • Hybrid heuristics
  • Learning mechanisms
  • Memetic algorithms
  • Pickup and delivery problem
  • Routing
  • Traveling salesman

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this