Optimization Online


The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm

Hernan Abeledo(abeledo***at***gwu.edu)
Ricardo Fukasawa(rfukasaw***at***math.uwaterloo.ca)
Artur Pessoa(artur***at***producao.uff.br)
Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: 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.

Keywords: polyhedral combinatorics, cutting planes

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: RPEP Vol.10 n.15 (2010) Universidade Federal Fluminense, Brazil

Download: [PDF]

Entry Submitted: 12/30/2010
Entry Accepted: 12/30/2010
Entry Last Modified: 12/30/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society