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

Authors: Albiach, J.; Sanchis, J.M.; Soler, D.

European Journal of Operational Research - 2008 Volume 189, Pages 789-802

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. © 2006 Elsevier B.V. All rights reserved.

https://doi.org/10.1016/j.ejor.2006.09.099

Cite as:

@article{Albiach_2008,
	doi = {10.1016/j.ejor.2006.09.099},
	url = {https://doi.org/10.1016%2Fj.ejor.2006.09.099},
	year = 2008,
	month = {sep},
	publisher = {Elsevier {BV}},
	volume = {189},
	number = {3},
	pages = {789--802},
	author = {Jos{'{e}} Albiach and Jos{'{e}} Mar{'{i}}a Sanchis and David Soler},
	title = {An asymmetric {TSP} with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation},
	journal = {European Journal of Operational Research}
}



    Leave a Reply

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

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close