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

Auction Algorithm for Shortest Paths in Road Networks Considering Delays for Intersection Movements

作　　者：杜牧青[1] 程琳[1] 

机构地区：[1]东南大学交通学院,江苏南京210096

出　　处：《西南交通大学学报》2010年第2期249-254,共6页Journal of Southwest Jiaotong University

基　　金：国家973计划资助项目(2006CB705500);国家高技术研究发展计划(2007AA11Z205);国家自然科学基金(50578037)

摘　　要：为了改进传统算法求解最短路径时运算量大且无法计算交叉口转向延误的不足,提出可直接求解受限路网中两点之间最短路径的改进拍卖算法.将价格矢量扩展至二维,解决了价值量被不同转向行为共用的问题.设计了节省存储空间的数据存储结构,可准确描述交叉口转向行为,且便于检索.针对不同规模和密度的随机路网,比较了改进算法和Dijkstra算法求解单一起、终点之间的最短路径问题.结果表明,在含5 000个结点、20 000条路段的高密度路网中,改进拍卖算法的搜索时间约为Dijkstra算法的30%,能准确求解受限路网中的最短路径,并保留了原Auction算法可并行计算的基本性质.In order to overcome the deficiencies that traditional algorithms for solving the shortest path problems spend large computing costs and are unable to consider the turning delays at intersections,an improved auction algorithm that can directly find out the shortest path between two nodes in restricted networks was proposed.In this algorithm,the price vector was expanded from one dimension to two to avoid being overwritten when it represents different turning movements.A memory-saving and easy-searched data structure was designed to describe intersection movements accurately.The proposed algorithm and Dijkstra＇s algorithm were implemented to solve the single-origin/single-destination shortest path problems for comparison in random networks of various scales and densities.The results show that the running time of the proposed algorithm is approximately 30% of that of Dijkstra＇s algorithm in high density networks with 5 000 nodes and 20 000 links,and it can accurately solve for the shortest path in restricted networks.This algorithm also inherits the characteristic from the original auction algorithm in the performance of parallel computing.

关 键 词：最短路径 拍卖算法 交叉口延误 转向限制 

分 类 号：U116.2[交通运输工程]