一种面向严重受损路网的抢修队调度算法

受损路网抢修是灾害应急响应中的一个非常重要的基础环节,主要研究如何对道路抢修队进行有效调度,以快速恢复受灾路网的交通能力,为后续顺利展开应急救援工作提供有效的保证.已有方法在路网受损严重的情形下往往难以给出有效的调度策略.为此,在已有工作的基础上,简化路网模型和决策模型,并基于动作集裁减和Q学习设计一种面向严重受损路网的抢修队调度算法.在该算法中,抢修队只能从当前可达的未修复受损路段集合中选择下一个动作,以确保Q学习的连续性.仿真实验结果表明,在节点数和受损率都较大的严重受损路网环境中,所提算法可以保证所有需求节点均可达,具有更高的稳定性和可靠性,且能够在更小的时间和修复代价内给出更优的调度方案.

An algorithm for repair crew scheduling on severely damaged road network

Repairing the damaged road network is one of the most important and basic parts of disaster emergency response. It mainly deals with how to effectively dispatch the repair crew to quickly restore the traffic capacity of the damaged road network and provide an effective guarantee for the smooth implementation of the subsequent emergency rescue. However, when the road network is severely damaged, the existing algorithms often fail to find a feasible solution. Therefore, this paper first simplifies models of damaged road network and decision-making on the basis of the existing work. Then, an improved algorithm for repair crew scheduling on severely damaged road network is developed according to Q-learning and action set reduction. Particularly, in the proposed algorithm, the repair crew can only choose the next action from the set of current damaged road sections which are unrepaired but reachable, ensuring the continuity of Q-learning. Finally, simulation results show that the proposed algorithm can ensure that all demand nodes are reachable, has higher stability and reliability, and can obtain better scheduling schemes at lower time and repair cost, even if the road network has been seriously damaged with a great number of damaged nodes and a big damage rate.