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

作     者：杜牧青 程琳 DU Muqing;CHENG Lin

作者机构：东南大学交通学院江苏南京210096 

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

出 版 物：《西南交通大学学报》 (Journal of Southwest Jiaotong University)

年 卷 期：2010年第45卷第2期

页      码：249-254页

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

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

学科分类：08[工学] 0823[工学-农业工程类] 

核心收录：

D　O　I：10.3969/j.issn.0258-2724.2010.02.015

馆 藏 号：203150198...