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

摘要

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.