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

DOI

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.

Copyright

© 2006, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

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
BT  - Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
PB  - Atlantis Press
SP  - 433
EP  - 436
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.214
DO  - 10.2991/jcis.2006.214
ID  - Dong2006/10
ER  -