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

详细信息    查看全文

• 作者：Colin Osterman ; César Rego
• 关键词：Algorithms ; Data structures ; Combinatorial optimization ; Ejection chains ; Traveling salesman problem
• 刊名：Annals of Operations Research
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：244
• 期：2
• 页码：583-601
• 全文大小：1,169 KB
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Combinatorics
  Theory of Computation
  
• 出版者：Springer Netherlands
• ISSN：1572-9338
• 卷排序：244

文摘

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.