Most reliable path-finding algorithm for maximizing on-time arrival probability
Most reliable path-finding algorithm for maximizing on-time arrival probability
复制标题
DOI：
10.1080/21680566.2016.1169953
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
B. Chen;Chaoyang Shi;Junlong Zhang;W. Lam;Qingquan Li;Shujin Xiang
中科院分区：
文献类型：
--
作者：
B. Chen;Chaoyang Shi;Junlong Zhang;W. Lam;Qingquan Li;Shujin Xiang
摘要寻找最可靠的路径，最大限度地提高准时到达的概率是经常遇到的旅行者面临的旅行时间的不确定性。然而，在文献中已经提出了一些精确的解决方案，以有效地确定在大规模的道路网络中的最可靠的路径。在本研究中，我们提出一个两阶段求解演算法来精确求解最可靠路径问题。在第一阶段，估计准时到达概率的上界和下界。建立了最可靠路问题的优势条件和单调性。在第二阶段，多准则标签设置方法被用来有效地确定最可靠的路径。为了说明所提出的解决方案的算法的适用性，进行了全面的案例研究，使用真实的道路网络的随机行程时间。算例结果表明，该求解算法与现有的多准则标签校正算法相比，具有显著的计算优势。
ABSTRACT Finding the most reliable path that maximizes the probability of on-time arrival is commonly encountered by travelers facing travel time uncertainties. However, few exact solution algorithms have been proposed in the literature to efficiently determine the most reliable path in large-scale road networks. In this study, a two-stage solution algorithm is proposed to exactly solve the most reliable path problem. In the first stage, the upper and lower bounds of on-time arrival probability are estimated. Dominance conditions and the monotonic property of the most reliable path problem are then established. In the second stage, the multi-criteria label-setting approach is utilized to efficiently determine the most reliable path. To illustrate the applicability of the proposed solution algorithm, a comprehensive case study is carried out using a real road network with stochastic travel times. The results of case study show that the proposed solution algorithm has a remarkable computational advantage over the existing multi-criteria label-correcting algorithm.