关键词: 关键词: 道路中断, 实时最短路径, 分类处理, 灾害救援

Abstract: Abstract: Aiming at the invalid real-time shortest path problem caused by abrupt road interruption during disaster rescue, a Fast Algorithm of Real-time Shortest Path(FARSP) was proposed. According to the FARSP strategy, the real-time new shortest path could be made out quickly when the vehicles got the sudden information of road interruption by judging and classifying the nodes into different categories and then dealing with them respectively according to various processing rules , which could avoid redundant calculations on the nodes and the sub-paths. Experiments with different cases of road nets were carried out which proved its correctness and efficiency. Compared with the standard results obtained by classical algorithm Dijkstra, the same rates of total length of the shortest path by FARSP and by Dijkstra are between 85% and 100%, and the deviation rates are 0-4%. The speed ratios of the proposed algorithm and Dijkstra algorithm increase significantly when network scale increase, with a maximum value of 24.2:1. Application of FARSP in disaster rescue with abrupt road interruption can get new real-time shortest path rapidly and has evident effect in reduing trasit time and improving the efficiency of disaster relief transportation.

Key words: Keywords: road interruption, real-time shortest path, classification processing, disaster rescue