考虑目标偏好的应急物资调度方案优化方法.pdf
《考虑目标偏好的应急物资调度方案优化方法.pdf》由会员分享,可在线阅读,更多相关《考虑目标偏好的应急物资调度方案优化方法.pdf(5页珍藏版)》请在咨信网上搜索。
1、管 理 决 策统计与决策2023年第21期总第633期0引言应急物资调度(Emergency Material Scheduling,EMS)的研究主要包括调度模型和求解方法两个方面。Hu等(2019)1指出EMS调度模型主要以最短时间、最短距离、最小成本、最大满意度、公平性等为目标。Liu等(2021)2考虑到受灾群众满意度,建立了具有满意度约束的调度模型。Li(2021)3建立了考虑运输时间、成本、资源可用性等影响因素的资源调度模型。薛星群等(2020)4以受灾点等待救援的平均时间最短以及应急网络总费用最低为目标,构建运力受限条件下受通行约束的救援物资联合运输多目标优化模型。苑津莎等(20
2、20)5在考虑需求点满意度的同时,引入需求迫切度概念,进一步提高调度模型的科学性。Wan等(2021)6建立了基于有序到货原则的多目标多约束应急物资调度模型。由于灾害发生后,很难估计应急救援物资的需求,刘扬等(2019)7以三角模糊数描述物资需求的不确定性,构建了考虑需求点匹配度和响应时间的多目标调度模型。Liu等(2020)8提出了一个具有连续时变供需约束的应急物资分配多目标优化模型,使得应急救援行动的损失和经济成本最小化。EMS因其多目标和多约束特性在大多数情况下为强NP-Hard问题,启发式算法成为解决这类优化问题的重要方法。但启发式算法几乎都存在早收敛和优化精度不高的问题,为此,一些改
3、进和融合算法有效地改善了算法的性能。Han等(2021)9通过引入状态转移算法的四种状态变换算子,解决了模拟退火算法探索初期收敛进度慢的问题。Joshi等(2021)10提出了一种嵌入邻域档案的改进引力搜索算法,有助于以更少的时间复杂度增加多样化的搜索。Mohammed 和 Rashid(2020)11提出鲸鱼灰狼优化算法,解决了局部搜索能力不足的问题。目前,考虑目标偏好的多目标应急物资调度研究尚不多见,算法的优化精度和搜索性能仍值得进一步改善,鉴于此,本文建立一个具有目标偏好的双目标应急物资调度模型,提出一种麦田竞赛算法(Tournament in Cornfield Al-gorithm,
4、TCA),以解决EMS方案优化问题。1应急物资调度模型1.1假设条件受到物资储备量、道路状况、运输能力等因素的影响,使得应急物资调度成为一项十分复杂的优化问题。考虑到上述影响因素以及应急物资调度的可行性,对调度模型作如下假设:(1)供应点是指第三方商业性物资储备库。(2)各类物资总储备量大于总需求量。(3)每个需求点应急物资需求和每个供应点应急物资储备的种类和数量不完全相同。(4)每个需求点可以从多个供应点调度物资,每个供应点可以向多个需求点供应物资。(5)同一供应点运输车辆性能相同且数量有限,每辆车只从一个供应点装载物资,只为一个需求点运送物资。考虑目标偏好的应急物资调度方案优化方法汪勇1,
5、李文凯1,艾学轶1,蒲秋梅2(1.武汉科技大学 恒大管理学院,武汉 430065;2.中央民族大学 信息工程学院,北京 100081)摘要:多需求点、多供应点以及多种物资需求的应急物资调度是一项复杂的优化问题,当前元启发式算法求解时存在早熟收敛现象且优化精度不高。为降低调度成本、缩短调度时间,文章构建一个多目标应急物资调度模型,设计一种调度方案实值映射编码,确保优化操作不破坏调度方案的有效性。基于此,模拟麦田理论的优化思想,提出了一种麦田竞赛元启发式算法。首先构造搜寻方向、搜寻速度和搜寻指令三个控制因子,建立具有目标偏好的成熟度函数,借此设计具有大范围搜索和精准搜索能力的麦穗搜寻算子以及优等麦
6、穗和最优麦穗筛选算子。其次根据麦穗物理指标和成熟度变化趋势更新搜寻方向。最后通过实验表明,新建立的应急物资调度模型能够大幅缩减调度成本和调度时间,所提出的算法优化精度和搜索性能明显优于相比较的五个元启发式算法。关键词:应急管理;物资调度;多目标优化;元启发式算法;麦田竞赛中图分类号:C931;TP301.6文献标识码:A文章编号:1002-6487(2023)21-0184-05基金项目:国家自然科学基金资助项目(71901167)作者简介:汪勇(1967),男,湖北武汉人,博士,教授,研究方向:智能优化算法、机器学习。李文凯(1997),男,湖北鄂州人,硕士研究生,研究方向:系统优化与决策。
7、艾学轶(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。为减少灾害带来的损失,在最短时间内将应急物资配送到位是调度者首要考虑的目标。此外,由于
8、供应点是商业性物资储备库,因此在保障应急物资及时供给时,需考虑应急物资的采购成本。故以时间和成本为目标构建应急物资调度模型。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的储
9、备量。式(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)表示供应点物资储备量和需求点物资需求量非负
10、约束。式(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
11、),则: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)
12、。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)
13、总的调度时间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表示需
14、求点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(1
15、7)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
16、),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为偏好
17、目标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的搜寻方向。当标
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考虑 目标 偏好 应急 物资 调度 方案 优化 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。