Principles and its prototype algorithm for dual shortest path tree in networks with turning constraints
-
摘要: 为比较有无转向约束条件下最短路径特征及其搜索算法的异同点, 基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树, 提出了对偶最短路径树(DSPT)概念, 并利用其分析算法之间的关系。研究结果表明: 转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内, 而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的; 对于转向约束网络中的最短路径问题可建立一个DSPT原型算法, 结合各种SPT标号技术能设计出更多的有效算法。Abstract: To analyze the difference and similarity between the shortest path characteristics and searching algorithms with and without turning constraints, dual graph theory was studied, the spanning tree of dual network was constructed with the shortest path set from a source node to all arcs in turning constraint network, the concept of dual shortest path tree(DSPT) was put forward and used for algorithm comparison.Analysis result shows that the present solution methods with turning constraints, including arc-labeling algorithm, node-labeling algorithm and dual-network method, can be unified into the same DSPT algorithmic frame, and have the same path searching strategies as the shortest path tree(SPT) algorithm without turning constraints; a prototype DSPT algorithm can be developed for the shortest path problem in networks with turning constraints, and more efficient algorithms can be designed according to different SPT labeling techniques.
-
Key words:
- traffic network /
- dual shortest path tree /
- dual graph /
- turning constraint /
- prototype algorithm
-
表 1 G1中的弧长与转向延误值
Table 1. Arc lengths and turning delays in G1
i j cij σijk 1 2 50 5, 5 3 10 55, ∞ 5 45 20 2 3 15 10, 5 5 10 10 3 1 20 5, 60, ∞ 4 15 10, 15 4 2 20 15, 10 5 35 20 5 4 30 10, 25 
下载: 导出CSV
-
[1] 马永锋, 陆键, 项乔君, 等. 基于出行决策的公路网多目标最优路径算法[J]. 交通运输工程学报, 2007, 7(3): 100-105. http://transport.chd.edu.cn/article/id/200703021MA Yong-feng, LU Jian, XI ANG Qiao-jun, et al. Optimalroute arithmetic with multigoalsin highway network based ontravel decision-making[J]. Journal of Traffic and Transportation Engineering, 2007, 7(3): 100-105. (in Chinese) http://transport.chd.edu.cn/article/id/200703021 [2] 徐红梅, 杨兆升, 闫长文, 等. 基于蚁群算法求解物流订单派送问题[J]. 长安大学学报: 自然科学版, 2007, 27(6): 84-86. https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200706018.htmXU Hong-mei, YANG Zhao-sheng, YAN Chang-wen, et al. Solving appoint order formjob problem based on ant colony system[J]. Journal of Chang an University: Natural Science Edition, 2007, 27(6): 84-86. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XAGL200706018.htm [3] 陆锋. 最短路径算法: 分类体系与研究进展[J]. 测绘学报, 2001, 30(3): 269-275. doi: 10.3321/j.issn:1001-1595.2001.03.016LU Feng. Shortest path algorithms: taxonomy and advancein research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 269-275. (in Chinese) doi: 10.3321/j.issn:1001-1595.2001.03.016 [4] 黎茂盛, 王炜. 基于路网子图空间的交通流平衡分析方法[J]. 中国公路学报, 2007, 20(2): 97-101. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200702018.htmLI Mao-sheng, WANG Wei. Traffic flow equilibrium analysis method based on road network sub-graph space[J]. China Journal of Highway and Transport, 2007, 20(2): 97-101. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200702018.htm [5] KIRBY R F, POTTS R B. The mini mumroute problem for networks with turn penalties and prohibitions[J]. Transportation Research, 1969, 3: 397-408. doi: 10.1016/S0041-1647(69)80022-5 [6] ANEZ J, BARRA T, PEREZ B. Dual graph representation of transport networks[J]. Transportation Research Part B, 1996, 30(3): 209-216. doi: 10.1016/0191-2615(95)00024-0 [7] ZILI ASKOPOULOS A K, MAHMASSANI HS. A note onleast time path computation considering delays and prohibitions for intersection movements[J]. Transportation Research Part B, 1996, 30(5): 359-367. doi: 10.1016/0191-2615(96)00001-X [8] 万绪军, 胡安洲. 用边标号法解决交通网络连通性问题[J]. 中国公路学报, 1999, 12(4): 73-77. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL199904012.htmWAN Xu-jun, HU An-zhou. Representation research ontransport networks[J]. China Journal of Highway and Transport, 1999, 12(4): 73-77. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL199904012.htm [9] 王丰元, 潘福全, 张丽霞, 等. 基于交通限制的路网最优路径算法[J]. 交通运输工程学报, 2005, 5(1): 92-95. http://transport.chd.edu.cn/article/id/200501022WANG Feng-yuan, PAN Fu-quan, ZHANG Li-xia, et al. Optimal path algorithm of road network with traffic restriction[J]. Journal of Traffic and Transportation Engineering, 2005, 5(1): 92-95. (in Chinese) http://transport.chd.edu.cn/article/id/200501022 [10] 任刚, 王炜, 邓卫. 带转向延误和限制的最短路径问题及其求解方法[J]. 东南大学学报: 自然科学版, 2004, 34(1): 104-108. https://www.cnki.com.cn/Article/CJFDTOTAL-DNDX200401024.htmREN Gang, WANG Wei, DENG Wei. Shortest path problem with turn penalties and prohibitions and its solutions[J]. Journal of Southeast University: Natural Science Edition, 2004, 34(1): 104-108. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-DNDX200401024.htm [11] 任刚, 王炜. 基于转向的Logit交通分配算法[J]. 交通运输工程学报, 2005, 5(4): 101-105. http://transport.chd.edu.cn/article/id/200504021REN Gang, WANG Wei. Turn-based algorithm for Logit traffic assignment[J]. Journal of Traffic and Transportation Engineering, 2005, 5(4): 101-105. (in Chinese) http://transport.chd.edu.cn/article/id/200504021 [12] 郑年波, 李清泉, 徐敬海, 等. 基于转向限制和延误的双向启发式最短路径算法[J]. 武汉大学学报: 信息科学版, 2006, 31(3): 256-259. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200603016.htmZHENG Nian-bo, LI Qing-quan, XUJing-hai, et al. Abidi-rectional heuristic shortest path algorithm with turn prohibitions and delays[J]. Geomatics and Information Science of Wuhan University, 2006, 31(3): 256-259. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200603016.htm -
点击查看大图
图(6) / 表(1)
计量
- 文章访问数: 305
- HTML全文浏览量: 123
- PDF下载量: 304
- 被引次数: 0
