A k-level data structure for large-scale traveling salesman problems

The problem of data representation is fundamental to the efficiency of search algorithms for the traveling salesman problem (TSP). The computational effort required to perform such tour operations as traversal and subpath reversal considerably influence algorithm design and performance. We propose a new data structure–the k‐level satellite tree–for representing a TSP tour with a discussion of properties in the framework of general tour operations. The k‐level satellite tree representation is shown to be significantly more efficient than its predecessors for large‐scale instances.