The tree representation for the pickup and delivery traveling salesman problem with LIFO loading

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

19 Scopus Citations
View graph of relations

Author(s)

  • Yongquan Li
  • Andrew Lim
  • Wee-Chong Oon
  • Hu Qin
  • Dejian Tu

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)482-496
Journal / PublicationEuropean Journal of Operational Research
Volume212
Issue number3
Publication statusPublished - 1 Aug 2011

Abstract

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases. © 2010 Elsevier B.V. All rights reserved.

Research Area(s)

  • Last-in-first-out loading, Pickup and delivery, Traveling salesman, Tree data structure, Variable neighborhood search

Citation Format(s)

The tree representation for the pickup and delivery traveling salesman problem with LIFO loading. / Li, Yongquan; Lim, Andrew; Oon, Wee-Chong; Qin, Hu; Tu, Dejian.

In: European Journal of Operational Research, Vol. 212, No. 3, 01.08.2011, p. 482-496.

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