首页    期刊浏览 2024年12月06日 星期五
登录注册

文章基本信息

  • 标题:The time dependent traveling salesman problem: polyhedra and algorithm
  • 其他标题:The time dependent traveling salesman problem: polyhedra and algorithm
  • 作者:Abeledo, Hernán ; Fukasawa, Ricardo ; Pessoa, Artur
  • 期刊名称:Mathematical Programming Computation
  • 印刷版ISSN:1867-2957
  • 出版年度:2013
  • 页码:27-55
  • DOI:10.1007/mpc.v0i0.102
  • 语种:English
  • 出版社:Mathematical Programming Computation
  • 摘要:The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP.We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts.We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.
  • 关键词:90C11; 90C27; 90C57
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有