The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading

Authors

  • Dejian Tu Sun Yat-Sen University
  • Songshan Guo Sun Yat-Sen University
  • Hu Qin City University of Hong Kong
  • Wee-Chong Oon City University of Hong Kong
  • Andrew Lim City University of Hong Kong

DOI:

https://doi.org/10.1609/aaai.v24i1.7532

Abstract

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are represented by vertex lists in existing literature. However, when the TSPPD requires that the 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 variable neighbourhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Experiments show that our VNS heuristic is superior to the current best heuristics for TSPPDL in terms of both solution quality and computing time.

Downloads

Published

2010-07-03

How to Cite

Tu, D., Guo, S., Qin, H., Oon, W.-C., & Lim, A. (2010). The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 191-196. https://doi.org/10.1609/aaai.v24i1.7532

Issue

Section

Constraints, Satisfiability, and Search