[1]任刚,王炜,邓卫.带转向延误和限制的最短路径问题及其求解方法[J].东南大学学报(自然科学版),2004,34(1):104-108.[doi:10.3969/j.issn.1001-0505.2004.01.025]
　Ren 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.[doi:10.3969/j.issn.1001-0505.2004.01.025]
点击复制

带转向延误和限制的最短路径问题及其求解方法()
分享到：

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
34
期数:
2004年第1期
页码:
104-108
栏目:
交通运输工程
出版日期:
2004-01-20

文章信息/Info

Title:
Shortest path problem with turn penalties and prohibitions and its solutions
作者:
任刚;  王炜;  邓卫
东南大学交通学院, 南京 210096
Author(s):
Ren Gang;  Wang Wei;  Deng Wei
College of Transportation, Southeast University, Nanjing 210096, China
关键词:
最短路径;  转向延误和限制;  对偶图;  标号;  扩展邻接表
Keywords:
shortest path;  turn penalties and prohibitions;  dual graph;  label;  extended adjacency list
分类号:
U491
DOI:
10.3969/j.issn.1001-0505.2004.01.025
摘要:
阐述了带转向延误和限制的最短路径问题(SP-Turn)的基本原理,系统介绍了现有的求解方法,包括扩展网络法、对偶网络法和弧标号算法,并提出了一个节点标号算法用于对比.分析指出弧标号、节点标号算法在算法原理上是一致的,对偶网络法是对它们的直观化.同时指出在SP-Turn方法中,扩展邻接表是高效的网络表示形式,在合理选择的前提下,一般SP算法的标号设定、标号修正等标号技术同样适用,最短路径可由节点至弧的形式转换为节点至节点的常规形式.
Abstract:
The theory of shortest path problem with turn penalties and prohibitions(SP-Turn)was introduced, and its state-of-the-art approaches, including method of expanded-network, dual-network and arc-labeling, were reviewed, while a new node-labeling algorithm was proposed for comparison. Further analysis shows that arc-labeling and node-labeling algorithms have no difference in fundamentals, while the dual-network method is their visualized version. We also point that the extended adjacency list is very efficient for network representation in SP-Turn methods, those labeling techniques used in ordinary shortest path algorithms, i.e. label-setting and label-correcting, can also be adopted after problem-specific choice, and the shortest paths of node-to-arc structure can be transformed to the standard node-to-node ones.

参考文献/References:

[1] Kirby R F,Potts R B.The minimum route problem for networks with turn penalties and prohibitions [J].Transportation Research,1969,3:397-408.
[2] Easa S M.Traffic assignment in practice:overview and guidelines for users [J]. Journal of Transportation Engineering, 1991,117(6):602-623.
[3] De La Barra T.Integrated land use and transport modeling [M].Cambridge:Cambridge Univ Press,1989.65-87.
[4] A(～overn)ez J,De La Barra T,Pérez B.Dual graph representation of transport networks [J].Transportation Research B, 1996,30(3):209-216.
[5] Caldwell T.On finding minimal routes in a network with turning penalties [J]. Communications of the ACM,1961,4(2):107-108.
[6] Ziliaskopoulos A K,Mahmassani H S.A note on least time path computation considering delays and prohibitions for intersection movements [J].Transportation Research B,1996,30(5):359-367.
[7] Pallottino S,Scutella M G.Shortest path algorithms in transportation models:Basemic Timesal and innovative aspects.[EB/OL].http://ftp.di.unipi.it/pub/techreports/TR-97-06.ps.Z.1997-06-25/2003-02-15.
[8] Cherkassky B V,Goldberg A V,Radzik T.Shortest paths algorithms:theory and experimental evaluation [R].Stanford:Computer Science Department,Stanford University,1993.

备注/Memo

备注/Memo:
基金项目: 国家“十五”科技攻关资助项目(2001BA402A06).
作者简介: 任刚(1976—),男,博士生; 王炜(联系人),男,博士,教授,博士生导师,wangwei@seu.edu.cn.
更新日期/Last Update: 2004-01-20