An integer programming approach for the TDTSP-TW with time dependent travel speeds

ISABEL MÉNDEZ-DÍAZ; AGUSTIN MONTERO; JUAN JOSÉ MIRANDA-BRONT

Santiago de Chile

Conferencia; CLAIO 2016; 2016

ALIO

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 consider 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 the travel speeds are modelled as step function of the time and the travel time results in a piecewise linear function. We propose a new ILP formulation and include several families of valid inequalities. In addition, we develop a Branch and Cut algorithm which is evaluated experimentally, showing that the approach is feasible to be applied in practice.