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

Authors: Siliang Wang, Minghui Wang

Abstract:

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.

Keywords: Markov decision processes (MDPs), stochastictime-varying networks, hypergraphs, route choice.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333240

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...