考虑转向延误的最短路径的节点标号算法  

Node Labeling Algorithm of Shortest Path Considering Turn Delay

作　　者：雒应[1] 何强 LUO Ying;HE Qiang(School of Highway,Chang an University,Xi an 710064,Shaanxi,China)

机构地区：[1]长安大学公路学院,陕西西安710064

出　　处：《重庆交通大学学报（自然科学版）》2021年第4期48-53,共6页Journal of Chongqing Jiaotong University(Natural Science)

摘　　要：拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况。分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法。对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n^(2))优化为O(n log n),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证。结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降。It is difficult to reflect the real traffic situation when the shortest path algorithm is applied without considering the turn delay in urban road network,because that travel delays at the intersection of urban road network may be larger than the driving time on road section.The existing shortest path algorithm considering turn delay was analyzed.The extension network method lacked practicability due to the excessive time and space overhead.The other algorithms,including dual network method,node labeling algorithm and arc labeling algorithm,were essentially to solve the shortest path problem including node weight and edge weight,and the final solution was node labeling algorithm.The typical node labeling algorithm—Dijkstra algorithm was improved.The steering discrimination was completed by recording the node s previous node,the time complexity of the proposed algorithm was optimized from O(n^(2))to O(n log n)by smallest heap optimization and the data structure of the proposed algorithm was given.The program coding was completed,and the proposed algorithm was validated through an example.The results show that the shortest path of the urban road network will change after considering turn penalties,meanwhile,the time complexity of the algorithm will decrease after heap optimization.

关 键 词：交通工程 道路交通 最短路径算法 转向延误 DIJKSTRA 

分 类 号：U491[交通运输工程—交通运输规划与管理]