Including dependence of the costs on time in the traveling salesman problem with time windows

Including dependence of the costs on time in the traveling salesman problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20117214
Volume: 25
Issue: 3
Start Page Number: 209
End Page Number: 216
Publication Date: Sep 2004
Journal: Revista Investigacion Operacional
Authors: , , ,
Keywords: 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.

Reviews

Required fields are marked *. Your email address will not be published.