Shortest path problem considering on-time arrival probability Export

@article{yu_wu_2009, abstract = {This paper studies the problem of finding a priori shortest paths to guarantee a given likelihood of arriving on-time in a stochastic network. Such ” reliable” paths help travelers better plan their trips to prepare for the risk of running late in the face of stochastic travel times. Optimal solutions to the problem can be obtained from local-reliable paths, which are a set of non-dominated paths under first-order stochastic dominance. We show that Bellman's principle of optimality can be applied to construct local-reliable paths. Acyclicity of local-reliable paths is established and used for proving finite convergence of solution procedures. The connection between the a priori path problem and the corresponding adaptive routing problem is also revealed. A label-correcting algorithm is proposed and its complexity is analyzed. A pseudo-polynomial approximation is proposed based on extreme-dominance. An extension that allows travel time distribution functions to vary over time is also discussed. We show that the time-dependent problem is decomposable with respect to arrival times and therefore can be solved as easily as its static counterpart. Numerical results are provided using typical transportation networks.}, author = {Nie, Yu M. and Wu, Xing}, citeulike-article-id = {6037492}, day = {12}, issn = {01912615}, journal = {Transportation Research Part B: Methodological}, keywords = {reliability, shortestpath, stochastic}, month = {March}, posted-at = {2009-10-29 21:53:14}, priority = {2}, title = {Shortest path problem considering on-time arrival probability}, year = {2009} }

TY - JOUR ID - yu_wu_2009 L3 - citeulike-article-id:6037492 N2 - This paper studies the problem of finding a priori shortest paths to guarantee a given likelihood of arriving on-time in a stochastic network. Such “reliable” paths help travelers better plan their trips to prepare for the risk of running late in the face of stochastic travel times. Optimal solutions to the problem can be obtained from local-reliable paths, which are a set of non-dominated paths under first-order stochastic dominance. We show that Bellman’s principle of optimality can be applied to construct local-reliable paths. Acyclicity of local-reliable paths is established and used for proving finite convergence of solution procedures. The connection between the a priori path problem and the corresponding adaptive routing problem is also revealed. A label-correcting algorithm is proposed and its complexity is analyzed. A pseudo-polynomial approximation is proposed based on extreme-dominance. An extension that allows travel time distribution functions to vary over time is also discussed. We show that the time-dependent problem is decomposable with respect to arrival times and therefore can be solved as easily as its static counterpart. Numerical results are provided using typical transportation networks. JF - Transportation Research Part B: Methodological SN - 01912615 TI - Shortest path problem considering on-time arrival probability KW - reliability KW - shortestpath KW - stochastic AU - Nie, Yu AU - Wu, Xing PY - 2009/03/12/ ER -