考虑需求满意度与救援时间公平的应急物资调度多目标模型及算法
时间：2022-12-10 16:50:03 来源：雅意学习网 本文已影响 人 
王付宇， 谢昊轩， 汤 涛
(1.安徽工业大学管理科学与工程学院 安徽 马鞍山 243032；
2.安徽工业大学复杂系统多学科管理与控制安徽普通高校重点实验室 安徽 马鞍山 243002)
突发性灾难发生初期，应急物资的需求往往要大于救援中心的可供应量，决策者在制作救援物资分配方案时，需要同时考虑灾区人民的满意度最大化与救援时间长短的嫉妒心理[1]。如果不能获得灾区人民对救援方案的支持，那么对灾区的救援工作将会产生极大的阻碍，容易使灾区人民的情绪不稳定，对灾区人民造成心理伤害，严重时，造成死伤人数进一步增加[2]。
关于应急物资调度的研究已有很多成果，早期的研究主要以成本最小化、时间最短等为目标来制定应急物资分配方案。例如，于小兵等[3]针对应急事件的特点，建立了总运输成本最小、延误时间最小的多目标模型，利用范数理想点法将其转换成单目标问题进行研究；
王海军等[4]针对大规模突发事件的应急调度问题，构建了总物流时间和应急成本为目标的多目标非线性整数规划模型，通过对两个目标的动态赋权，提高了模型柔性。如今，许多学者开始考虑灾民心理[5]，以需求满意度、时间满意度、需求满足率、物资分配的公平性等目标来进行研究。例如，宋晓宇等[6]以调度总成本最小与整体反应时间最早为目标，构建了由受灾点、救援中心与储备中心组成的应急调度模型。陈刚等[7]构建了总加权嫉妒值最小与总物流成本最小的多目标应急物资调度模型，以各灾点需求量占总需求量的比例为权重来分配物资，设计改进的非支配排序遗传算法来求解冲突帕累托解。Jincheng等[8]把时间、路径可行性加入模型中，提出一种带有车辆调度的应急物资模型来解决物资调度问题，但未考虑应急物资的分配公平性和成本控制。张力丹等[9]以应急调度救援成本和救援的不及时造成的损失为目标构建多目标数学模型，利用遗传算法求解此类大型应急调度问题。王付宇等[10]针对地震后的应急物资配送问题，建立了以总救援时间最短和相对综合救援权重值最大的多目标数学规划模型。王飞跃等[11]考虑物流成本与系统损失，建立了基于路况的最小化救灾行动的成本和最大化有限救灾资源分配的多目标应急资源配置模型。王旭坪等[12]量化灾区人民的不理智攀比心理，为了体现分配的公平性，建立了攀比目标函数。
以上文献虽然将灾民满意度与时间满意度以及公平性等目标考虑到模型里面，但是公平分配只针对物资分配量的公平，没有考虑分配物资时间方面的公平。并且，关于灾民的需求满意度的研究，仅与本受灾点物资分配量有关，没有考虑到灾民的满意度和本受灾点物资分配量以及其他受灾点物资分配量都有关系，也没有将道路异质性与灾区异质性等特点考虑到所建立的模型之中。
综上所述，目前已有部分学者对应急物资需求满意度与救援时间方面作为目标来进行研究，但是成果较少。本文研究利用人们具有攀比心理来定义灾民的满意度与时间分配公平函数，本文在现有文献研究基础上，以本受灾点物资需求满足程度与其他各个灾点的物资满足程度相比较，从而得出本受灾点的需求满意度，以本受灾点物资分配时间和其他受灾点物资分配时间的比较来体现时间上的分配公平。本文研究与之前文献的研究不同在于：(1)本文的灾民需求满意度是通过各个灾点物资分配量的比较而计算得出；
(2)利用各个灾点的救援时间的比较来构造分配时间公平函数，且将灾区异质性与道路异质性考虑到模型里，构建了多目标应急调度模型；
(3)由于标准萤火虫算法不适用于多目标求解，本文设计了改进的非支配排序萤火虫算法来对模型进行求解研究。
灾难爆发后初期，由于应急物资的供不应求，如何对各个受灾区进行合理的救援物资分配，有利于安抚灾区人民[13]，以防伤员的人数进一步增加。由于人具有攀比的心理，人们在获得援助时，不可避免地要关注别人所获得的是否比自己获得的要多得多，鉴于这种心理，考虑本受灾点物资分配量与其他受灾点物资分配量，以温国峰[14]综合考虑疫区民众的时间风险感知、物资满足率以及公平感知，建立动态分配模型为例，在此基础上构建了灾民物资满意度目标函数和应急物资调度时间公平函数。
1.1 灾民满意度
Ri=riδi
(1)
(2)
(3)
1.2 差异化时间指标获得
在应急调度中，每个灾区都希望自己能尽快得到物资的援助，决策者在分配物资时，应该考虑到各个灾点接受首批物资的总时间长短。影响救援中心到达灾区的时间因素有很多[15]，主要包括道路的通行可靠性πh(h为道路总数目)、道路受灾程度ρh、道路周边基础设施资源αh等。本文借鉴文献对影响时间的各个指标进行数据搜集，衡量道路受灾程度，考虑道路所在区域的伤亡人数与经济损失等；
衡量道路通行可靠性时，综合运用一些方法来评估道路的可行性；
衡量道路周边基础设施资源时，利用道路所属区域的基础设施竞争力指数来评估。
按照影响因素对时间距离的影响作用分为正向(ρh)与反向(πh、αh)。为了去除量纲，将正向指标与反向指标按照下式进行变换
(4)
(5)
r+=1,2,…,Z+;r-=1,2,…,Z-;h=1,2，…，n×m
(6)
Q′(hr+)、Q′(hr-)分别表示路径h第r个正、负方向指标上的处理数据，Q(hr+)、Q(hr-)分别表示路径h第r个正、负方向指标上的原始数据，Z+、Z-表示正、负方向指标的个数。将处理后的数据进一步平均化，以平均化后的指标作为时间差异化的度量指标。
(7)
1.3 时间公平
当物资调度时间差别太大，会影响部分灾民的救助，物资调度的时间公平需要保障。tik表示救援中心k与灾点i的时间距离，Tij={Ti-Tj}，Tij表示灾点i与灾点j比较时的救援时间满意度，Ti、Tj分别表示灾点i和j救援时间偏度。由于种种因素的影响，定义救援中心到达灾点i的最小救援时间Tip为参照点，Tip=min{tikLh,h=i×k,∀i∈I,∀k∈K}，灾点i救援时间计算如式(8)，这里假设所有车辆正常情况下行驶速度相同，时间偏度计算如式(9)，时间公平目标函数如式(10)。
tik=Dik/v,i∈I,k∈K
(8)
(9)
(10)
1.4 成本
在应急救援中，决策者首要考虑灾区的需求满意度与时间公平，也要考虑整个救援工作成本的大小。本研究将整个救援工作的总成本定义为
(11)
1.5 应急调度模型
1.5.1 模型参数说明
I表示灾点集合，I={1,2，…n}，i,j∈I；
K表示救援中心集合，K={1,2,…m}，k∈K；
wi表示灾点i的权重；
ri表示灾区i的幸存人数；
δi为灾区i幸存人数的人均物资消耗量；
Ri表示灾点i应急物资需求量，可事先依据灾点情况预测；
Gk表示救援中心的物资储备量；
oi表示灾点i的物资满足程度；
oij表示灾点i与灾点j比较时，灾点i的满意度；
cik表示救援中心k到灾点i的单位物资物流成本；
xik表示救援中心k分配给灾点i的物资量；
tik表示救援中心k到灾点i的时间距离；
Lh为时间差异化衡量指标；
Ti表示灾点i接受物资的救援时间偏离度；
Tip表示各个救援中心到灾点i的平均救援时间；
Tij表示灾点i与灾点j的救援时间差；
Dik表示救援中心k与灾点i的距离。
1.5.2 模型构建
建立的应急物资分配多目标模型为
(12)
(13)
(14)
s.toij={oi-oj},∀i,j∈I
(15)
Tij={Ti-Tj},∀i,j∈I
(16)
(17)
(18)
(19)
(20)
其中，式(12)为灾民需求满意度，其值为负数，为0时，表示各个灾点物资满足程度没有差别；
式(13)为时间公平函数；
式(14)为总成本函数；
式(15)为满意度计算方式；
式(16)为时间公平衡量方式；
式(17)为各个灾点权重计算方式；
式(18)表示灾点获得的应急物资量小于其需求量；
式(19)表示救援中心援助各个灾点的物资量总量不大于其储备量；
式(20)表示决策变量为非负整数。
多目标问题中的各个目标是互相牵制对方的，无法得到使每个目标都是最优的最优解，得到的是一组帕累托解[16]。随着智能优化算法的发展，如多目标粒子群算法、NSGA-II算法的出现，为多目标问题的解决提供了有力方法[17]。印度学者Kaipa和Ghose提出了一种新型智能算法，即萤火虫算法[18]。由于该算法具有实现简单、参数少等优点，广泛应用于诸多领域[19-22]，本文研究了标准萤火虫原理，设计了改进多目标萤火虫算法来求解该应急物资调度模型。
2.1 标准萤火虫算法
设xi(t)表示t代i萤火虫位置，li(t)表示该萤火虫的荧光素浓度，荧光素的更新由其自身更新与适应度值修正两部分组成，在每一次迭代时，使荧光素变化与适应度值相关，萤火虫在移动过程中朝着荧光素浓度最高的萤火虫前进，即向适应度值最优的萤火虫前进。
li(t+1)=(1-ρ)li(t)+λF(xi(t))
(21)
式中，ρ为荧光素挥发系数，λ为目标函数值修正系数，F(xi(t))表示t代萤火虫i的目标函数值，即适应度值。
萤火虫移动过程中，依据选择概率选择领域内萤火虫进行移动，i萤火虫选择领域内j萤火虫的选择概率计算如式(22)，Ni(t)表示萤火虫i的领域，其按照式(23)计算，萤火虫位置更新如式(24)，移动结束后，以式(25)更新决策半径。
(22)
(23)
(24)
(25)
2.2 改进多目标萤火虫算法
步长处理：标准萤火虫算法在搜索最优解过程中，始终保持固定步长，导致算法性能低下。正切函数y=tan(x)的原理是当括号里的自变量x为0.785时，y为1，y的值随着x的值减小而逐渐减小，在这个过程中y的减小速率也是逐渐变小。为了使萤火虫算法在搜索过程中步长值可以自适应逐渐变小，因此将正切函数引入步长更新公式中，改进萤火虫步长更新机制如式(26)。
(26)
式中：tmax、t分别为最大迭代次数和当前迭代次数，s、s0分别为萤火虫算法步长和步长固定参数，且步长固定参数取值为1，改进步长变化趋势如图1所示，算法前期，以较大步长搜索，使算法有更好的全局搜索能力，随着算法迭代，步长逐渐慢慢缩小，增强算法局部搜索能力。
图1 改进步长变化趋势图
多目标处理：标准萤火虫算法首先利用荧光素在决策半径内确定领域，然后选择一个领域最优萤火虫，逐渐向其靠近。为了使萤火虫算法适用于本文问题模型，需要将非支配排序思想引入萤火虫算法中，本文以求解两个最小化目标为例来进行描述，具体如下。
(27)
(28)
位置更新：由于是多目标，原先的荧光素导向更新机制不再适用。本文在Pareto解集里寻找领域，然后，以领域内所有个体位置的平均值来进行位置更新，具体方法为
(29)
(30)
(31)
当萤火虫领域为空集时，萤火虫便不会继续移动，因此，本文设计了第二种位置更新机制，以避免算法陷入极值，萤火虫i直接从Pareto解集里随机选择一个Pareto解去更新，更新机制具体为
(32)
式中：xpareto(t)表示Pareto解集里随机选择的萤火虫位置。
2.3 改进多目标萤火虫算法步骤
Step1：设置算法参数，最大迭代次数tmax，种群大小，初始决策半径，步长固定参数s0等，生成初始解；
Step2：计算种群目标函数值，并且依据目标函数值筛选初始帕累托解；
Step3：循环开始，更新算法参数，在帕累托解集按照式(29)搜索领域；
Step4：利用帕累托解，按照式(30)、(31)更新种群个体位置；
Step5：判断领域是否为空集，如果领域为空集，则按式(32)更新种群个体位置；
Step6：计算种群目标函数值，更新帕累托解集；
Step7：判断算法是否达到最大迭代次数，若是，结束算法，输出解，否则，转step3。
3.1 参数设计
由于某种突发性灾难，致使周围8个地区成为灾区，附近有5个可供救援物资的救援中心，且物资储备量分别为G1=1000，G2=800，G3=1500，G4=1200，G5=1400。经过相关专家根据灾区情况预测出各个灾区的物资需求量，如表1所示，救援中心与灾区之间的单位物资运费如表2所示，距离矩阵如表3。
3.2 计算结果
运用改进多目标萤火虫算法、标准萤火虫算法以及多目标粒子群算法来求解该模型。硬件环境为Intel(R)Core(TM) i7-1065G7@ 2.52 GHz 双核处理器，运行内存8 GB，软件环境为Window8系统64 位，编程软件为Matlab R2014b软件。设置种群大小为100，步长固定参数s0=1，最大迭代次数tmax为200，为了比较算法性能，3种不同算法相同参数取值一致，结果如表4，模型初始解分布如图2。
图2 初始解分布
由于篇幅限制，表4展示Pareto解集里部分结果，改进多目标萤火虫算法所求Pareto解集分布如图3所示，具体物资分配方案如表5所示。除此之外，利用算法对不考虑路径异质性的应急物资配置方案进行了求解(见表6)。
由表5、表6可以看出，考虑路径异质性特点时所求得物资分配方案下的灾区需求满意度值虽然略大于不考虑路径异质性所得方案的灾区需求满意度值，但是时间公平函数值具有明显差别(1.6<2.016)。考虑路径差异所产生的时间差异化影响因素，所求得方案时间公平目标更为优化，也更符合实际情况，原因在于，同样物资满足的情况下，若时间和往常一样，可能会产生时间上的浪费。
图3 改进萤火虫算法Pareto分布
表1 灾区信息
表2 救援中心与灾区之间的单位物资运费
表3 救援中心与灾点距离
表4 算法计算结果
表5 考虑路径异质性应急物资配置方案
表6 不考虑路径异质性应急物资配置方案
3.3 算法性能比较
通过比较收敛性指标γ和分布性指标Δ来比较算法性能，由于在计算时需要真实最优Pareto，所以，本文将全部运行结果合并为一个集合代替最优Pareto解集。
(33)
(34)
表7 算法评价指标
由表7可得，从收敛性指标γ来看，改进萤火虫算法要优于标准萤火虫算法，从分布性指标Δ来看，改进萤火虫算法与多目标粒子群算法无显著差异，且优于标准萤火虫算法。
应急物资配置是灾后及时开展救援工作的首要任务，合理、科学地制定应急物资调度方案对于防灾减灾具有重要意义。之前的应急物资配置研究，公平分配只针对物资分配量的公平或者分配物资时间方面的公平，很少有学者将二者结合起来进行研究。并且，没有考虑到灾民的满意度和本受灾点物资分配量以及其他受灾点物资分配量都有关系，也没有将时间差异性特点考虑到所建立的模型之中。
本文利用时间差异化指标、距离来对各个救援中心到灾点的时间进行差异化模拟，基于受灾点需求程度与其他灾区需求程度构建了以需求满意度为目标和时间公平目标的应急物资多目标模型。基于非支配排序思想，改进设计了多目标萤火虫算法，通过仿真案例的求解与分析，证明了模型的可行性与算法的有效性。
猜你喜欢 萤火虫灾区物资 募集52万件物资驰援东华大学纺织服装周刊(2022年16期)2022-05-11利用简单几何原理 制造可作为灾区紧急避难所的帐篷海外星云(2021年6期)2021-10-14ГОРОДА-ПОБРАТИМЫ ПОМОГАЮТ ХАРБИНУ В БЕДЕ俄友好城市向哈尔滨捐赠医疗物资伙伴(2020年2期)2020-03-13萤火虫小天使·一年级语数英综合(2018年7期)2018-09-12萤火虫小天使·一年级语数英综合(2017年6期)2017-06-07救援物资瞭望东方周刊(2016年8期)2016-03-12抱抱就不哭了为了孩子（孕0～3岁）(2016年1期)2016-01-16夏天的萤火虫小天使·一年级语数英综合(2015年8期)2015-07-06大陆援台物资遇波澜环球时报(2009-08-19)2009-08-19灾区笑脸四川党的建设(2009年6期)2009-08-04
