|
文摘
|
标号算法是经典的最短路径算法之一，在交通领域中具有广泛的应用。在交通领域中，时间最短路径比距离最短路径更有意义，而时间最短路径不仅与道路的时间权值有关，还与道路之间的转弯阻抗有关。在传统的交通路网抽象方式下，道路抽象为平面图中的弧段，道路间的交叉口抽象为节点。本文介绍了一种适用于传统交通路网模型的弧段标记时间最短路径算法，详细阐述了该算法的原理、数据基础与运行结构。通过分析和实例测试表明，该算法可以顾及城市路网在路口的交通限行与转弯延迟的影响，并且时间复杂度低，具有一定的实际应用价值。 |
|
其他语种文摘
|
Label-setting algorithm is one of the most classic shortest path algorithm, and widely used in the field of transportation. In the field of transportation, the shortest time path is more significant than the shortest length path. And the shortest time path is related with many factors such as the hierarchy of the roadway, the average speed and the delay from one roadway to another. In general, a logic road network is produced from a real one in this way： the real roadway is abstracted as an arc in the logic network and the node is the crossing. After a brief description of some typical kinds of transportation network data model, an arc-labeling time shortest path algorithm is discussed here, which is more suitable than the node-labeling shortest path algorithm. The principle and theory analysis are presented in this article as well as the base data and running structure. In the following the characteristics and advantages of the are-labeling algorithm, compared to node-labeling algorithm, are given. That it is more easily to calculate the delay and trace the time shortest path in arc-labeling algorithm. By the theory analysis and experiment test, it is proved that the arc-labeling algorithm can take the traffic informat affect and turning delay into account easily. So it is a practical shortest time path algorithm. |
|
来源
|
地球信息科学
,2008,10(5):604-610 【扩展库】
|
|
关键词
|
标号算法
;
弧段标记
;
时间最短
;
转弯延迟
|
|
地址
|
中国科学院地理科学与资源研究所, 资源与环境信息系统国家重点实验室, 北京, 100101
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1560-8999 |
|
学科
|
自动化技术、计算机技术;公路运输 |
|
基金
|
国家863计划
;
中国科学院知识创新工程领域前沿项目
;
中国科学院知识创新工程重要方向项目
|
|
文献收藏号
|
CSCD:3402659
|
|
|
1.
李清泉. 数字中国地理空间基础框架.
地理与地理信息科学,2004,20(3):31-35
|
被引
9
次
|
|
|
|
|
2.
陆锋.
基于特征的城市交通网络GIS,数据组织与处理方法,1999
|
被引
1
次
|
|
|
|
|
3.
NLSSON N.J.
Artificial Intelligence:A New Synthesis,1999
|
被引
1
次
|
|
|
|
|
4.
陆锋. 最短路径算法:分类体系与研究进展.
测绘学报,2001,30(3):269-275
|
被引
63
次
|
|
|
|
|
5.
陆锋. 交通网络限制搜索区域时间最短路径算法.
中国图象图形学报,1999,4(A):849-853
|
被引
24
次
|
|
|
|
|
6.
Caldwell T. On finding minimum routes in a network with turn penalties.
Communication of the ACM,1961,4(2):107-108
|
被引
6
次
|
|
|
|
|
7.
韩刚. 车载导航系统中顾及道路转向限制的弧段Dijkstra算法.
测绘学报,2002,31(4):366-368
|
被引
11
次
|
|
|
|
|
8.
任刚. 带转向延误和限制的最短路径问题及其求解方法.
东南大学学报,2004,34(1):104-108
|
被引
14
次
|
|
|
|
|
9.
郑年波. 基于转向限制和延误的双向启发式最短路径算法.
武汉大学学报,2006,31(3):256-259
|
被引
2
次
|
|
|
了解气象卫星更多信息，请访问