Ranking paths in stochastic time-dependent networks
Ranking paths in stochastic time-dependent networks
复制标题
DOI：
10.1016/j.ejor.2013.10.022
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
L. Nielsen;K. A. Andersen;D. Pretolani
中科院分区：
文献类型：
--
作者：
L. Nielsen;K. A. Andersen;D. Pretolani
在本文中，我们解决最优路由问题的网络中的旅行时间是随机的和时间依赖的。在这些网络中，最佳路由选择不一定是路径，而是时间自适应策略，该策略根据时间为节点分配后继节点。然而，在某些特定情况下，必须先验地选择起点-目的地路径，因为不允许时间自适应选择。不幸的是，寻找先验最短路径是一个NP-难问题.本文提出了一种解决先验最短路径问题的方法，并证明了它可以很容易地推广到前K条最短路径的排序.我们的方法利用时间自适应路由问题的解决方案作为先验问题的松弛。计算结果表明，根据现实的旅行时间和成本的分布，我们的解决方案是有效的和强大的。
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 atime-adaptive strategythat 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 thea priorishortest 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 firstKshortest 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.