ICC   25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
Integer programming and the TDTSP-TW with time dependent travel speeds
Autor/es:
JUAN JOSÉ MIRANDA-BRONT; ISABEL MÉNDEZ-DÍAZ; AGUSTIN MONTERO
Lugar:
Buenos Aires
Reunión:
Workshop; MIP@AR - Primer workshop argentino de programación entera y combinatoria poliedral; 2016
Institución organizadora:
Departamento de Computación, FCEyN, UBA
Resumen:
Integer programming and the TDTSP-TW with time dependent travel speedsIn the last few years, there has been a trend to enrich classical Vehicle Routing Problems(VRPs) with more general characteristics. Time-Dependent VRPs is the name assigned toa family of VRPs which considers more general travel time functions, aiming to capturethe effects of congested road networks appearing in real-world operations within largecities. One of such problem is the Time-Dependent Traveling Salesman Problem withTime Windows, a generalization of the classical TSPTW where the travel times are notassumed to be constant during the day.In this paper we consider the travel speed model from the literature where they are modeledas step function of the time and, therefore, the travel time results in a piecewise linearfunction. We review some of the exact approaches in the literature and present the detailsof the formulation propsed by Arigliano, Ghiani, Grieco and Guerriero (2015). We discussthe details of the algorithm and its relation with the structure of the problem. Thisdiscussion is supported by preliminary computational results considering the approach byArigliano et al. (2015), aiming to provide some insights regarding the effectiveness ofthe algorithm as well as some possibly directions for future approaches and alternativeformulations for the TDTSPTW.