作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2023, Vol. 49 ›› Issue (6): 300-313. doi: 10.19678/j.issn.1000-3428.0064702

• 开发研究与工程应用 • 上一篇    下一篇

受灾路网抢修队动态调度问题的建模与求解方法

张国富1,2,3, 沈宇锋1, 宋晓晓1, 苏兆品1,2,3   

  1. 1. 合肥工业大学 计算机与信息学院, 合肥 230601;
    2. 合肥工业大学 工业安全与应急技术安徽省重点实验室, 合肥 230601;
    3. 安全关键工业测控技术教育部工程研究中心, 合肥 230601
  • 收稿日期:2022-05-16 修回日期:2022-06-30 发布日期:2022-08-30
  • 作者简介:张国富(1979-),男,教授、博士,主研方向为智慧应急;沈宇峰、宋晓晓,硕士研究生;苏兆品,副教授、博士。
  • 基金资助:
    教育部人文社会科学研究青年基金(19YJC870021);中央高校基本科研业务费专项资金(PA2021GDSK0073,PA2021GDSK0074);安徽省重点研究与开发计划项目(202104d07020001,202004d07020011);广东省类脑智能计算重点实验室开放课题(GBL202117)。

Method for Modeling and Solving the Dynamic Scheduling Problem of the Repair Crew for Restoring Damaged Road Network

ZHANG Guofu1,2,3, SHEN Yufeng1, SONG Xiaoxiao1, SU Zhaopin1,2,3   

  1. 1. School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230601, China;
    2. Anhui Province Key Laboratory of Industry Safety and Emergency Technology, Hefei University of Technology, Hefei 230601, China;
    3. Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education, Hefei 230601, China
  • Received:2022-05-16 Revised:2022-06-30 Published:2022-08-30

摘要: 地震、受灾路网抢修作为灾后应急响应中的一个基础环节,主要研究如何制定道路抢修队的修复方案,从而快速打通生命救援线路,确保救援队伍、装备、物资等及时输送到灾区各个需求点。然而,已有研究大多专注于静态受灾路网,难以适应地震、洪水等重特大自然灾害下的复杂应急场景。构建一种动态受灾路网模型,模拟应急场景的动态恶化,并基于Markov决策过程构建抢修队的动态决策模型,设计相应的状态空间、动作空间和回报函数。最后,提出一种基于改进Q学习(IQL)的动态调度(IQLDS)算法,以适应当前的路网状态,快速得到较优的修复策略。实验结果表明,与蚁群优化算法、IQL算法相比,IQLDS算法在大规模、高受损率路网环境中的目标函数值降低了约50%,能够在精确感知路网环境变化后及时调整学习策略,并充分利用历史经验获得较优的修复方案。

关键词: 灾后应急响应, 路网修复, 抢修队动态调度, Q学习, 最优动作集更新

Abstract: Restoring damaged road network is a basic part of post-disaster emergency response,and studies mainly focus on how to develop a restoration scheme for the repair crew to quickly open up a rescue route and ensure that the rescue teams,equipment,and relief supplies can be transported to the disaster area in a timely manner.However,most existing works focus on a static road network,which is difficult to adapt to the complex emergency scenarios in extraordinarily serious natural disasters,such as earthquakes and floods.A dynamic disaster road network model is constructed to simulate the dynamic deterioration of emergency scenarios.Based on the Markov decision process,a dynamic decision model for the emergency repair team is constructed,and a corresponding state space,action space, and return function are designed. Finally,an Improved Q-Learning(IQL)for Dynamic Scheduling(IQLDS) algorithm is proposed to adapt to the current state of the road network and quickly make better repair strategies.Experimental results show that,compared with Ant Colony Optimization(ACO) algorithm and the IQL algorithm,the value of the objective function obtained by our method for a large-scale and high-damage road network is reduced by approximately 50%.Furthermore,our method can adjust the learning strategy in a timely manner after accurately perceiving the changes in the road network and make full use of historical experience to obtain a better repair plan.These improvements may help emergency management departments facilitate a schedule plan for the repair crew for restoring a damaged road network more efficiently and effectively.

Key words: post-disaster emergency response, road network restoration, dynamic scheduling of the repair crew, Q-Learning(QL), optimal action set updating

中图分类号: