道路突发中断情况下实时最短路径快速求解算法

Fast algorithm of real-time shortest path in case of emergent road interruption during disaster rescue

针对灾害救援中突发道路中断所导致原有最短路径失效的情况,提出一种实时最短路径快速求解算法FARSP。当车辆行驶在原定救援最短路径上,收到某些路径无法通行的突发信息时,根据所设计的求解策略,将节点进行判断并实现分类,依据多个不同的处理规则分别展开计算,减少了需要重新计算的节点和路径数量,快速求出新的最短路径。多个案例的仿真实验验证了算法的正确性、有效性,与经典算法Dijkstra所获得的标准结果比较,本算法最短路径总长度相同率达到85%～100%,总长度误差率为0～4%,而速度比随着网络规模的增大而显著增长,最大可达24.2∶1。应用该算法在道路突发中断情况下能够高效求得新的实时最短路径,有效减少灾害救援运输时间,提高救援效率,从而更好地实施应急救助。

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,the new real-time 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 to prove the correctness and efficiency of the algorithm.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 the network scale increases,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.