Both the risk of concentration phenomenon for the navigation system and the risk of encountering unacceptable delay are reduced by guiding risk-averse drivers along reliable paths while avoiding high-risk links as far as possible. A constrained dynamic A* algorithm is proposed to search for a reliable path subject to a trip duration constraint in a time-dependent road network. The efficiency of the dynamic A* search is increased by taking advantage of information computed off-line. The algorithms proposed are implemented, and their computational performance is analyzed in simulation.
Get full access to this article
View all access options for this article.
References
1.
ArnottR.De PalmaA. and LindseyR.Does Providing Information to Drivers Reduce Traffic Congestion. Transportation Research A, Vol. 25, No. 51991, pp. 309–318.
2.
Ben-AkivaM.De PalmaA. and KayasiI.Dynamic Network Models and Driver Information Systems. Transportation Research A, Vol. 25, No. 51991, pp. 251–266.
3.
LeeC. K.A Multiple-Path Routing Strategy for Vehicle Route Guidance Systems. Transportation Research, Vol. 2, No. 31994, pp. 185–195.
4.
HartE. P.NilssonN. J. and RaphaelB.A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems, Science, and Cybernetics—Part C: Applications and Reviews, SSC Vol. 4, No. 2, 1968, pp. 100–107.
5.
DijkstraE. W.A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
6.
OrdaA. and RomR.Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge Length. Journal of the ACM, Vol. 37, 1990, pp. 607–625.
7.
ZiliaskopoulosA. and MahmassaniH.Time-Dependent Shortest Path Algorithms for Real-Time Intelligent Vehicle Highway System Applications. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 94–100.
8.
BellmanR.On a Routing Problem. Quarterly of Applied Mathematics, Vol. 16, 1958, pp. 87–90.
9.
KaufmannD. E. and SmithR. L.Fastest Paths in Time Dependent Networks for IVHS Application. IVHS Journal, Vol. 1, 1993, pp. 1–12.
10.
ChabiniI. and DeanB.Shortest Path Problems in Discrete-Time Dynamic Networks: Complexity, Algorithms, and Implementations.Technical report. Massachusetts Institute of Technology, Cambridge, 2003.
11.
SungK. and BellM. G. H.Shortest Paths in a Network with Time-Dependent Flow Speeds. European Journal of Operational Research, Vol. 121, 2000, pp. 32–39.
12.
FuL. P. and RilettL. R.Expected Shortest Paths in Dynamic and Stochastic Traffic Networks. Transportation Research B, Vol. 32, No. 71998, pp. 499–516.
13.
MeyerU.Average-Case Complexity of Single-Source Shortest-Paths Algorithms: Lower and Upper Bounds. Journal of Algorithms, Vol. 48, 2003, pp. 91–134.
14.
CerulliR.FestaP. and RaiconiG.Shortest Paths in Randomly Time Varying Networks. Proc., 2001 IEEE Intelligent Transportation Systems Conference, Oakland, Calif., 2001.
15.
SenS.PillaiR.JoshiS. and RathiA.A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems. Transportation Science, Vol. 35, No. 12001, pp. 37–49.
16.
PretolaniD.A Directed Hypergraph Model for Random Time Dependent Shortest Paths. European Journal of Operational Research, Vol. 123, 2000, pp. 315–324.
17.
HallR.The Fastest Path Through a Network with Random Time-Dependent Travel Times. Transportation Science, Vol. 20, 1986, pp. 182–188.
18.
Abdel-AtyM. A.KitamuraR. and JovanisP. P.Investigating Effect of Travel Time Variability on Route Choice Using Repeated-Measurement Stated Preference Data. In Transportation Research Record 1493, TRB, National Research Council, Washington, D.C., 1995, pp. 39–45.
19.
BatesJ.PolakJ.JonesP. and CookA.The Valuation of Reliability for Personal Travel. Transportation Research E, Vol. 37, 2001, pp. 191–229.
20.
LamT. C. and SmallK. A.The Value of Time and Reliability: Measurement from a Value Pricing Experiment. Transportation Research E, Vol. 37, 2001, pp. 231–251.
21.
LiuH. X.ReckerW. and ChenA.Uncovering the Contribution of Travel Time Reliability to Dynamic Route Choice Using Real-Time Loop Data. Transportation Research A, Vol. 38, No. 62004, pp. 435–453.
22.
SivakumarR. A. and BattaR.The Variance-Constrained Shortest Path Problem. Transportation Science, Vol. 28, No. 41994, pp. 309–406.
23.
YenJ. Y.Finding the K Shortest Loopless Paths in a Network. Management Science, Vol. 17, 1971, pp. 711–715.
24.
ClimacoJ. C. N. and MartinsE. Q. V.A Bicriterion Shortest Path Algorithm. European Journal of Operational Research, Vol. 11, 1982, pp. 399–404.
25.
EppsteinD.Finding the K Shortest Paths. SIAM Journal on Computing, Vol. 28, No. 21998, pp. 652–673.
26.
RouphailN. M.RanjithanS. R.DessoukiW. E.SmithT. and BrillE. D.A Decision Support System for Dynamic Pre-Trip Route Planning. Proc., 4th ASCE International Conference on Application of Advanced Technologies in Transportation, New York, 1995, pp. 325–329.
