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

• 作者: 杜牧青 程琳
• 来源期刊: 西南交通大学学报
• 学科: 交通运输
• 关键词: 最短路径 拍卖算法 交叉口延误 转向限制
• 年，卷（期）: 2010,（2）
• 页码范围: 249-254
• 页数: 6页
• 分类号: ULL6.2
• 字数: 4476字
• 语种: 中文
• DOI: 10.3969/j.issn.0258-2724.2010.02.015

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杜牧青	东南大学交通学院	2	9	1.0	2.0
2	程琳	东南大学交通学院	118	1369	22.0	30.0