کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481999 | 1446168 | 2008 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation](/preview/png/481999.png)
In this paper we deal with an extended version of the Asymmetric Traveling Salesman Problem with Time Windows (ATSPTW) that considers time-dependent travel times and costs, for a more accurate approximation of some routing problems inside large cities, in which the time or cost of traversing certain streets (e.g. main avenues) depends on the moment of the day (for example rush-hours).Unlike other existing papers about time-dependent routing problems, we focus on an exact method for solving this new problem. For this end we first transform the problem into an Asymmetric Generalized TSP and then into a Graphical Asymmetric TSP. In this way, we can apply a known exact algorithm for the Mixed General Routing Problem, which seems to run well with our resulting instances. Computational results are presented on a set of 270 adapted instances from benchmark ATSPTW instances.
Journal: European Journal of Operational Research - Volume 189, Issue 3, 16 September 2008, Pages 789–802