Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31100
Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks

Authors: Siliang Wang, Minghui Wang, Jun Hu


A novel path planning approach is presented to solve optimal path in stochastic, time-varying networks under priori traffic information. Most existing studies make use of dynamic programming to find optimal path. However, those methods are proved to be unable to obtain global optimal value, moreover, how to design efficient algorithms is also another challenge. This paper employs a decision theoretic framework for defining optimal path: for a given source S and destination D in urban transit network, we seek an S - D path of lowest expected travel time where its link travel times are discrete random variables. To solve deficiency caused by the methods of dynamic programming, such as curse of dimensionality and violation of optimal principle, an integer programming model is built to realize assignment of discrete travel time variables to arcs. Simultaneously, pruning techniques are also applied to reduce computation complexity in the algorithm. The final experiments show the feasibility of the novel approach.

Keywords: stochastic, pruning method, time-varying networks, optimal path planning

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1580


[1] I. Chabini. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time. Transportation Research Record, 1645:170-175, 1999.
[2] K.L. Cooke and E. Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14:493-498, 1966.
[3] Kulkarni. Shortest paths in stochastic networks with arc lengths having discrete distributions. Networks, 23(3):175-183, 1993.
[4] R.W.Hall. The fastest path through a network with random timedependent travel times. Transportation Science, 20(3):91-101, 1986.
[5] S. Gao and I.Chabini. Optimal routing policy problems in stochastic time dependent networks. Transportation Research Part B, 40(2):93-122, 2006.
[6] L. Fu. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information. Transportation Research Part B, 35:749-765, 2001.
[7] L.R. Nielsen. Route Choice in Stochastic Time-Dependent Networks. PhD thesis, Department of Operations Research, University of Aarhus, 2004
[8] Ziliaskopoulos, A., Mahmassani. Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications. Transportation Research Record 1408, 94-100, 1993.
[9] Miller-Hooks, E., Mahmassani, H.,. Least possible time paths in stochastic, time-varying networks. Computers and Operations Research 25, 1107- 1125,1998.
[10] Miller-Hooks. Optimal routing in time-varying, stochastic networks: Algorithms and implementation. Ph.D. Dissertation, The University of Texas at Austin,1997.
[11] Miller-Hooks. Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks.European Journal of Operational Research 146(1): 67-82,2003.