Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

34 Scopus Citations
View graph of relations


  • Brenda Cheang
  • Xiang Gao
  • Andrew Lim
  • Hu Qin
  • Wenbin Zhu

Related Research Unit(s)


Original languageEnglish
Pages (from-to)60-75
Journal / PublicationEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 16 Nov 2012


We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem. © 2012 Elsevier B.V. All rights reserved.

Research Area(s)

  • Distance constraint, Last-in-first-out loading, Metaheuristic, Pickup and delivery, Traveling salesman

Citation Format(s)