AAAI Publications, Twenty-Fourth AAAI Conference on Artificial Intelligence

Font Size: 
The Tree Representation of Feasible Solutions for the TSP with Pickup and Delivery and LIFO Loading
Dejian Tu, Songshan Guo, Hu Qin, Wee-Chong Oon, Andrew Lim

Last modified: 2010-07-03


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.

Full Text: PDF