naa a22 4500 510809022 CHVBK 20180411083432.0 cr unu---uuuuu 180411e20130301xx s 000 0 eng 10.1007/s12532-012-0047-y doi (NATIONALLICENCE)springer-10.1007/s12532-012-0047-y The time dependent traveling salesman problem: polyhedra and algorithm [Elektronische Daten] [Hernán Abeledo, Ricardo Fukasawa, Artur Pessoa, Eduardo Uchoa] 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. Springer and Mathematical Optimization Society, 2012 Integer programming nationallicence Polyhedral combinatorics nationallicence Cutting planes nationallicence Branch-price-and-cut nationallicence Time dependent traveling salesman nationallicence Abeledo Hernán Department of Engineering Management and Systems Engineering, The George Washington University, Washington, DC, USA aut Fukasawa Ricardo Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada aut Pessoa Artur Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, RJ, Brazil aut Uchoa Eduardo Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, RJ, Brazil aut Mathematical Programming Computation Springer-Verlag 5/1(2013-03-01), 27-55 1867-2949 5:1<27 2013 5 12532 https://doi.org/10.1007/s12532-012-0047-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s12532-012-0047-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Abeledo Hernán Department of Engineering Management and Systems Engineering, The George Washington University, Washington, DC, USA aut NATIONALLICENCE 700 1- Fukasawa Ricardo Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada aut NATIONALLICENCE 700 1- Pessoa Artur Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, RJ, Brazil aut NATIONALLICENCE 700 1- Uchoa Eduardo Departamento de Engenharia de Produção, Universidade Federal Fluminense, Niterói, RJ, Brazil aut NATIONALLICENCE 773 0- Mathematical Programming Computation Springer-Verlag 5/1(2013-03-01), 27-55 1867-2949 5:1<27 2013 5 12532 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer