Adaptive Path Selection in Stochastic and Time-Dependent Traffic Networks
-
摘要: 根据路段旅行时间具有随机性、时间依赖性等特点,将路段在不同时刻的旅行时间定义为离散随机变量;建立了随机的时间依赖网络的自适应路径模型,给出用多项式表示时间复杂性的算法,获得基于最小期望时间的所有节点到给定终点的自适应路径.出行者可以根据到达某节点的具体时刻选择下一步的最优路径.通过算例验证了算法的可行性.Abstract: The travel time for each road section at different time was defined as a discrete random variable according to the stochastic and time dependent properties of travel time in traffic networks.Based on this,an adaptive path selection model was built in stochastic,time dependent networks,and an algorithm with polynomial time complexity was given.By this model,travelers can obtain adaptive paths from all nodes to a specified destination with the least expected time,and then select an optimal route to their destination at any node according to the arrival time.In the end,an illustrative example verified the effectiveness of the algorithm.
-
Key words:
- stochastic property /
- time dependency /
- traffic network /
- adaptive path /
- least expected time
-
王行风,贾凌.GIS支持下的城市交通网络最短路径研究[J].计算机与现代化,2005,115(3):9-12.WANG Xingfeng,JIA Ling.Research on shortest path searching for urban traffic network based on GIS[J].Computer and Modernization,2005,115(3):9-12.[2] POLYCHRONOPOULOS G H.Stochastic shortest path problems with recourse[J].Networks,1996,27(2):133-143.[3] FRANK H.Shortest path in probabilistic graphs[J].Operations Research,1969,17(4):583-599.[4] WALLER S T,ZILIASKOPOULOS A K.On the on-line shortest path problem with limited arc cost dependencies[J].Networks,2002,40(4):216-227.[5] FU L.An adaptive routing algorithm for in-vehicle route guidance systems with real-time information[J].Transportation Research Part B,2001,35(8):749-765.[6] COOKE K L,HALSEY E.The shortest route through a network with time-dependent internode transit times[J].Journal of mathematical analysis and applications,1966,14:493-498.[7] CHABINI I.Discrete dynamic shortest path problems in transportation applications[J].Transportation Research Record,1998,1645:170-175.[8] PRETOLANI D.A directed hypergraph model for random time dependent shortest paths[J].European Journal of Operational Research,2000,123(2):316-324.[9] DAVIES C,LINGRAS P.Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks[J].European Journal of Operational Research,2003,144(1):27-38.[10] 谭国真.时变、随机网络最优路径算法及其用研究[D].大连:大连理工大学,2002.[11] MILLER-HOOKS E,MAHMASSANI H.Path comparisons for a priori and time-adaptive decisions in stochastic,time-varying networks[J].European Journal of Operational Research,2003,146(1):67-82.[12] HALL R W.The fastest path through a network with random time-dependent travel times[J].Transportation Science,1986,20(3):182-188.[13] GALLO G,LONGO G,PALLOTTINO S,et al.Directed hypergraphs and applications[J].Discrete Applied Mathematics,1993,42(2):177-201.[14] MILLER-HOOKS E,MAHMASSANI H.Least possible time paths in stochastic,time-varying networks[J].Computer Operations Research,1998,25(12):1107-1125.[15] MILLER-HOOKS E,MAHMASSANI H.Least expected time paths in stochastic,time-varying transportation networks.Transportation Science,2000,34(2):198-215.[16] MILLER-HOOKS E.Least-expected time paths with recourse in stochastic,time-varying transportation and data networks[J].Networks,2001,37(1):35-52.[17] FU L,RILETT L R.Expected shortest paths in dynamic and stochastic traffic networks[J].Transportation Research Part B,1998,32(7):499-516.[18] KAUFMAN D,SMITH R.Fastest paths in time-dependent networks for intelligent vehicle highway systems applications[J].IVHS Journal,1993,1(1):1-11.
点击查看大图
计量
- 文章访问数: 1533
- HTML全文浏览量: 75
- PDF下载量: 47
- 被引次数: 0