Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:49319", author = "Siliang Wang and Minghui Wang and Jun Hu", title = "Optimal Path Planning under Priori Information in Stochastic, Time-varying Networks", abstract = "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 = "pruning method, stochastic, time-varying networks,optimal path planning.", volume = "4", number = "1", pages = "1-4", }