随机时间依赖交通网络自适应路径选择

陈京荣; 俞建宁; 李引珍

随机时间依赖交通网络自适应路径选择

基金项目:

国家自然科学基金资助项目(60870008)

甘肃省自然科学基金资助项目(3XS051-A25-030)

详细信息

作者简介:
陈京荣(1975- ),女,副教授,博士研究生,研究方向为图理论及其在城市交通中的应用,电话:0931-3352727,E-mail:chenjr@mail.lzjtu.cn

计量
- 文章访问数: 1541
- HTML全文浏览量: 77
- PDF下载量: 47
- 被引次数: 0
出版历程
- 收稿日期: 2008-06-26

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.
- stochastic property /
- time dependency /
- traffic network /
- adaptive path /
- least expected time

HTML全文

参考文献(1)

王行风,贾凌.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.

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 1541
HTML全文浏览量: 77
PDF下载量: 47
被引次数: 0