| 考虑转向延误的最短路径的节点标号算法 |
| |
| 引用本文： | 雒应,何强.考虑转向延误的最短路径的节点标号算法[J].重庆交通大学学报(自然科学版),2021,40(4):48-53. |
| |
| 作者姓名： | 雒应 何强 |
| |
| 作者单位： | 长安大学 公路学院,陕西 西安710064 |
| |
| 摘 要： | 拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况.分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法.对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n2)优化为O(nlogn),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证.结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降.
|
| 关 键 词： | 交通工程 道路交通 最短路径算法 转向延误 Dijkstra |
Node Labeling Algorithm of Shortest Path Considering Turn Delay |
| |
| LUO Ying,HE Qiang.Node Labeling Algorithm of Shortest Path Considering Turn Delay[J].Journal of Chongqing Jiaotong University,2021,40(4):48-53. |
| |
| Authors: | LUO Ying HE Qiang |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
