Current Issue Cover
道路转向延迟的动态对偶图模型

郑年波, 陆 锋, 段滢滢(中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室, 北京 100101)

摘 要
传统的道路转向延迟对偶图表达法缺乏对交通网络时间依赖特性的考虑,不适合动态路径规划问题的求解。本文将时间因素引入到对偶图中,发展了一种动态对偶图模型,将交通路网表达为动态对偶网络,并为之定义了FIFO(先进先出)条件,推导了满足FIFO条件的动态行程计算方法,设计了时间依赖的标号设定最短路径算法。实验结果表明,利用该对偶图模型和动态对偶网络,能有效表达路网转向延迟,在以出行时间为标准的动态路径规划中,基于动态对偶网络的路径规划结果可节省约16%的出行时间。
关键词
Dynamic Dual Graph Model for Turn Delays on Road Networks

ZHENG Nianbo, LU Feng, DUAN Yingying(State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101)

Abstract
Traditional dual graph modeling turn delays at road intersections are ill-suited to the time-dependent route planning in the travel information services, due to the ignorance of time-dependency of transportation networks. With introducing a time factor into a dual graph, a dynamic dual network model is presented, where the links in the original network are mapped into the nodes in the dual network, and the turns in the original network are mapped into the links in the dual network. Besides, the First-In-First-Out(FIFO) condition is defined for this dynamic dual network, and two relevant arrival-time computational formulas are then given out. The classical label-setting shortest path algorithm is temporally adapted to the dynamic dual network by the definition of origin-destination dual node sets and time-dependent dual node labels. An experiment on a real road network shows that the proposed model is suitable for dealing with the turn delays, and saved about 16 percent travel time in the real-time route planning.
Keywords

订阅号|日报