灾害链中多资源应急调度模型与算法

Multi-resource emergency scheduling model and algorithm in disaster chain

灾害事故的应急资源调度是减少生命财产损失的有效手段.针对灾害链中多资源应急调度问题,建立了多资源多受灾点应急调度模型,设计了基于图论中网络优化和线性规划优化思想的启发式算法,并分析了算法复杂性.该算法根据应急资源在原生灾害和次生灾害中的需求对资源进行分类,对灾害链中都需要的公共应急资源,通过对模型线性松弛解的修正,降低问题的复杂性,减少算法的计算时间;而对原生或次生灾害中需要的应急资源,运用领域搜索方法寻找出救点,得到满意的资源调度方案.最后通过算例验证了算法的有效性和可行性,表明算法适合较大规模的计算,并能满足应用中的实时性要求.

Emergency resource scheduling of disasters and accidents is an effective means to reduce the loss of lives and property. This paper considers the multi-resource emergency scheduling problem in disaster chain. After the multi-resource and multi-disaster-place scheduling model is proposed, a novel heuristic algorithm is given based on~ network optimization in graph theory and linear programming optimization. The computational complexity of the algorithm is also analyzed. This algorithm divides the resources into different categories according to emergency resource demand in original and secondary disasters. For common emergency resources both disasters demand in disaster chain, this algorithm reduces the complexity and computation time of the problem by improving the linear relaxation solution of the model. For emergency resources the original or secondary disasters demand, this algorithm finds depots by local search method. Therefore the satisfactory resource scheduling solution is obtained. Finally, a numerical example is presented to show the effectiveness and feasibility of this algorithm. The algorithm is suitable for large-scale problems and meets the real-time requirement.