A New Three-Level Tree Data Structure for Representing TSP Tours in the Lin-Kernighan Heuristic

Hung Dinh NGUYEN  Ikuo YOSHIHARA  Kunihito YAMAMORI  Moritoshi YASUNAGA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.10   pp.2187-2193
Publication Date: 2007/10/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.10.2187
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and its Applications)
Category: Optimization
traveling salesman problem,  Lin-Kernighan heuristic,  data structure,  three-level trees,  

Full Text: PDF>>
Buy this Article

Lin-Kernighan (LK) is the most powerful local search for the Traveling Salesman Problem (TSP). The choice of data structure for tour representation plays a vital role in LK's performance. Binary trees are asymptotically the best tour representation but they perform empirically best only for TSPs with one million or more cities due to a large overhead. Arrays and two-level trees are used for smaller TSPs. This paper proposes a new three-level tree data structure for tour representation. Although this structure is asymptotically not better than the binary tree structure, it performs empirically better than the conventional structures for TSPs having from a thousand to three million cities.