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

详细信息   全文下载|推荐本文 |

• 出版年：2010
• 作者：杜牧青；程琳
• 单位1：东南大学交通学院
• 出生年：1986
• 学历：博士研究生
• 语种：中文
• 作者关键词：最短路径；拍卖算法；交叉口延误；转向限制
• 起始页：249
• 总页数：6
• 经费资助：国家973计划资助项目（2006CB705500）；国家高技术研究发展计划（2007AA11Z205）；国家自然科学基金（50578037）
• 刊名：西南交通大学学报
• 是否内版：否
• 刊频：双月刊
• 创刊时间：1954
• 主管单位：中华人民共和国教育部
• 主办单位：西南交通大学
• 主编：翟婉明
• 地址：中国、成都
• 邮编：610031
• 电子信箱：xbz@home.swjtu.edu.cn
• 网址：http://journal.swjtu.edu.cn
• 卷：45
• 期：2
• 期刊索取号：P860.6 210
• 数据库收录：EI Compendex收录期刊；中文核心期刊；中国科技论文统计源期刊；中国科学引文数据库来源期刊；德国数学文摘（Zbl MATH)收录期刊
• 核心期刊：中文核心期刊

摘要

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