title: |
A Novel Tour Construction Heuristic for Traveling Salesman Problem Using LFF Principle |
|
publication: |
||
part of series: |
Advances in Intelligent Systems Research | |
ISBN: |
978-90-78677-01-7 | |
ISSN: |
1951-6851 | |
DOI: |
doi:10.2991/jcis.2006.214 (how to use a DOI) | |
author(s): |
Sheqin Dong, Fan Guo, Jun Yuan, Rensheng Wang, Xianlong Hong |
|
corresponding author: |
||
publication date: |
October 2006 |
|
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: |
©
Atlantis Press. This article is distributed under the
terms of the Creative Commons Attribution License, which permits
non-commercial use, distribution and reproduction in any medium,
provided the original work is properly cited. |
|
full text: |