An integer programming approach for the time-dependent traveling salesman problem with time windows

Abstract

Congestion in large cities and populated areas is one of the major challenges in urban logistics, andshould be addressed at different planning and operational levels. The Time Dependent Travelling Sales-man Problem (TDTSP) is a generalization of the well known Traveling Salesman Problem (TSP) where thetravel times are not assumed to be constant along the day. The motivation to consider the time dependency factor is that it enables to have better approximations to many problems arising from practice. In this paper, we consider the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSP-TW), where the time dependence is captured by considering variable average travel speeds. We propose an Integer Linear Programming model for the problem and develop an exact algorithm, which is compared on benchmark instances with another approach from the related literature. The results show that the approach is able to solve instances with up to 40 customers.