顾及转向延误的时间依赖A最短路径算法

被引：19

作者：

郑年波 ^{[1
]}

陆锋 ^{[1
]}

李清泉 ^{[2
]}

段滢滢 ^{[1
]}

机构：

[1] 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室

[2] 武汉大学交通研究中心

来源：

测绘学报 | 2010年 / 05期

关键词：

路径规划; 最短路径; A*算法; 时间依赖网络; 转向延误;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

建立基于路段的时间依赖网络模型,将转向延误时间引入到FIFO(先进先出)条件的定义中,并给出满足FIFO条件的路段到达时间和转向延误时间计算式。通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。试验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加10%左右。由于不再需要进行频繁的路径重优化,该算法能提高路径规划的整体效率。

引用

页码：534 / 539

页数：6

共 9 条

[1]

出行信息服务关键技术研究进展与问题探讨 [J].

陆锋 ;

郑年波 ;

段滢滢 ;

张健钦 .

中国图象图形学报, 2009, 14 (07) :1219-1229

[2]

基于弧段标记的交通网络时间最短路径算法 [J].

高松 ;

陆锋 .

地球信息科学, 2008, (05) :604-610

[3]

基于转向限制和延误的双向启发式最短路径算法 [J].

郑年波 ;

李清泉 ;

徐敬海 ;

宋莺 .

武汉大学学报(信息科学版), 2006, (03) :256-259

[4]

带转向延误和限制的最短路径问题及其求解方法 [J].

任刚 ;

王炜 ;

邓卫 .

东南大学学报(自然科学版), 2004, (01) :104-108

[5]

车载导航系统中顾及道路转向限制的弧段Dijkstra算法 [J].

韩刚 ;

蒋捷 ;

陈军 ;

曹元大 .

测绘学报, 2002, (04) :366-368

[6]

基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法 [J].

陆锋 ;

卢冬梅 ;

崔伟宏 .

中国图象图形学报, 1999, (12)

[7]

Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks[J] Eliécer Gutiérrez;Andrés L. Medaglia Annals of Operations Research 2007,

[8]

A shortest path algorithm with novel heuristics for dynamic transportation networks[J] B. Huang;Q. Wu;F. B. Zhan International Journal of Geographical Information Science 2007,

[9]

Modeling costs of turns in route planning[J] Stephan Winter Geoinformatica: An international journal of advances of computer science for geographic 2002,

← 1 →