INCLUDING DEPENDENCE OF THE COSTS ON TIME IN THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS(

Abstract

We present in this paper a generalization of the Traveling Salesman Problem with Time Windows (TSPTW) in which arc costs depend on the period of time in which the cycle starts to traverse the arcs. This new problem fits more accurately some real routing problems in big cities than the TSPTW, because the time, and then the cost, of traversing certain avenues depends on the instant we start to do it. For instance, at peak hours this time is bigger than in other moment of the day. We prove that this new problem can be transformed in pseudo-polynomial time into an Asymmetric Generalized Traveling Salesman Problem and then, into an Asymmetric Traveling Salesman Problem. Thus, we can solve the problem with known techniques. We also present computational results on this transformation in a set of 140 instances with up to 30 vertices with an exact algorithm. We consider our results satisfactory
according to the complexity of the new problem.