| 考虑交叉口转向延误的最短路径拍卖算法 |
| |
| 引用本文： | 杜牧青,程琳.考虑交叉口转向延误的最短路径拍卖算法[J].西南交通大学学报,2010,45(2). |
| |
| 作者姓名： | 杜牧青 程琳 |
| |
| 作者单位： | 东南大学交通学院,江苏南京,210096 |
| |
| 基金项目： | 科技部科研项目，国家高技术研究发展计划(863计划)，国家自然科学基金 |
| |
| 摘 要： | 为了改进传统算法求解最短路径时运算量大且无法计算交叉口转向延误的不足,提出可直接求解受限路网中两点之间最短路径的改进拍卖算法.将价格矢量扩展至二维,解决了价值量被不同转向行为共用的问题.设计了节省存储空间的数据存储结构,可准确描述交叉口转向行为,且便于检索.针对不同规模和密度的随机路网,比较了改进算法和Dijkstra算法求解单一起、终点之间的最短路径问题.结果表明,在含5 000个结点、20 000条路段的高密度路网中,改进拍卖算法的搜索时间约为Dijkstra算法的30%,能准确求解受限路网中的最短路径,并保留了原Auction算法可并行计算的基本性质.
|
| 关 键 词： | 最短路径 拍卖算法 交叉口延误 转向限制 |
Auction Algorithm for Shortest Paths in Road Networks Considering Delays for Intersection Movements |
| |
| DU Muqing,CHENG Lin.Auction Algorithm for Shortest Paths in Road Networks Considering Delays for Intersection Movements[J].Journal of Southwest Jiaotong University,2010,45(2). |
| |
| Authors: | DU Muqing CHENG Lin |
| |
| Institution: | DU Muqing,CHENG Lin(School of Transportation,Southeast University,Nanjing 210096,China) |
| |
| Abstract: | 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 ... |
| |
| Keywords: | shortest paths auction algorithm intersection delay turning restriction |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
