IEEEJAS的个人博客分享 http://blog.sciencenet.cn/u/IEEEJAS

博文

基于Q学习的受灾路网抢修队调度问题建模与求解

已有 234 次阅读 2020-10-12 16:59 |系统分类:博客资讯

近年来,各类突发事件发生得越来越频繁,各类突发事件在世界各地造成了大量人员伤亡和巨大的经济损失。 


虽然突发事件常常是不可避免的,但是,人们可以通过某些技术手段,或措施对突发事件进行应急管理,在相当程度上减轻灾害事件造成的巨大损失和心灵创伤。 


应急管理中修复受损的道路交通网络,使得受灾人员能够及时得到救助,同时满足将部分受灾人员进行安全转移等任务的需求,这是应急管理中不可或缺的重要一环。 


这篇论文研究了如何利用智能决策理论和计算机辅助工具为道路抢修队的修复决策提供规划方案。



抢修队的修复工作需要满足两个目标,第一个目标是,在尽可能小的时间开销上使道路网通畅;第二个目标是,对道路网修复后,在保证路网通畅下,使运输效率尽可能高。


我们建立了路网抢修队的修复决策模型,并提出了求解模型的算法,最终生成了合理高效的修复方案。


image001.png


目前的研究存在一些不足:主要体现在两个方面:首先,已有的工作着眼于路网本身,构建的路网大都过于理想化,仅考虑修复路网中的哪些路段可以实现目标的最优化,而没有考虑这些受损路段是否可达和修复工程队在危险环境中的路线问题,也没有考虑受损路段的修复顺序对应急救援的影响。其次,虽然考虑了抢修队的可达路线,并能够给出道路抢修队的修复策略集,但无法处理像地震、洪水等特大自然灾害所引起的连续路段受损情形。

 

这篇论文通过强化学习从另一个角度研究了这个问题。首先把这个问题建模为马尔可夫决策过程,然后再利用Q学习方法求解。主要基于这几个考虑:部分可观测状态、延迟回报、探索和利用。


部分可观测状态

主要是指抢修队只能观测到一部分路网的信息。一开始,抢修队无法获取路网环境的全部信息,并且路网中存在影响路网结构的非需求节点后,这种不确定性会增加。抢修队可能要综合考虑以前的观察以及当前的状态以选择动作。


延迟回报

主要是指在路网修复规划问题中,就是寻找一系列最优的修复行为。但是,在修复连续受损的路段时,抢修队可能要连续修复一系列路段后才能看到路网的连通性明显变化。


探索和利用

抢修队在与环境交互的过程中,面临一个权衡过程:是选择探索未知的状态和动作,还是选择利用它已经学习过、会产生高回报的状态和动作。


image002.png

(a) 路段受损率较小,路网规模逐渐增加


image003.png

(b)路段受损率较大,路网规模逐渐增加


image004.png

(c) 路网规模和路段受损率均较大、最大可授受距离逐渐增加


图2 两种算法的修复路段数和应急点可达率


这篇论文主要对比了动态规划方法和Q学习方法用于求解规划方案。在路段受损率较小时, 随着路网规模的增加, Q-learning算法和DP算法均可以使所有应急点可达, 且最终修复的路段数也一样. 在路网修复初期, DP算法可以使更多的应急点可达. 但随着修复过程的推进, Q-learning算法很快就赶上并且超过了DP算法, 这是因为在Q-learning算法中,抢修队牺牲了一部分的短期回报来获取更好的长期回报.


在路段受损率较大时, 随着路网规模的增加, Q-learning算法要明显比DP算法更优. Q-learning算法在路网修复整个阶段都能使更多的应急点可达, 并直至使所有应急点都可达, 且最终修复的路段数也多于DP算法. 因此,在灾情较严重时, 与DP算法相比, Q-learning算法所给的抢修队规划方案能够更快的使更多的应急点可达. 也就是说, Q-learning算法能够更快的使路网交通系统恢复程度最大, 更有利于应急救援的实施和灾民的快速安全疏散.在路网规模和路段受损率都较大时, 无论应急点最大可接受距离变大还是变小,仍然只有Q-learning能够使所有应急点可达, 且修复了更多的路段. 而DP算法随着最大可接受距离的变小, 应急点可达率越来越小.


因此, 当距离约束要求发生变化时, Q-learning更加鲁棒, 能够统筹考虑受损路网的全局, 会随着距离约束要求的变化从全局和长期收益的角度让抢修队重新适应这些约束的变化. 与之明显不同的是, 当距离约束要求变化时, DP算法不能做出相应的调整, 尤其在约束苛刻时, DP算法可能会找不到任何有效规划.


引用格式:苏兆品, 李沫晗, 张国富, 刘扬. 基于Q学习的受灾路网抢修队调度问题建模与求解. 自动化学报, 2020, 46(7): 1467-1478

文章链接:http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180081



作者简介


苏兆品

合肥工业大学计算机与信息学院副教授. IEEE 会员. 2008 年获得合肥
工业大学计算机科学与技术专业博士学位. 主要研究方向为演化计算, 灾害应急决策, 多媒体安全.

E-mail: szp@hfut.edu.cn


李沫晗

合肥工业大学计算机与信息学院硕士研究生. 2014 年获得合肥工业大
学光信息科学与技术专业学士学位. 主要研究方向为灾害应急决策和强化学习.

E-mail: limohan@mail.hfut.edu.cn


张国富

合肥工业大学计算机与信息学院教授. 中国自动化学会、 IEEE 会员.2008 年获得合肥工业大学计算机科学与技术专业博士学位. 主要研究方向为计算智能, 多 agent 系统, 基于搜索的软件工程. 本文通信作者.

E-mail: zgf@hfut.edu.cn


刘  扬

合肥工业大学计算机与信息学院博士研究生. 2005 年获得合肥工业大学通信工程专业学士学位, 2007 年获得合肥工业大学信号与信息处理专业硕士学位. 主要研究方向为灾害应急决策和演化计算.

E-mail: lyy673@163.com




http://blog.sciencenet.cn/blog-3291369-1254109.html

上一篇:科研必备!盘点常用文献管理工具
下一篇:基于一致性敏感哈希块匹配的HDR图像去伪影融合方法

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-27 19:55

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部