A Novel Approach of Route Choice in Stochastic Time-varying Networks

Many exist studies always use Markov decision processes (MDPs) in modeling optimal route choice in stochastic, time-varying networks. However, taking many variable traffic data and transforming them into optimal route decision is a computational challenge by employing MDPs in real transportation networks. In this paper we model finite horizon MDPs using directed hypergraphs. It is shown that the problem of route choice in stochastic, time-varying networks can be formulated as a minimum cost hyperpath problem, and it also can be solved in linear time. We finally demonstrate the significant computational advantages of the introduced methods.

Authors:

• Siliang Wang
• Minghui Wang

Keywords:

• Markov decision processes (MDPs)
• stochastictime-varying networks
• hypergraphs
• route choice.

References:

[1] Miller-Hooks, E.. Adaptive least expected time paths in stochastic,
time-varying transportation and data networks. Networks 37(1),
35-52,2001.
[2] Miller-Hooks, E., Mahmassani, H.,. Least possible time paths in
stochastic, time-varying networks. Computers and Operations Research
25, 1107-1125.,1998.
[3] Miller-Hooks. Optimal routing in time-varying, stochastic
networks:Algorithms and implementation. Ph.D. Dissertation, The
University of Texas at Austin..,1997
[4] R.W. Hall. The fastest path through a network with random
time-dependent travel times. Transportation Science, 20(3):182-188,
1986..
[5] Miller-Hooks, E., Mahmassani, H.. Least expected time paths in
stochastic, time-varying transportation networks.Transportation Science
34, 198-215.,2000.
[6] D. Pretolani. A directed hypergraph model for random time-dependent
shortest paths. European Journal of Operational Research, 123:315,
2000..
[7] S.Gao et al.Best routing policy problem in stochastictime-dependent
networks, Transp. Res. Rec., vol.1783, pp.188-196,2002..
[8] L.R. Nielsen, K.A. Andersen, and D. Pretolani. Bicriterion shortest
hyperpaths in random time-dependent networks. IMA Journal of
Management Mathematics, 2003.
[9] S. Kim, Optimal vehicle routing and scheduling with real-time traffic
information, Ph.D. thesis, Dept. Ind. Syst. Eng., Univ. Michigan,
AnnArbor, MI, 2003..
[10] G.H.Polychronopoulos and J. N. Tsitsiklis, Stochastic shortest path
problems with recourse, Networks, vol. 27, no. 2, pp. 133-143, 1996..
[11] L.R. Nielsen. Route Choice in Stochastic Time-Dependent Networks.
PhD thesis, Department of Operations Research, University of Aarhus,
2004..
[12] L.R. Nielsen, K.A. Andersen, and D. Pretolani. Finding the K shortest
hyperpaths.Computers & Operations Research, 32(6):1477-1497,
2005.....
[13] L.R. Nielsen, D. Pretolani, and K.A. Andersen. Finding the K shortest
hyperpaths using reoptimization. Operations Research
Letters.doi:10.1016/j.orl.2005.04.008, 2005....
[14] G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. Directed hypergraphs
and applications. Discrete Applied Mathematics, 42:177-201, 1993...