A Novel Tour Construction Heuristic for Traveling Salesman Problem Using LFF Principle
Sheqin Dong 0, Fan Guo, Jun Yuan, Rensheng Wang, Xianlong Hong
Available Online October 2006.
- https://doi.org/10.2991/jcis.2006.214How to use a DOI?
- Less Flexibility First, Traveling Salesman Problem, Tour Construction Heuristic
- 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.
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 -