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

作者：Osterman Colin; Rego Cesar^*

来源：Annals of Operations Research, 2016, 244(2): 583-601.

DOI：10.1007/s10479-016-2159-7

• Algorithms
• Data structures
• Combinatorial optimization
• Ejection chains
• Traveling salesman problem

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.

• 出版日期2016-9