基于混合蛙跳的路网应急车辆动态最短路径

Dynamic Shortest Paths of Emergency Vehicles in Expressway Network Based on Shuffled Frog Leaping Algorithm

针对路网离散动态特性,提出一种求解应急车辆最短路径的混合蛙跳算法.首先设计一种随机编码方案,并引入节点时间度概念对编码方案进行了改进.然后,提出一种逆向标记迭代策略,通过对比优势族群与劣势个体的进入节点时刻和路段行程时间,促使车辆在最佳时刻进入最短路段.最后,以北京市东城区和朝阳区路网为例,将服从正态分布的动态路段行程时间作为权值,对算法进行了验证.验证结果表明,所提混合蛙跳算法能在1 s内求得最短路径,基于节点时间度编码方案的混合蛙跳算法较随机编码方案计算速度提高一倍,平均计算准确率提高4.3%.

Considering the discrete dynamic characteristic of the expressway network, a novel shuffled frog leaping algorithm is proposed to solve the shortest paths of emergency vehicles. In this paper, a random coding scheme is designed firstly, and then the concept of node travel time degree is introduced to improve the coding scheme. Then a backward marking update rule is put forward. The entering node moment and the link travel time of the worst individual are compared with those of the advantaged group, and the update rule makes the vehicle enter a shorter road section at the earlier time. Finally, the dynamic link travel time distributed in a normal is used as the weights, and the algorithm is verified by the example of expressway network of Dong Cheng District and Chao Yang District in Beijing. The results show that the proposed shuffled frog leaping algorithm can search the shortest path in one second. The calculation speed of the algorithm based on node travel time degree is raised by 100% comparing to the random coding scheme, and the average accuracy rate of the former is raised by 4.3% comparing to the latter.