For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2007/10/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Nonlinear Theory and its Applications)
traveling salesman problem, Lin-Kernighan heuristic, data structure, three-level trees,
Full Text: PDF>>
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.