Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)

A Novel Tour Construction Heuristic for Traveling Salesman Problem Using LFF Principle

Authors
Sheqin Dong 0, Fan Guo, Jun Yuan, Rensheng Wang, Xianlong Hong
Corresponding Author
Sheqin Dong
0Tsinghua University
Available Online October 2006.
DOI
https://doi.org/10.2991/jcis.2006.214How to use a DOI?
Keywords
Less Flexibility First, Traveling Salesman Problem, Tour Construction Heuristic
Abstract
Less Flexibility First(LFF) principle is inspired and developed by enhancing some rule-of-thumb guidelines resulting from the generation-long work experience of human professionals in ancient days. In this paper, we generalize this principle to the classical Traveling Salesman Problem and propose a tour construction heuristic. Our new heuristic is closely related to Cheapest Insertion, a well-known heuristic for TSP. Then we prove that our algorithm can be implemented to run in O(n4) time, achieving a tour no worse than Convex Hull, Cheapest Insertion (CHCI). Experimental results are comparable to simple local search heuristics such as 3-opt and baseline simulated annealing and better than any conventional tour construction heuristic at the expense of increased running time.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
Part of series
Advances in Intelligent Systems Research
Publication Date
October 2006
ISBN
978-90-78677-01-7
ISSN
1951-6851
DOI
https://doi.org/10.2991/jcis.2006.214How to use a DOI?
Open Access
This is an open access article distributed under the CC BY-NC license.

Cite this article

TY  - CONF
AU  - Sheqin Dong
AU  - Fan Guo
AU  - Jun Yuan
AU  - Rensheng Wang
AU  - Xianlong Hong
PY  - 2006/10
DA  - 2006/10
TI  - A Novel Tour Construction Heuristic for Traveling Salesman Problem Using LFF Principle
PB  - Atlantis Press
SP  - 433
EP  - 436
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.214
DO  - https://doi.org/10.2991/jcis.2006.214
ID  - Dong2006/10
ER  -