Solution techniques are studied for the problem of finding a priori paths that are shortest to ensure a specified probability of on-time arrival in a stochastic network. A new discretization scheme called α-discrete is proposed. The scheme is well suited to large-scale applications because it does not depend on problem-specific parameters. A procedure for evaluating convolution integrals based on the new scheme is given, and its complexity is analyzed. Other implementation strategies also are discussed to improve the computational performance of the exact yet nondeterministic polynomial label-correcting algorithm. These include an approximate method based on extreme dominance and two cycle-avoidance strategies. Comprehensive numerical experiments are conducted to test the effects of the proposed implementation strategies using different networks and different distribution types.
Get full access to this article
View all access options for this article.
References
1.
HallR. W.The Fastest Path Through a Network with Random Time-Dependent Travel Time. Transportation Science, Vol. 20, 1986, pp. 182–188.
2.
AndreattaG. and RomeoL.Stochastic Shortest Paths with Recourse. Networks, Vol. 18, 1988, pp. 193–204.
3.
PolychronopoulosG. H. and TsitsiklisJ. N.Stochastic Shortest Path Problems with Recourse. Networks, Vol. 27, 1996, pp. 133–143.
4.
CheungR. K.Iterative Methods for Dynamic Stochastic Shortest Path Problems. Naval Research Logistics, Vol. 45, 1998, pp. 769–789.
5.
FuL. and RilettL. R.Expected Shortest Paths in Dynamic and Stochastic Traffic Networks. Transportation Research, Part B, Vol. 32, No. 71998, pp. 499–516.
6.
FuL.An Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information. Transportation Research, Part B, Vol. 35, No. 82001, pp. 749–765.
7.
Miller-HooksE. D. and MahmassaniH. S.Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks. Transportation Science, Vol. 34, 2000, pp. 198–215.
8.
Miller-HooksE. D.Adaptive Least-Expected Time Paths in Stochastic, Time-Varying Transportation and Data Networks. Networks, Vol. 37, 2001, pp. 35–52.
9.
WallerS. T. and ZiliaskopoulosA. K.On the Online Shortest Path Problem with Limited Arc Cost Dependencies. Networks, Vol. 40, 2002, pp. 216–227.
10.
ProvanJ. S.A Polynomial-Time Algorithm to Find Shortest Paths with Recourse. Networks, Vol. 41, 2003, pp. 115–125.
11.
FanY.KalabaR. and MooreJ.Shortest Paths in Stochastic Networks with Correlated Link Costs. Computers and Mathematics with Applications, Vol. 49, 2005, pp. 1549–1564.
12.
GaoS. and ChabiniI.Optimal Routing Policy Problems in Stochastic Time-Dependent Networks. Transportation Research, Part B, Vol. 40, No. 22006, pp. 93–122.
13.
FrankH.Shortest Paths in Probabilistic Graphs. Operations Research, Vol. 17, 1969, pp. 583–599.
14.
MirchandaniP. B.Shortest Distance and Reliability of Probabilistic Networks. Computers and Operations Research, Vol. 3, 1976, pp. 347–355.
15.
SigalC. E.AlanA.PritskerB. and SolbergJ. J.The Stochastic Shortest Route Problem. Operations Research, Vol. 28, 1980, pp. 1122–1129.
16.
LouiR. P.Optimal Paths in Graphs with Stochastic or Multidimensional Weights. Communications of the ACM, Vol. 26, 1983, pp. 670–676.
17.
MarkowitzH.Portfolio Selection. Journal of Finance, Vol. 7, 1952, pp. 77–91.
18.
EigerA.MirchandaniP. B. and SoroushH.Path Preferences and Optimal Paths in Probabilistic Networks. Transportation Science, Vol. 19, 1985, pp. 75–84.
19.
MurthyI. and SarkarS.A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems. Transportation Science, Vol. 30, 1996, pp. 220–236.
20.
MurthyI. and SarkarS.Stochastic Shortest Path Problems with Piece-wise Linear Concave Linear Functions. Management Science, Vol. 44, 1998, pp. 125–136.
21.
YuG. and YangJ.On the Robust Shortest Path Problem. Computers and Operations Research, Vol. 25, 1998, pp. 457–468.
22.
MontemaniR. and GambardellaL.An Exact Algorithm for the Robust Shortest Path Problem with Interval Data. Computers and Operations Research, Vol. 31, 2004, pp. 1667–1680.
23.
BertsimasD. and SimM.Robust Discrete Optimization and Network Flow. Mathematical Programming Series B, Vol. 98, 2003, pp. 49–71.
24.
Miller-HooksE. D. and MahmassaniH. S.Least Possible Time Paths in Stochastic, Time-Varying Networks. Computers and Operations Research, Vol. 25, 1998, pp. 1107–1125.
25.
Miller-HooksE. Optimal Routing in Time-Varying, Stochastic Networks: Algorithms and Implementations. PhD thesis. Department of Civil Engineering, University of Texas, Austin, 1997.
26.
Miller-HooksE. D. and MahmassaniH. S.Path Comparisons for A Priori and Time-Adaptive Decisions in Stochastic, Time-Varying Networks. European Journal of Operational Research, Vol. 146, 2003, pp. 67–82.
27.
BardJ. and BennettJ.Arc Reduction and Path Preference in Stochastic Acyclic Networks. Management Science, Vol. 37, No. 21991, pp. 198–215.
28.
NieY. and WuX.The Shortest Path Problem Considering On-Time Arrival Probability. Transportation Research, Part B, Vol. 43, No. 62009, pp. 597–613.
29.
HansenP.Bicriterion Path Problems. In Multiple Criteria Decision Making: Theory and Application (FandelG. and GalT., eds.), Springer-Verlag, New York, 1979, pp. 109–127.
30.
FanY. and NieY.Optimal Routing for Maximizing the Travel Time Reliability. Networks and Spatial Economics, Vol. 3, No. 32006, pp. 333–344.
31.
NieY. and WuX.Reliable A Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies. In Proc., 18th International Symposium on Transportation and Traffic Theory, in press, 2009.
32.
HadarJ. and RussellW.Rules for Ordering Uncertain Prospects. American Economic Review, Vol. 59, 1969, pp. 25–34.
33.
FanY.KalabaR. and MooreJ.Arriving on Time. Journal of Optimization Theory and Applications, Vol. 127, 2005, pp. 497–513.
34.
HenigM. I.The Shortest Path Problem with Two Objective Functions. European Journal of Operational Research, Vol. 25, 1985, pp. 281–291.
35.
Bar-GeraH.Origin-Based Algorithm for the Traffic Assignment Problem. Transportation Science, Vol. 36, 2002, pp. 398–417.
