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

摘要

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