Shortest path problem considering on-time arrival probability

被引:259
作者
Nie, Yu [1 ]
Wu, Xing [1 ]
机构
[1] Northwestern Univ, Dept Civil & Environm Engn, Evanston, IL 60208 USA
关键词
Arriving on-time; A priori shortest path; First-order stochastic dominance; Bellman's principle of optimality; Label-correcting; VARYING TRANSPORTATION; ROUTE GUIDANCE; ALGORITHM;
D O I
10.1016/j.trb.2009.01.008
中图分类号
F [经济];
学科分类号
02 ;
摘要
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. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码:597 / 613
页数:17
相关论文
共 42 条
  • [1] STOCHASTIC SHORTEST PATHS WITH RECOURSE
    ANDREATTA, G
    ROMEO, L
    [J]. NETWORKS, 1988, 18 (03) : 193 - 204
  • [2] [Anonymous], THESIS U TEXAS AUSTI
  • [3] [Anonymous], 1980, Lecture Notes in Economics and Mathematical Systems, DOI DOI 10.1007/978-3-642-48782-8_9
  • [4] Bellman R.E., 1958, Q APPL MATH, V16, P87
  • [5] AN EMPIRICAL-INVESTIGATION OF SOME BICRITERION SHORTEST-PATH ALGORITHMS
    BRUMBAUGHSMITH, J
    SHIER, D
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 43 (02) : 216 - 224
  • [6] GENERALIZED DYNAMIC-PROGRAMMING FOR MULTICRITERIA OPTIMIZATION
    CARRAWAY, RL
    MORIN, TL
    MOSKOWITZ, H
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 44 (01) : 95 - 104
  • [7] Cheung RK, 1998, NAV RES LOG, V45, P769, DOI 10.1002/(SICI)1520-6750(199812)45:8<769::AID-NAV2>3.0.CO
  • [8] 2-#
  • [9] CHEUNG RK, 1998, NAV RES LOG, V25, P729
  • [10] PATH PREFERENCES AND OPTIMAL PATHS IN PROBABILISTIC NETWORKS
    EIGER, A
    MIRCHANDANI, PB
    SOROUSH, H
    [J]. TRANSPORTATION SCIENCE, 1985, 19 (01) : 75 - 84