An integer programming approach for the time-dependent TSP

Artículo

Autoría

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

Fecha

2010

Editorial y Lugar de Edición

Elsevier

Revista

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

Resumen Información suministrada por el agente en 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.

Ver más Ver menos

Palabras Clave

BRANCH AND CUTCOMBINATORIAL OPTIMIZATIONTDTSP

Descargue o solicite el texto completo

http://hdl.handle.net/11336/16566