考虑目标偏好的应急物资调度方案优化方法.pdf

管 理 决 策统计与决策2023年第21期总第633期0引言应急物资调度（Emergency Material Scheduling，EMS）的研究主要包括调度模型和求解方法两个方面。Hu等（2019）1指出EMS调度模型主要以最短时间、最短距离、最小成本、最大满意度、公平性等为目标。Liu等（2021）2考虑到受灾群众满意度，建立了具有满意度约束的调度模型。Li（2021）3建立了考虑运输时间、成本、资源可用性等影响因素的资源调度模型。薛星群等（2020）4以受灾点等待救援的平均时间最短以及应急网络总费用最低为目标，构建运力受限条件下受通行约束的救援物资联合运输多目标优化模型。苑津莎等（2020）5在考虑需求点满意度的同时，引入需求迫切度概念，进一步提高调度模型的科学性。Wan等（2021）6建立了基于有序到货原则的多目标多约束应急物资调度模型。由于灾害发生后，很难估计应急救援物资的需求，刘扬等（2019）7以三角模糊数描述物资需求的不确定性，构建了考虑需求点匹配度和响应时间的多目标调度模型。Liu等（2020）8提出了一个具有连续时变供需约束的应急物资分配多目标优化模型，使得应急救援行动的损失和经济成本最小化。EMS因其多目标和多约束特性在大多数情况下为强NP-Hard问题，启发式算法成为解决这类优化问题的重要方法。但启发式算法几乎都存在早收敛和优化精度不高的问题，为此，一些改进和融合算法有效地改善了算法的性能。Han等（2021）9通过引入状态转移算法的四种状态变换算子，解决了模拟退火算法探索初期收敛进度慢的问题。Joshi等（2021）10提出了一种嵌入邻域档案的改进引力搜索算法，有助于以更少的时间复杂度增加多样化的搜索。Mohammed 和 Rashid（2020）11提出鲸鱼灰狼优化算法，解决了局部搜索能力不足的问题。目前，考虑目标偏好的多目标应急物资调度研究尚不多见，算法的优化精度和搜索性能仍值得进一步改善，鉴于此，本文建立一个具有目标偏好的双目标应急物资调度模型，提出一种麦田竞赛算法（Tournament in Cornfield Al-gorithm，TCA），以解决EMS方案优化问题。1应急物资调度模型1.1假设条件受到物资储备量、道路状况、运输能力等因素的影响，使得应急物资调度成为一项十分复杂的优化问题。考虑到上述影响因素以及应急物资调度的可行性，对调度模型作如下假设：（1）供应点是指第三方商业性物资储备库。（2）各类物资总储备量大于总需求量。（3）每个需求点应急物资需求和每个供应点应急物资储备的种类和数量不完全相同。（4）每个需求点可以从多个供应点调度物资，每个供应点可以向多个需求点供应物资。（5）同一供应点运输车辆性能相同且数量有限，每辆车只从一个供应点装载物资，只为一个需求点运送物资。考虑目标偏好的应急物资调度方案优化方法汪勇1，李文凯1，艾学轶1，蒲秋梅2（1.武汉科技大学 恒大管理学院，武汉 430065；2.中央民族大学 信息工程学院，北京 100081）摘要：多需求点、多供应点以及多种物资需求的应急物资调度是一项复杂的优化问题，当前元启发式算法求解时存在早熟收敛现象且优化精度不高。为降低调度成本、缩短调度时间，文章构建一个多目标应急物资调度模型，设计一种调度方案实值映射编码，确保优化操作不破坏调度方案的有效性。基于此，模拟麦田理论的优化思想，提出了一种麦田竞赛元启发式算法。首先构造搜寻方向、搜寻速度和搜寻指令三个控制因子，建立具有目标偏好的成熟度函数，借此设计具有大范围搜索和精准搜索能力的麦穗搜寻算子以及优等麦穗和最优麦穗筛选算子。其次根据麦穗物理指标和成熟度变化趋势更新搜寻方向。最后通过实验表明，新建立的应急物资调度模型能够大幅缩减调度成本和调度时间，所提出的算法优化精度和搜索性能明显优于相比较的五个元启发式算法。关键词：应急管理；物资调度；多目标优化；元启发式算法；麦田竞赛中图分类号：C931；TP301.6文献标识码：A文章编号：1002-6487（2023）21-0184-05基金项目：国家自然科学基金资助项目（71901167）作者简介：汪勇（1967），男，湖北武汉人，博士，教授，研究方向：智能优化算法、机器学习。李文凯（1997），男，湖北鄂州人，硕士研究生，研究方向：系统优化与决策。艾学轶（1983），女，湖北随州人，博士，副教授，研究方向：库存管理、启发式算法。蒲秋梅（1976），女，湖北十堰人，博士，副教授，研究方向：数据挖掘、机器学习。DOI:10.13546/ki.tjyjc.2023.21.034184管 理 决 策统计与决策2023年第21期总第633期1.2调度模型构建1.2.1问题描述设有n个需求点，m个供应点，u种应急物资，qik表示需求点i需求应急物资k的数量，cjk表示供应点j储备应急物资k的数量。一个调度方案x可表示为x=xijk|i=12nj=12mk=12u。为减少灾害带来的损失，在最短时间内将应急物资配送到位是调度者首要考虑的目标。此外，由于供应点是商业性物资储备库，因此在保障应急物资及时供给时，需考虑应急物资的采购成本。故以时间和成本为目标构建应急物资调度模型。f1(x)、f2(x)分别表示调度时间和调度成本，调度目标是使得f1(x)与f2(x)最小，即：minf1(x)minf2(x)（1）s.t.xijkN+（2）0 xijkcjk（3）i=1nxijkcjk（4）xijkqikj=1mxijk=qik（5）cjk0qik0（6）i=1nqikj=1mcjk（7）式（2）至式（7）为式（1）的约束条件。式（2）表示应急物资调度数量整数约束，即决策变量xijk为正整数。式（3）表示决策变量xijk非负且不大于供应点j物资k的储备量。式（4）表示所有需求点从供应点j调度物资k的总量不大于该供应点物资k的储备量。式（5）表示需求点i从所有供应点调度物资k的总量等于该需求点对物资k的需求量。式（4）、式（5）是决策变量定义域约束。所有决策变量定义域不相同且存在依赖关系。由式（4）知，当供应点j可供调度的物资k数量小于需求点i需求物资k的数量时，则需求点i从供应点j调度物资k的数量不超过该供应点剩余物资k的数量。即xijkcjk-h=1i-1xhjk。由式（5）知，需求点i从供应点j调度物资k的数量不超过该需求点所需剩余物资k的数量，即xijkqik-h=1j-1xihk。式（6）表示供应点物资储备量和需求点物资需求量非负约束。式（7）表示所有需求点物资k的需求量不超过所有供应点物资k的储备量。1.2.2调度时间在不考虑物资装载时间的情形下，调度时间即应急物资运输时间。每个供应点按照需求点受灾程度运送应急物资，先向受灾程度最严重的需求点运送物资，接着向受灾程度次严重的需求点运送物资，依此类推，直到完成所有需求点的物资运送任务。对于一个调度方案x，设需求点i从供应点j调度物资总重量为Mij(x)，则：Mij(x)=k=1urjkwjkxijk（8）其中，rjk是供应点j物资k的储备状态，cjk=0时，rjk=0；cjk0时，rjk=1。wjk是供应点j物资k的单位重量。设供应点j向所有需求点运送物资的车次为b(j)，则：b(j)=i=1nMij(x)/gj（9）其中，gj是供应点j车辆载重量。b(j)0时，表示需要多台车辆运送应急物资。设供应点j总的运输任务为Sj(x)，根据式（8）、式（9），Sj(x)=s1s2sb(j)，b(j)为运输任务数，即每车次为一个运输任务。一个需求点可能存在多个运输任务，供应点j到需求点i的运输时间记为Tij(x)，则：Tij(x)=dij/vj（10）其中，dij是供应点j到需求点i的距离，vj是供应点j车辆平均时速。由式（10）可得各任务的运输时间Tj(x)=t1t2tb(j)。设供应点j的车辆数为h(j)。根据运输任务及其运输时间计算供应点j的调度时间DTj(x)。0时刻开始执行前h(j)个运输任务，当有运输任务完成时，释放的车辆开始执行第h(j)+1个运输任务，依此类推，直到所有运输任务完成为止，设第a(a=12b(j)-h(j)+1)批任务最短运输时间为STa，则第a+1批任务的剩余运输时间RTa+1见式（11）。RTa+1=RTa-i=1aSTi（11）显然，a=1时，RT1t1t2th(j)。根据式（11）计算每一批未完成任务的剩余运输时间，从而得到该批任务的最短运输时间STa和最后一批任务的最长运输时间LTb(j)-h(j)+1，则所有任务的调度时间见式（12）。DTj(x)=LTb(j)-h(j)+1+i=1b(j)-h(j)STi（12）总的调度时间f1(x)取决于所有需求点调度时间的最大值，即：f1(x)=maxDTj(x)j=12m（13）其中，为惩罚因子。若调度方案满足式（3）、式（4）约束，则=1，否则，=+。1.2.3调度成本调度成本由采购成本和物流成本构成。由假设条件可知，供应点为商业性物资储备库，调度物资必然产生成本，称为采购成本，记为pc(x)。采购成本取决于供应点应急物资单位价格和调度数量。设pjk表示供应点j应急物资k的单位价格，则所有需求点调度的应急物资采购185管 理 决 策统计与决策2023年第21期总第633期成本为：pc(x)=i=1nj=1mk=1upjkxijk（14）其中，xijk=0表示需求点i没有应急物资k的需求。物流成本主要来自车辆使用费，记为lc(x)。设j表示供应点j的单位运输费用。根据式（8）得到物流成本为：lc(x)=i=1nj=1mjMij(x)（15）由式（14）和式（15）得到调度方案x的调度成本为：f2(x)=pc(x)+lc(x)（16）1.3调度方案编码由于直接采用优化变量实值编码易产生大量无效解，故设置一个新的决策变量ijk，ijk0，为所有新的决策变量上界。ijk表示需求点i从供应点j调度应急物资k的份额，ijk是一个三维变量，为便于计算，按照需求点排列为一维结构编码。新变量与原始变量的映射函数见式（17）。xijk=qikijk/j=1mijk（17）2麦田竞赛算法2.1相关定义定义1：选手手中的麦穗称为标准麦穗，标准麦穗的集合称为标准群体，记为X，X=xi|i=12N，xi表示第i个标准麦穗。选手眼中搜寻到的麦穗称为挑战麦 穗，挑 战 麦 穗 的 集 合 称 为 挑 战 群 体，记 为Y，Y=yi|i=12N，yi是xi的挑战麦穗。N为群体规模。定义2：决策变量是一组反映麦穗质量的物理指标。xij表示标准麦穗xi的第j项物理指标，j=12L。yij表示挑战麦穗yi的第j项物理指标。L为物理指标数。定义3：筛选目标是判断标准麦穗和挑战麦穗质量优劣的依据，如颗粒饱满度、色泽等。筛选目标与麦穗物理指标间的关系称为筛选目标函数，记为fk(xi)，fk(xi)表示标准麦穗xi的第k个筛选目标，k=12m，m为目标数。选手关注程度最高的目标称为偏好目标。定义4：设xiX，yiY，xi与yi具有质量优劣关系，若k1m，都有fk(yi)fk(xi)成立，则yi优于xi，yi为优等麦穗，记为yixi。反之，xi为优等麦穗，记为xiyi。显然，麦穗质量优劣关系具有传递性。若xi，xj，xhX，xixj，且xjxh，则xixh。定义5：对于xiX，yiY，若$k，l1m，kl，使得fk(xi)fk(yi)，且f1(xi)F(xj)成立，则称xi为标准麦穗群体的最优麦穗。若对于xjX，都有Fk(xi)Fk(xj)成立(k=12m)，则称xi为偏好目标k的最优麦穗。2.2麦穗搜寻阶段TCA主要包括麦穗搜寻和麦穗筛选两个阶段，搜寻实际上是标准麦穗的启发式计算过程，由此产生挑战麦穗。搜寻阶段从当前标准群体出发，竞赛选手根据标准麦穗所在的区域范围，搜寻标准麦穗附近的挑战麦穗，所有选手搜寻到的挑战麦穗构成挑战群体。设xij(t)表示第t轮标准麦穗xi的第j个物理指标，yij(t)表示其挑战麦穗相应的物理指标，i=12N，j=12L。根据定义 2，挑战麦穗yi(t)与标准麦穗xij(t)的启发式计算见式（18）。yij(t)=xij(t)+Dij(t)Instijvij（18）式（18）中，Dij(t)是t轮标准麦穗xi物理指标j的搜寻方向。当标准个体与挑战个体的指标值（决策变量）与成熟度值变化趋势一致时，Dij(t)=1，相反时，Dij(t)=-1；当指标值无变化时，Dij(t)保持不变。搜寻方向引导算法朝着最优解方向定向搜索，进一步提升 TCA 的搜索性能。Instij是物理指标j的搜寻指令，Instij=0表示停止搜寻，Instij=1表示开始搜寻。vij是物理指标j的搜寻速度，vij计算见式（19）。vij=|r|Gjxij(t)+1（19）式（19）中，r是均值为0、方差为1的正态分布的随机数。Gj是截止到第t轮搜寻的最优麦穗第j个物理指标值。xij(t)越大，对该项指标的搜寻速度越慢，反之越快。2.3筛选阶段2.3.1淘汰赛阶段筛选阶段模拟竞赛过程，在小规模范围内搜索可能的最优解，包括淘汰赛和锦标赛两种筛选形式。淘汰赛是在挑战麦穗和标准麦穗之间进行，胜者作为下一轮的标准麦穗，所有获胜者形成新一轮标准群体。根据定义3和定义4，第t+1轮标准群体X(t+1)按式（20）、式（21）计算。X(t+1)=i=1N(xl(t)yi(t)（20）(x)=xi(t)x0yi(t)x00,x=0-1,x0（24）由式（24）知，任意两个标准麦穗的筛选目标统计函数值之和为0，即(x)+(-x)=0。因此，F(xi)=0。2.4算法描述步骤 1：输入。需求点应急物资需求种类与数量q，供应点应急物资储备种类、数量c、单位重量w和单价p，供应点车辆数量h、载重量g、平均时速v和单位运输费用，竞赛轮数T，偏好目标pf，搜寻方向D（初始值为1），初始标准群体X。步骤 2：按式（8）至式（13）计算f1(x)，按式（14）至式（16）计算f2(x)。步骤 3：按式（22）至式（24）计算标准麦穗的成熟度F，保存最优麦穗（最优调度方案）x*及f(x*)。步骤 4：若达到最大竞赛轮数，则终止计算，转步骤 9，否则，转下一步。步骤 5：按式（18）、式（19）搜寻挑战麦穗，获得挑战群体Y。步骤 6：按式（8）至式（16）分别计算挑战群体Y中挑战麦穗的筛选目标值f1(x)和f2(x)。步骤 7：按式（20）、式（21）逐一筛选标准麦穗和相应的挑战麦穗，胜者作为优等麦穗加入标准群体，产生新一轮标准群体X。步骤 8：更新搜寻方向D，转步骤 3。步骤 9：输出。全局最优调度方案x*及调度时间f1(x*)和调度成本f2(x*)。3实证分析3.1数据与参数设置2021 年河南特大洪涝灾害共造成 17 个省辖市、1417.85万人受灾，直接经济损失达1767.03亿元。以此为算例背景，选择11个受灾地区为应急物资需求点，9个仓储为应急物资供应点，以大米、面粉、饮用水等6种物资为主要的应急救援物资。根据受灾情况设置各地区各类应急物资需求量。参考河南省应急管理厅、统计局、电商等官网数据，整理得到供应点物资储备、价格等数据，存储于相关数据集。为验证调度模型的有效性和提出算法的性能，同时采用TCA、DE、GWO、GSA、NSGA-II和PSO求解最优调度方案。为便于对比，各算法初始群体相同，群体个体数N=20，误差精度e=5.00.5，调度份额上界lambda=15，最大迭代次数T=5000。3.2应急物资优化调度算法比较应急救援工作要求在最短时间内将应急物资运送到受灾点，采取最近供应点调度的方案见表1。表1最近供应点调度方案方案1方案2方案3方案4方案5方案6需求点1，42，35，7，86910供应点214867调度成本（万元）713.9541.1845.9185.4156.9117.3调度时间（小时）74.430.215.322.626.34.0由表1可知，最近供应点调度的总成本为2560.5万元，调度时间是完成所有需求点应急物资运送任务的时间，故总调度时间为74.4小时。为求解最优调度方案，并检验提出算法的优化效果，分别采用无目标偏好的TCA算法与其他五个算法进行对比实验，为避免算法的随机性，所有算法均计算30次，取其平均值作为全局最优目标值。各算法求解结果见表2。表2最优调度方案算法调度成本（万元）调度时间（小时）TCA1889.740.5DE2174.171.7GWO2191.874.7GSA2285.678.3NSGA-II2288.682.2PSO2260.069.4由表2可知，无论是调度成本还是调度时间，无目标偏好的TCA算法求解结果都明显低于其他算法。TCA的调度成本远低于最近供应点调度方案，调度时间将近缩短一倍。各算法全局最优调度曲线变化趋势见图1。240022502100195018000100020003000400001000200030004000130105805530（b）调度时间迭代次数（a）调度成本迭代次数TCADEGWOPSONSGA-IIGSA图1 全局最优调度目标曲线图1（a）为算法最优调度成本曲线。1000次迭代计算内，DE收敛速度最快，NSGA-II收敛速度最慢。此后，除TCA外，其他算法基本趋于收敛，TCA却继续呈下降趋势，且远离曲线相对集中的其他算法。图1（b）为最优调度时间曲线。TCA曲线持续保持下降趋势，其他曲线均出现早187管 理 决 策统计与决策2023年第21期总第633期熟收敛。可见，TCA优化能力明显优于相比较的算法。3.3考虑目标偏好的TCA优化调度调度者根据目标要求设定目标偏好，为验证具有目标偏好的调度模型有效性和TCA求解多目标问题的优化能力，分别考虑调度成本偏好和调度时间偏好求解最优调度目标值，并与无偏好情形进行对比。优化结果见表3，算法均计算30次，取其平均值作为最优调度目标值。表3考虑目标偏好的TCA最优调度方案调度目标调度成本（万元）调度时间（小时）无目标偏好1889.740.5调度成本偏好1835.946.7调度时间偏好1946.536.4由表1至表3知，考虑成本偏好的TCA求解的调度成本最低，与最近供应点调度相比，节约调度成本26.2%，此时，调度时间约为最近供应点调度的一半。考虑时间偏好的TCA求解的调度时间最短，仅为36.4小时，与最近供应点调度相比，节约调度时间51.1%，此时，调度成本也明显低于最近供应点调度以及其他算法求解结果。无偏好TCA两个目标值介于成本偏好和时间偏好之间，是一个折中方案。由此可见，TCA求解的应急物资优化调度方案均优于其他算法求解的优化调度方案。考虑目标偏好的TCA最优目标变化趋势见图2。0100020003000400001000200030004000（b）调度时间迭代次数（a）调度成本迭代次数24002250210019501800130105805530无偏好成本偏好时间偏好无偏好成本偏好时间偏好图2 目标偏好的TCA全局最优调度目标曲线由图2可知，无论是考虑成本偏好还是考虑时间偏好，相应的目标曲线都呈下降趋势，且三种情形下降趋势基本一致。表明考虑目标偏好的TCA与无偏好TCA一样，其最优目标是收敛的。3.4算法搜索性能比较尽管包括TCA在内的上述算法求解的最优目标均是收敛的，但算法的搜索性能不尽相同。每一代群体最优目标值变化趋势反映算法的搜索性能，所有算法的每一代群体最优调度时间和最优调度成本曲线见图3，其中TCA为考虑目标偏好情形。13080301309050240021201840240022602120020004000020004000020004000020004000020004000020004000020004000020004000020004000020004000020004000020004000TCADETCADEGWONSGA-GSAGWOGSAPSOPSONSGA-f1f1f1f1f1f1f2f2f2f2f2f2130100130100701301007013010070tttttttttttt240023252250240023252250240023252250240023252250（a）（b）图3 每一轮群体最优调度目标曲线图3（a）和图3（b）分别是调度时间和调度成本优化曲线，考虑目标偏好的TCA两个目标曲线基本不存在振荡，每一代群体两个最优目标值持续降低，直至收敛。其他算法两个目标曲线存在较大幅度振荡。由此可见，考虑目标偏好的TCA优化算法搜索性能明显优于相比较的算法。4结束语实证表明，本文建立的应急物资调度模型能有效地降低调度成本，大幅缩短调度时间，可为应急物资优化调度提供决策参考。所提出的TCA优化算法简洁高效，适合求解多目标优化问题，其优化精度和搜索性能均优于相比较的算法，可满足应急物资管理者的多目标调度决策需求。调度方案实值映射编码能够保持所有算法个体更新的有效性。当需求点和供应点数量较大、需求物资以及考虑目标较多时，调度方案解空间将显著增加，TCA等优化算法计算效率降低，因此，对于具有更多调度目标和高维度决策变量的应急物资调度模型，提高TCA算法的计算效率值得进一步研究。参考文献：1Hu H,He J,He X,et al.Emergency Material Scheduling Optimization Model and Algorithms:A Review J.Journal of Traffic and Transportation Engineering(English Edition),2019,6(5).2Liu S C,Chen C,Zhan Z H,et al.Multi-objective Emergency Resource Dispatch Based on Coevolutionary Multiswarm Particle SwarmOptimization C.Shenzhen:International Conference on EvolutionaryMulti-Criterion Optimization,2021.3Li C L.Optimization of Emergency Resource Scheduling in Serial Terrorist Attacks Based on PSO-CS Algorithm J.Journal of Applied Security Research,2021,16(4).4薛星群,王旭坪,韩涛,等.考虑通行约束和运力限制的灾后应急物资联合调度优化研究J.中国管理科学,2020,28(3).5苑津莎,马姿,杨宏.地震救灾初期应急物资智能调度问题的研究J.科学技术与工程,2020,20(21).6Wan F,Guo H X,Ying Y J.A Scheduling and Planning Method forGeological Disasters J.Applied Soft Computing,2021,111(11).7刘扬,张国富,苏兆品,等.救灾物资多阶段分配与调度问题建模与求解J.控制与决策,2019,34(9).8Liu Y H,Li Y C,Huang D.A Multiobjective Optimization Model forContinuous Allocation of Emergency Rescue Materials J.Mathematical Problems in Engineering,2020,(7).9Han X,Dong Y,Yue L,et al.State-transition Simulated AnnealingAlgorithm for Constrained and Unconstrained Multi-objective Optimization Problems J.Applied Intelligence,2021,51(2).10Joshi S K,Gopal A,Singh S.A Novel Neighborhood Archives Embedded Gravitational Constant in GSA J.Soft Computing,2021,25(8).11Mohammed H,Rashid T.A Novel Hybrid GWO With WOA for Global Numerical Optimization and Solving Pressure Vessel Design J.Neural Computing&Applications,2020,32(18).（责任编辑/刘柳青）188