THE TIME DEPENDENT TRAVELLING SALESMAN PROBLEM WITH TIME WINDOWS

This paper deals with an exact algorithm for the Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW) with continuous piecewise linear cost functions. There are two main research streams that can benefit from efficient exact algorithms for TDTSPTW. The first concerns determining optimal vehicle route planning taking traffic congestion into account explicitly. The latter deals with sequence dependent set-up single machine scheduling problems minimizing total completion times or total tardiness. The contribution of this paper is twofold. First, it is proved that the Asymmetric Traveling Salesman Problem with Time Windows is optimal for the TDTSPTW, if all the arcs share a common congestion pattern. Second, an integer linear programming model is formulated for TDTSPTW, and valid inequalities are then embedded into a branch-and-cut algorithm. Preliminary results show that the proposed algorithm is able to solve instances with up to 67 vertices.