کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481045 | 1446027 | 2014 | 12 صفحه PDF | دانلود رایگان |
• We consider networks where travel times are both stochastic and time-dependent.
• We consider the NP-hard problem where an o–d path must be chosen a priori.
• Our algorithm can easily be extended to the ranking of the first K shortest paths.
• The algorithm uses the time-adaptive solution as a relaxation of the a priori problem.
• Our solution methods are effective and robust under realistic test instances.
In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin–destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem.In this paper, we propose a solution method for the a priori shortest path problem, and we show that it can be easily extended to the ranking of the first K shortest paths. Our method exploits the solution of the time-adaptive routing problem as a relaxation of the a priori problem. Computational results are presented showing that, under realistic distributions of travel times and costs, our solution methods are effective and robust.
Journal: European Journal of Operational Research - Volume 236, Issue 3, 1 August 2014, Pages 903–914