Integer programming and the TDTSP-TW with time dependent travel speeds

AGUSTÍN ISMAEL MONTERO; ISABEL MÉNDEZ-DÍAZ; JUAN JOSÉ MIRANDA BRONT

Ciudad Autonoma de Buenos Aires

Workshop; MIP@AR 2016; 2016

Departamento de Computación, FCEyN, UBA

In 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 to a family of VRPs which considers more general travel time functions, aiming to capture the effects of congested road networks appearing in real-world operations within large cities. One of such problem is the Time-Dependent Traveling Salesman Problem with Time Windows, a generalization of the classical TSPTW where the travel times are not assumed to be constant during the day.In this paper we consider the travel speed model from the literature where they are modeled as step function of the time and, therefore, the travel time results in a piecewise linear function. We review some of the exact approaches in the literature and present the details of the formulation propsed by Arigliano, Ghiani, Grieco and Guerriero (2015). We discuss the details of the algorithm and its relation with the structure of the problem. This discussion is supported by preliminary computational results considering the approach by Arigliano et al. (2015), aiming to provide some insights regarding the effectiveness of the algorithm as well as some possibly directions for future approaches and alternative formulations for the TDTSPTW.