考虑交叉口转向延误的最短路径拍卖算法

被引：6

作者：

杜牧青

程琳

机构：

[1] 东南大学交通学院

来源：

西南交通大学学报 | 2010年 / 45卷 / 02期

关键词：

最短路径; 拍卖算法; 交叉口延误; 转向限制;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; O224 [最优化的数学理论];

学科分类号：

081202 ; 070105 ; 1201 ;

摘要：

为了改进传统算法求解最短路径时运算量大且无法计算交叉口转向延误的不足,提出可直接求解受限路网中两点之间最短路径的改进拍卖算法.将价格矢量扩展至二维,解决了价值量被不同转向行为共用的问题.设计了节省存储空间的数据存储结构,可准确描述交叉口转向行为,且便于检索.针对不同规模和密度的随机路网,比较了改进算法和Dijkstra算法求解单一起、终点之间的最短路径问题.结果表明,在含5 000个结点、20 000条路段的高密度路网中,改进拍卖算法的搜索时间约为Dijkstra算法的30%,能准确求解受限路网中的最短路径,并保留了原Auction算法可并行计算的基本性质.

引用

页码：249 / 254

页数：6

共 10 条

[1] 交通诱导系统中道路网络的表达与存储方法 [J].