| 道路网络中门到门包含重复节点的最优路径算法 |
| |
| 引用本文： | 李挺,杨殿阁,罗禹贡,郑四发,李克强,连小珉. 道路网络中门到门包含重复节点的最优路径算法[J]. 清华大学学报(自然科学版), 2007, 47(5): 707-709 |
| |
| 作者姓名： | 李挺 杨殿阁 罗禹贡 郑四发 李克强 连小珉 |
| |
| 作者单位： | 清华大学,汽车安全与节能国家重点实验室,北京,100084 |
| |
| 摘 要： | 设计了用于包含交通约束的受限路网中基于兴趣点(PO I)的门到门包含重复节点的寻路算法。首先利用距离最短准则建立PO I和路网间的临时拓扑关系,然后根据受限路网中最优路径的结构特征,构造包含驶入路段的节点进行寻路拓展,以此为基础进行标记设定广度优先搜索,即可获得门到门包含重复节点的最优路径。在道路密度较大的北京市路网中的试验结果表明,该算法能够根据交通约束规划出实用的最优路径,对于长度约60 km路径的计算平均耗时在3 s左右,可以满足车辆导航应用的实时性要求。
|
| 关 键 词： | 最优路径算法 交通约束 重复节点 道路网络 |
| 文章编号： | 1000-0054(2007)05-0707-03 |
| 修稿时间： | 2006-04-05 |
Between-POIs shortest path algorithm containing overlapped nodes for traffic road networks |
| |
| LI Ting,YANG Diange,LUO Yugong,ZHENG Sifa,LI Keqiang,LIAN Xiaomin. Between-POIs shortest path algorithm containing overlapped nodes for traffic road networks[J]. Journal of Tsinghua University(Science and Technology), 2007, 47(5): 707-709 |
| |
| Authors: | LI Ting YANG Diange LUO Yugong ZHENG Sifa LI Keqiang LIAN Xiaomin |
| |
| Abstract: | An algorithm was developed to find the shortest paths between points of interest(POIs) in traffic road networks constrained by traffic regulations and with shortest paths containing overlapped nodes.The algorithm first constructs the temporary topological relationship with the minimum-distance rule between POIs and the network, and then constructs nodes containing source links according to the characteristics of the best paths in the constrained networks.The method obtains the shortest paths containing overlapped nodes with a general label setting breadth-first search.Experimental results based on a high density road network in Beijing show that this algorithm provides practical shortest paths that satisfy traffic regulations,with the average computing time for path lengths of about 60 km of 3 s.Therefore,this algorithm can provide real time vehicle navigation support. |
| |
| Keywords: | shortest path algorithm traffic regulation overlapped nodes road network |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
