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

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.