没有合适的资源?快使用搜索试试~ 我知道了~
基于Q学习的受灾路网抢修队调度问题建模与求解.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 182 浏览量
2023-02-23
16:51:14
上传
评论
收藏 359KB DOCX 举报
温馨提示
试读
17页
基于Q学习的受灾路网抢修队调度问题建模与求解.docx
资源推荐
资源详情
资源评论
伴随着全球气候变化以及我国经济快速发展和城市化进程不断加快, 我国的资源、环
境和生态压力日益加剧.各类自然灾害多发频发, 给我国经济和商业社会造成的损害也日益
严重
[1-2]
.仅在"十二五"期间, 年均造成 3.1 亿人次受灾, 因灾死亡失踪 1 500 余人, 紧急转移
安置 900 多万人次, 倒塌房屋近 70 万间, 农作物受灾面积 2 700 多万公顷, 直接经济损失达
3 800 多亿元.为此, 国务院在《"十三五"国家科技创新规划》和《国家综合防灾减灾规划
(2016--2020 年)》中明确提出了"要提高防灾减灾救灾工作规范化、现代化水平, 强化科技
创新, 有效提高防灾减灾救灾科技支撑能力和水平".
在灾害应急响应中
[3-4]
, 及时修复受损路网、打通生命通道是开展灾后救援工作的一个
重要环节
[5]
.主要研究如何利用智能决策理论和计算机辅助工具规划道路抢修队的调度, 即
如何修复路段、修复哪些路段可以使得路网的修复时间最小、运输效率最大, 这对应急救
援的实施和灾民的快速安全疏散具有重要的现实意义.因此, 近年来, 灾后路网的修复问题
越来越受到各国政府和学者的重视和关注
[6]
.
Chen
[7]
将应急抢修的后勤保障调度构建为一个整数多商品的网络流问题, 并设计了一
种基于问题分解和变量固定技术的启发式算法, 可在约束的运营时间内降低后勤保障的短
期运营成本.霍建顺
[8]
针对道路抢修的不确定性, 基于模糊机会约束规划和模糊比较排序确
定震后道路抢修排程. Nurre 等
[9]
针对在极端破坏下的基础设施系统恢复服务的问题, 提出了
一种新的启发式调度规则用来分配工作组将节点和弧建立到网络中, 以最大限度地提高网
络中的累积加权流量.但是, 这种路网修复是以增加新的点和边为代价, 成本较大.
Yan 等
[10-11]
基于应急抢修和救灾物资分配的双层时空网络, 将道路抢修和物资分配构
建为一个多目标、混合整数、多商品的网络流问题, 并引入蚁群优化搜索最优抢修、物资
分配路线和时间表.花丙威等
[12]
基于灾后路网状态识别提出了路网脆弱性评价指标, 并构建
了基于路网脆弱性和路径出行费用的双层规划模型.邱慧
[13]
将灾后公路网修复分为应急修复
期和全面修复期, 在时间和设备资源的约束下, 构建了基于最大连通子图的大小和公路网加
权效率的两阶段模型. Aksu 等
[14-15]
研究灾后道路障碍清理规划问题, 提出了一个基于动态路
径的数学模型来识别道路阻塞的临界性, 并以有限的设备资源清除路上障碍, 随后设计了一
个相应的启发式方法, 以最大化整个路网的连通性和最小化路障清理时间. Kasaei 等
[16-17]
基
于弧路由问题来规划灾后道路的障碍清除, 设计了基于整数规划和启发式的混合算法以最
小化路网重新连通的时间开销或在给定的时间约束内最大化路网重新连通后的的总收益.不
过, 上述方法均是着眼于路网本身, 构建的路网大都过于理想化, 仅考虑修复路网中的哪些
路段可以实现目标的最优化, 而没有考虑这些受损路段是否可达和修复工程队的在危险环
境中的路线问题, 也没有考虑受损路段的修复顺序对应急救援的影响.
李爱庆
[18]
基于用多目标的受损道路抢修与紧急物资配送的混合整数多重网络规划模型
求解各受损道路的抢通时间, 各个工作队的抢修路径. Duque 等
[19]
从道路抢修队(包含人员、
设备和原材料等)自身的视角出发, 针对灾后道路抢修队的调度和路线规划问题, 提出了一
个较为完整的数学模型, 不仅考虑了应该修复哪些受损边, 还考虑了修复时间和修复路线的
影响, 并基于动态规划(Dynamic programming, DP)和贪婪策略优化路网中那些需要救援的
地点的可达性. Kim 等
[20]
考虑额外损失和可变损失率等灾害因素下的道路抢修队调度问题,
以尽量减少因受灾点不可达而造成的总损失.上述工作虽然考虑了抢修队的调度路径, 并能
够给出道路抢修队的修复策略集, 但在其数学模型中, 应急需求点和受损路段均是以受损节
点来表示, 不能明确表现路网结构, 也不利于系统演示.此外, Duque 等
[19]
提出的 DP 算法是
通过每一步的贪婪策略选择局部最优的行为来逐步达到全局最优, 因此, 其算法往往容易陷
入局部最优解而无法跳出.
基于上述背景, 本文在整理和分析已有工作的基础上, 首先, 构建了考虑连续受损路段
的抢修队调度和路线规划问题的数学模型; 然后, 基于马尔科夫决策过程
[21]
来模拟抢修队的
修复活动, 并基于 Q 学习算法
[22]
求解道路抢修队的最优调度策略; 最后, 通过对比实验验证
了本文方法的有效性.
1. 问题描述
考虑如下路网 G={V,E}G={V,E}, VV 为 GG 中的道路节点序号集合, E=V×VE=V×V 为
GG 中的所有路段的集合.
如图 1 所示, VV 中包含一个救援物资的储备点序号和 n∈Nn∈N 个需求节点的序号.
不失一般性, 我们用节点"0''表示储备点, 用 V∗={1,2,⋯,n}V∗={1,2,⋯,n}表示需求节点的集合
(所有的非需求节点已经从路网中剔除), 则 V=V∗∪{0}V=V∗∪{0}. ∀i∈V∗∀i∈V∗为一个急需
救援的应急点, 代表某城市、村庄或社区等.在实际的灾害应急响应中, 由于每一个应急点
的受灾程度不同, 对救援需求的迫切性也不同.因此, 我们用 Ii∈RIi∈R 表示和区分每个应急
点 ii 的受灾程度.
图 1 受损路网示意图
Fig. 1 Schematic diagram of the damaged road network
下载: 全尺寸图片 幻灯片
在应急这个特殊场景中, EE 中的每条路段 eij∈E,∀i,j∈Veij∈E,∀i,j∈V 是双向通行的,
且每条路段 eijeij 有一个长度 lij∈Rlij∈R.此外, 我们用 ξij∈{0,1}ξij∈{0,1}来表示每条路段
eijeij 是否是畅通的.如果 ξij=1ξij=1, 则路段 eijeij 是可通行的; 否则, eijeij 目前为一条受损
路段.基于此, EE 可以划分为如下两部分: Ec={eij|eij∈E,ξij=1,∀i,j∈V}Ec={eij|eij∈E,ξij=1,∀i,j
∈V}为 EE 中所有可通行路段的集合; Er={eij|eij∈E,ξij=0,∀i,j∈V}Er={eij|eij∈E,ξij=0,∀i,j∈V}
为 EE 中所有受损路段的集合.显然, E=Ec∪ErE=Ec∪Er.
如果路网 GG 中任一节点 ii 到任一节点 jj 之间是可通行的, 则我们用 Dij∈RDij∈R 表
示节点 ii 到节点 jj 之间的最短路径的长度, 可由经典的 Dijkstra 算法
[23]
根据每条路段的长度
计算得到.特别的, Di0Di0 为应急点 ii 到储备点 0 的最短路径的长度.需要注意的是, 救援工
作必须在一定的时限内完成, 比如黄金救援 72 小时等.因此, 对于每个应急点 i∈V∗i∈V∗,
有一个最大可接受距离 Di∈RDi∈R 的约束.基于此, 我们用 δi∈{0,1}δi∈{0,1}来表示储备点
0 到应急点 ii 是否可达.如果储备点 0 到应急点 ii 是连通的, 而且其距离 Di0≤DiDi0≤Di, 则
ii 是可达的, δi=1δi=1; 如果储备点 0 到应急点 ii 是不连通的, 或者即使储备点 0 到应急点
ii 是连通的, 但 Di0>DiDi0>Di, ii 是不可达的, δi=0δi=0, 因为将会错过应急点 ii 的最佳救援
时间.
道路抢修队(包含人员、设备和原材料等)将从储备点 0 出发对受损路网进行一系列的
修复活动, 以使储备点 0 到各个应急点 i∈V∗i∈V∗都是可达的.抢修队在高速路和山路的前
进速度显然是不一样的, 和已有工作一样
[19]
, 假设抢修队在各种路段上的平均前进速度为
v∈Rv∈R, 修复任一受损边 eij∈Ereij∈Er 的时间开销为 tij∈Rtij∈R, 则抢修队在任意一条路
段 eij∈Eeij∈E 上的时间开销 cij∈Rcij∈R 为
cij=⎧⎩⎨lijv,lijv+tij,ξij=1ξij=0cij={lijv,ξij=1lijv+tij,ξij=0
(1)
注意, 如果 eijeij 是受损路段, 那么 eijeij 在被修复后应该更新 ξij←1ξij←1.
抢修队一个完整的修复和路线规划可以用向量 HH=⟨ei1j1,⋯,eikjk⟩HH=⟨ei1j1,
⋯,eikjk⟩ (k∈Nk∈N)来表示.例如, 图 1 中的抢修队修复和路线规划为
HH=⟨e02,e23,e36,e63,e35,e51,e14⟩HH=⟨e02,e23,e36,e63,e35,e51,e14⟩.不同的 HHHH 构成一个
修复规划集 Θ={HH1,⋯,HHm}Θ={HH1,⋯,HHm} (m∈Nm∈N), 满足
|Θ|=∑i=0|Er|P(Er,i)|Θ|=∑i=0|Er|P(Er,i)
其中, P(Er,i)P(Er,i)为从受损路段集 ErEr 中挑选 ii 条路段的排列数.
对于一个可能的修复规划 HH∈ΘHH∈Θ, 首先需要考虑救灾物资的运输效率, 要求每
个应急点 i∈V∗i∈V∗到储备点 0 的距离要尽可能短, 即
minf1(HH)=∑∀i∈V∗(Di0⋅Ii)minf1(HH)=∑∀i∈V∗(Di0⋅Ii)
(2)
其中, Di0Di0 为在修复规划 HHHH 下的应急点 ii 到储备点 0 的最短路径长度, 例如,
图 1 中, D40=l01+l14D40=l01+l14, D90=l02+l23+l36+l69D90=l02+l23+l36+l69.受灾程度 IiIi
起到了一个偏好的作用, 对于受灾较严重的应急点 ii, 输送距离 Di0Di0 要尽可能的短.此外,
还需要考虑路网的修复效率, 要求每个应急点 i∈V∗i∈V∗要尽可能快地与储备点 0 连通, 以
尽快打通生命通道, 即
minf2(HH)=∑∀i∈V∗(Ci0⋅Ii)minf2(HH)=∑∀i∈V∗(Ci0⋅Ii)
(3)
其中, Ci0∈RCi0∈R 为在修复规划 HHHH 下, 应急点 ii 与储备点 0 连通时抢修队的累
积时间开销, 可由式(1)计算得到.例如, 在图 1
中, C20=l02/v+t02C20=l02/v+t02, C40=(l02/v+t02)+(l23/v+t23)+(l36/v+t36)+(l36/v)+(l35/v
)+(l15/v+t15)+(l14/v+t14)C40=(l02/v+t02)+(l23/v+t23)+(l36/v+t36)+(l36/v)+(l35/v)+(l15/v+t1
5)+(l14/v+t14).
基于上述考虑, 抢修队的修复和路线规划可描述为如下的约束优化问题:
{minf(HH)=λ⋅f1(HH)+(1−λ)⋅f2(HH)s. t.Di0≤Di,∀i∈V∗{minf(HH)=λ⋅f1(HH)+(1−λ)⋅f2(HH)s. t.Di0≤Di,∀i∈V∗
(4)
其中, λ∈(0,1)λ∈(0,1)为加权因子, 控制着 f1f1 和 f2f2 在整体应急响应目标中的偏好.
2. 马尔科夫决策模型
从前面的描述可以明显的看出, 抢修队的修复和路线规划是一个典型的序贯决策, 而
且具有部分随机、部分可由决策者控制的动态特征, 这与马尔可夫决策过程(Markov
decision process, MDP)
[21, 24-25]
具有天然的契合性.因此, 我们从道路抢修队的视角出发, 把抢
修队看成是一个智能体(agent)
[26]
, 而受损路网即是这个 agent 待感知的环境, 基于马尔可夫
决策型来描述 agent 的决策过程.
如图 1 所示, agent 从储备点 0 出发, 沿着某一方向前进, 并决定是否修复受损路段
eijeij, agent 的动作空间 AA 即为受损路段集合 ErEr, 即 A=ErA=Er.显然, AA 是有限的. agent
的状态由三元组 S=⟨V,D,E⟩S=⟨V,D,E⟩组成.其中, V={i|δi=1,∀i∈V∗}V={i|δi=1,∀i∈V∗}为已经
可达的应急点列表; D={⟨i,Di0⟩|δi=1,∀i∈V∗}D={⟨i,Di0⟩|δi=1,∀i∈V∗}为已经可达的每个应急
点 ii 到储备点 0 的最短路径长度列表; E={eij|ξij=1,eij∈Er}E={eij|ξij=1,eij∈Er}为已经修复的
受损路段列表.当 agent 决定并修复受损路段 eijeij 后, ξij←1ξij←1, agent 将确定 jj 是否可达
并更新⟨V,D,E⟩⟨V,D,E⟩, 然后将 eijeij 从动作空间 AA 中剔除继续前进.例如, 在图 1 中, agent
的初始状态为⟨{1},{⟨1,l01⟩},∅⟩⟨{1},{⟨1,l01⟩},∅⟩, 动作空间为
{e02,e23,e36,e56,e15,e14}{e02,e23,e36,e56,e15,e14}, 在执行动作 e02e02 后状态为
⟨{1,2},{⟨1,l01⟩,⟨2,l02⟩},{e02}⟩⟨{1,2},{⟨1,l01⟩,⟨2,l02⟩},{e02}⟩, 动作空间为
剩余16页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3632
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功