Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

• 成果类型: Article
• 署名作者: Toriello, Alejandro
• 署名单位: University of Southern California
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0631-6
• 发表日期: 2014
• 页码: 247-264
• 关键词: programming approach; algorithm; relaxation

摘要

We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with different basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between cities. We then introduce an exact reformulation that generates a family of successively tighter lower bounds, all solvable in polynomial time. We show that the base member of this family yields a bound greater than or equal to the well-known Held-Karp bound, obtained by solving the linear programming relaxation of the TSP's integer programming arc-based formulation.