An integer programming approach for the time-dependent TSP

Article

Authorship

MIRANDA BRONT, JUAN JOSE ; Méndez Díaz, Isabel ; ZABALA, PAULA LORENA

Date

2010

Publishing House and Editing Place

Elsevier

Magazine

Electronic Notes in Discrete Mathematics, vol. 36 (pp. 351-358) Elsevier

Summary Information provided by the agent in SIGEVA

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 travelled. In this paper, we focus on 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 formulations proposed in Picard and Queryanne [8] and Vander Wiel and Sahinidis [10], analyze the relationship betwe... 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 travelled. In this paper, we focus on 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 formulations proposed in Picard and Queryanne [8] and Vander Wiel and Sahinidis [10], analyze the relationship between them and derive some valid inequalities and facets. Computational results are also presented for a Branch and Cut algorithm (B&C)that uses these inequalities, which showed to be very effective.