The time dependent traveling salesman problem: polyhedra and algorithm

  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, Eduardo Uchoa
DOI:https://doi.org/10.1007/s12532-012-0047-y
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2012
Tag:Software; Theoretical Computer Science
Volume:5
Issue:1
Page Number:29
First Page:27
Last Page:55
Mathematical Programming Computation :MPC 2013 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.