An Integer Programming Approach for the Time Dependent Travelling Saleman Problem

ISABEL MÉNDEZ-DÍAZ; JUAN MIRANDA BRONT; PAULA ZABALA

Bonn, Alemania

Conferencia; 23rd European Conference on Operational Research; 2009

Association of European Operational Research Societies

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is taken. In this paper, we focus in the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider the formulation proposed in Picard and Queyranne (1978) and derive some valid inequalities. We also present computational results for a Branch and Cut algorithm that incorporates these inequalities.