城市路网动态转向建模与优先选择研究

交通运输系统工程与信息 ›› 2017, Vol. 17 ›› Issue (4): 132-137.

城市路网动态转向建模与优先选择研究

徐广宁¹，王印海*^{1, 2}，曾自强^{2, 3}

1. 哈尔滨工业大学交通科学与工程学院，哈尔滨150090；2. 华盛顿大学土木与环境工程学院，西雅图98195，美国； 3. 四川大学商学院不确定决策实验室，成都610065

收稿日期:2017-04-21 修回日期:2017-06-13 出版日期:2017-08-25 发布日期:2017-08-25
作者简介:徐广宁（1983-），男，广东广州人，博士生.
基金资助:
国家自然科学基金/National Natural Science Foundation of China（51138003）

Network Representation and Sub-optimal Choice of Linkbased Dynamic Routing in Urban Network

XU Guang-ning ¹,WANG Yin-hai ^1,2, ZENG Zi-qiang ^{2, 3}

1. School of Transportation Science and Engineering, Harbin Institute of Technology, Harbin 150090, China; 2. School of Civil and Environment Engineering, University ofWashington, Seattle 98195, USA; 3. Uncertainty Decision-Making Laboratory, School of Business, Sichuan University, Chengdu 610065, China

Received:2017-04-21 Revised:2017-06-13 Online:2017-08-25 Published:2017-08-25

摘要/Abstract

摘要：

确立网络表述方式是在城市路网中建立路径规划系统的基础工作之一.在不牺牲计算效率的前提下，网络表述方式既要能灵活反映出车辆在交叉口中所能进行的转向动作，又必须保证这些转向动作不会造成交叉口的安全隐患与通行效率的下降.针对这一需求，提出了一套面向决策点的网络表述方法，并在其数据结构的基础上，通过扩展现有的Dijkstra 最短路搜索算法，在不改变以最短路为优化目标的前提下，以次优选择方式实现了干道优先和非左转优先的转向选择.以现实交通网络为模型，通过一系列实验验证算法在静态路径规划中的有效性.结果表明，算法以提高0.5%额外总出行成本的前提下，同时降低了11%的支道选择和21%的左转选择.

关键词: 智能交通, 路径规划, 网络表示, 动态转向, 次优选择

Abstract:

Establishing network representation is usually the first step of implementing a route planning system in urban street networks. Without losing computation efficiency, network representation should be able to reflect all the possible vehicle routing movements that are allowed in city intersections considering transportation safety and mobility. To fulfill the requirement, a full package of decision- point oriented network representation is proposed in this paper. Based on the data structure of the network representation, two extensions on the conventional Dijkstra shortest path finding algorithm, not by changing its global optimality but using sub- optimal thresholds, are also proposed to establish priority turning for arterial first and left-turn avoiding principles. In order to validate the network representation and the extended algorithms, a series of static route planning experiments are conducted using the simulation model of a real-world street network. Test results manifest that 11% of branches and 21% of left-turn choices are avoided simultaneously only at the cost of 0.5% of extra total travel cost.

Key words: intelligent transportation, route planning, network representation, link-based routing, suboptimal choice

中图分类号:

U492.2

徐广宁，王印海，曾自强. 城市路网动态转向建模与优先选择研究[J]. 交通运输系统工程与信息, 2017, 17(4): 132-137.

XU Guang-ning,WANG Yin-hai,ZENG Zi-qiang . Network Representation and Sub-optimal Choice of Linkbased Dynamic Routing in Urban Network[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(4): 132-137.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19461.shtml

http://www.tseit.org.cn/CN/Y2017/V17/I4/132

参考文献

[1] WATLING D, VAN VUREN T. The modeling of dynamic route guidance systems[J]. Transportation Research Part C Emerging Technology, 1993, 1(2): 159- 182.

[2] YANG H, MA O, WONG S. New observations on the benefit evaluation of advanced traveler information systems[J]. Intelligent Transportation System Journal, 1999, 5(3): 251-274.

[3] DONG W. An overview of in- vehicle route guidance system[C]. Australasian Transport Research Forum, 2011.

[4] FU L, SUN D, RILETT L. Heuristic shortest path algorithms for transportation applications: State of the art[J]. Computers and Operations Research, 2006, 33 (11): 3324-3343.

[5] SCHMITT E, JULA H. Vehicle route guidance systems: classification and comparison[C]. IEEE Intelligent Transportation System Conference, 2006.

[6] ANEZ J, DE LA BARRA T, PEREZ B. Dual graph representation of transport networks[J]. Transportation Research Part B: Methodology, 1996, 30(3): 209-216.

[7] 周熙阳, 杨兆升, 张伟, 等. 考虑信号交叉口转向类型的最优路径规划算法[J]. 华南理工大学学报(自然科学版), 2016, 44(4): 101-108. [ZHOU X Y, YANG Z S, ZHANG W, et al. Optimal route planning algorithm considering movement type at signal intersections[J]. Journal of South China University of Technology (Natural Science Edition), 2016, 44(4): 101-108.]

[8] 张可, 刘小明, 王笑京. 车辆自动导航的路线优化系统研究[J]. 系统工程, 2001, 19(2): 48-53. [ZHANG K, LIU X M, WANG X J. Research on route planning system for vehicle automatic navigation[J]. System Engineering, 2001, 19(2): 48-53.]

[9] 郑年波, 李清泉, 徐敬海, 等. 基于转向限制和延误的双向启发式最短路径算法[J]. 武汉大学学报(信息科学版), 2006, 31(3): 256-259. [ZHENG N B, LI Q Q, XU J H, et al. A Bidirectional heuristic shortest path algorithm with turn prohibitions and delays[J]. Journal of Wuhan University (Information Science Volume), 2006, 31(3): 256-259.]

[10] CLOSSEY J, LAPORTE G, SORIANO P. Solving arc routing problems with turn penalties[J]. Journal of Operational Reseach Society, 2001, 52(4): 433-439.

[11] VILLENEUVE D, DESAULNIERS G. The shortest path problem with forbidden paths[J]. European Journal of Operation Research, 2005(165): 97-107.

[12] NAMKOONG S, RHO J, CHOI J. Development of the tree- based link labeling algorithm for optimal pathfinding in urban transportation networks[J]. Mathematical Programming, 1998, 27(9-11): 51-65.

[13] WU Y, ZHANG G, WANG Y. Link- journey speed estimation for urban arterial performance measurement using advance loop detector data under congested conditions[J]. Journal of Transportation Engineering, 2012, 138(11): 1321-1332.

[14] ZHANG H. Link-journey-speed model for arterial traffic[J]. Transportation Research Record 1999, 1676 (99): 109-115.

[15] SKABARDONIS A, GEROLIMINIS N. Real-time monitoring and control on signalized arterials[J]. Journal of Intelligent Transportation System, 2008(12): 64-74.

[16] ZHANG H, NIE X. Some consistency conditions for dynamic traffic assignment problems[J]. Networks Spatial Economics, 2005, 5(1): 71-87.