INVESTIGADORES
MIRANDA BRONT Juan Jose
congresos y reuniones científicas
Título:
A Cut and Branch Algorithm for the Time-Dependent Travelling Salesman Problem
Autor/es:
JUAN JOSÉ MIRANDA BRONT; ISABEL MÉNDEZ-DÍAZ
Lugar:
Buenos Aires
Reunión:
Workshop; VI ALIO/EURO Workshop on Applied Combinatorial Optimization; 2008
Institución organizadora:
Asociación Latino-Iberoamericana de Investigación Operativa y The Association of European Operational Research Societies
Resumen:
The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditionalTSP 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 formulations proposed in Picard and Queyranne (Operations Res. 26(1), 86?110, 1978) and Vander Wiel and Sahinidis (Naval Res. Logist. 43(6), 797?820, 1995), analyze the relationship between them and derive some valid inequalities. Computational results are also presented for a Cut and Branch algorithm that uses these inequalities, which showed to be very effective.
