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

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming computation 2013-03, Vol.5 (1), p.27-55
Main Authors: Abeledo, Hernán, Fukasawa, Ricardo, Pessoa, Artur, Uchoa, Eduardo
Format: Article
Language:English
Subjects:
Full Length Paper
Mathematics
Mathematics and Statistics
Mathematics of Computing
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1867-2949
1867-2957
DOI:10.1007/s12532-012-0047-y