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

An algorithm for repair crew scheduling on severely damaged road network

作　　者：张国富[1,2,3] 涂冰花 苏兆品[1,2,3] 岳峰[1,2] ZHANG Guo-fu;TU Bing-hua;SU Zhao-pin;YUE Feng(School of Computer Science and Information Engineering,Hefei University of Technology,Hefei 230601,China;Anhui Province Key Laboratory of Industry Safety and Emergency Technology,Hefei University of Technology,Hefei 230601,China;Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education,Hefei 230601,China)

机构地区：[1]合肥工业大学计算机与信息学院,合肥230601 [2]合肥工业大学工业安全与应急技术安徽省重点实验室,合肥230601 [3]安全关键工业测控技术教育部工程研究中心,合肥230601

出　　处：《控制与决策》2021年第7期1663-1671,共9页Control and Decision

基　　金：国家自然科学基金项目(61573125);中国工程院战略咨询重点项目(2020-XZ-3);教育部人文社会科学研究青年基金项目(19YJC870021,18YJC870025);中央高校基本科研业务费专项资金项目(PA2019GDQT0008,PA2019GDPK0072)。

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

关 键 词：灾害应急响应 受损路网抢修 严重受损路网 抢修队调度 Q学习 动作集裁减 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]