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

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

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

4 Citations (Scopus)

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. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Original language	English
Title of host publication	Proceedings of the National Conference on Artificial Intelligence
Pages	191-196
Volume	1
Publication status	Published - 2010
Event	24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10 - Atlanta, GA, United States Duration: 11 Jul 2010 → 15 Jul 2010

Publication series

Name
Volume	1

Conference

Conference	24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10
Country/Territory	United States
City	Atlanta, GA
Period	11/07/10 → 15/07/10

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{8c4bed12ef13411c80e16ba9cca07923,

title = "The tree representation of feasible solutions for the TSP with pickup and delivery and LIFO loading",

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. Copyright {\textcopyright} 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",

author = "Dejian Tu and Songshan Guo and Hu Qin and Wee-Chong Oon and Andrew Lim",

year = "2010",

language = "English",

isbn = "9781577354642",

volume = "1",

pages = "191--196",

booktitle = "Proceedings of the National Conference on Artificial Intelligence",

note = "24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10 ; Conference date: 11-07-2010 Through 15-07-2010",

}

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. in Proceedings of the National Conference on Artificial Intelligence. vol. 1, pp. 191-196, 24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10, Atlanta, GA, United States, 11/07/10.

The tree representation of feasible solutions for the TSP with pickup and delivery and LIFO loading. / Tu, Dejian; Guo, Songshan; Qin, Hu et al.
Proceedings of the National Conference on Artificial Intelligence. Vol. 1 2010. p. 191-196.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - The tree representation of feasible solutions for the TSP with pickup and delivery and LIFO loading

AU - Tu, Dejian

AU - Guo, Songshan

AU - Qin, Hu

AU - Oon, Wee-Chong

AU - Lim, Andrew

PY - 2010

Y1 - 2010

N2 - 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. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

AB - 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. Copyright © 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

UR - http://www.scopus.com/inward/record.url?scp=77958534088&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-77958534088&origin=recordpage

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781577354642

VL - 1

SP - 191

EP - 196

BT - Proceedings of the National Conference on Artificial Intelligence

T2 - 24th AAAI Conference on Artificial Intelligence and the 22nd Innovative Applications of Artificial Intelligence Conference, AAAI-10 / IAAI-10

Y2 - 11 July 2010 through 15 July 2010

ER -

The tree representation of feasible solutions for the TSP with pickup and delivery and LIFO loading

Abstract

Publication series

Conference

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this