震后多时段应急物资联合配送路径优化研究

杜茂康,杨 单,陆 聪

(重庆邮电大学经济管理学院,重庆 400065)

地震灾害救援一直是中国应急救援的重中之重。中国共有23条地震带,地震活动频度高、强度大、震源浅、分布广,是一个震灾严重的国家。强度较大的地震如2008年汶川地震、2011年玉树地震、2017年九寨沟地震和2022年泸定地震等[1],都给人民生命安全和财产造成重大损失。完备的震后应急救援系统能够极大限度地将灾害造成的损失降至最低。地震救援具有时效性强的特点,越早投入救援力量和救援物资震后损失越小。因此,震后应急救援物资的及时合理配送一直是学者们研究的重要课题。

通常情况下,自然灾害往往会伴随一些破坏性较大的活动,灾区内的交通设施可能会面临瘫痪。在突发灾害情景下,还需要从多方面对应急救灾进行多种考虑。FIKAR等[2]提出了一个模拟优化的决策分析系统来满足不同受灾点的动态需求。闫森等[3]研究道路受损对应急物资配送的影响,考虑多种类物资和多中心配送。狄卫民等[4]综合对灾后道路损毁状况、道路复杂程度及物资拆分等因素进行了研究。文献[5-7]分别对灾民心理影响、手机数据测算及次生灾害等其他方面构建模型进行研究。赵建有等[8]将受灾点进行区域划分,以救援过程总时间最短和总费用最小为目标,在汶川地震背景下构建算例进行模型验证。上述研究考虑了灾后受灾区域内道路受损情况,构建多目标模型以满足不同的灾民物资需求,但并未考虑特殊点位的特殊需求,如震中区域的时间窗要求。

在考虑受灾区域内道路损毁状况的同时,除了上述学者的研究,有部分学者尝试通过设计划分多个阶段,根据损毁程度或多种目标划分两阶段或是三阶段进行问题求解。AHMADI等[9]在考虑道路损坏的情况下,设计一种随机行程时间的两阶段随机线性规划。曲冲冲等[10]考虑时效性和物资分配的公平性,建立了多阶段的应急配送中心选址-配送模型。张立等[11]将应急物资配送任务划分多个周期进行求解考虑。上述文献集中研究划分多个阶段的方式进行物资配送,能够使物资配送流程更加合理规范,但由于涉及较广,因而不能很好地突出受灾道路损毁等重要影响因素。文献[12-16]的研究主要解决了受灾区域交通状况受限情况下的物资高效配送问题,包括研究道路通行难易程度、道路修复及道路修复结合设施选址等有针对性的方法解决道路受限问题,但在交通运输工具的选择上过于单一,往往不能满足灾民需求。

本文在灾后初期受灾区道路受损程度不一情况下,结合实际中应急救援物资源源不断从各地运至应急分配中心,且各受灾点由于受灾程度和次生灾害影响会产生持续的物资需求的情况,研究物资规划和及时配送问题。通过抢修力度及道路修复情况划分时段进行物资配送,且考虑不同时段下受损道路的恢复状况以满足及时配送的需要。采用“车辆+直升机”的联合配送方式,根据受灾点受灾道路严重程度使用不同的配送工具。在震中附近道路损坏严重区域使用直升机进行配送,其他道路受损但不影响通行的区域及道路修复区域采用车辆进行配送。为了及时更新配送路线以节省救援时间,本文构建多目标规划模型,以救援物资需求配送总成本最小和总配送时间最短为目标,利用遗传算法结合模拟退火算法对该模型进行求解。本研究可为灾后初期应急救援物资的配送提供决策思路,以减少因突发灾害造成的人员伤亡和经济损失。

1 问题描述与模型构建

1.1 问题描述

地震灾害发生后,需要及时向灾区运送生活物资和医疗物资,紧紧把握救援“黄金72小时”。通常情况下,在地震灾害发生后,交通运输路网会因灾害或次生灾害遭到破坏,无法完成物资运送任务。因此,考虑采用“车辆+直升机”对灾区进行联合配送。对震中区域道路损毁严重、短时间内道路无法通行地区采用直升机进行配送;同时,在其他道路畅通区域采用卡车进行受灾点的物资配送。随着抢险力量的介入,道路修复通畅程度会加快。据此,提出时段划分情景下考虑道路修复程度的应急物资配送方案。灾后72 h将被平均划分为3个时段,根据不同时段会出现不同的道路通畅情况,进行受灾点的物资配送路径优化。由于灾害发生需要在最短时间内完成救援配送任务,因此首要约束目标考虑满足所有受灾点物资需求配送的总时间最小化,其次考虑应急物资配送方式的成本最小化,在联合配送情况下达到高效合理运输应急物资至受灾点的目标。

根据道路通畅情况进行配送任务的分配,道路为L1通畅度时代表不影响车辆通行,道路为L2通畅度时代表此道路需要在灾后t1时段才可恢复通行。据此,如图1中L1区域中的点均可由救援车辆进行物资配送,其余点要由直升机配送;图2表示多时段,原L2的点将被吸收至配送L1区域的后续点,另外点将延续使用直升机进行配送。

图1 “救援车辆+直升机”联合配送示意图

图2 多时段下联合配送示意图

1.2 问题假设

1)由于灾害发生第一时间就会实施应急响应机制,信息会逐步完善,因此应急分拨中心位置和容量、受灾点位置和需求已知。

2)根据卫星地图等信息分析可知道路通畅程度。

3)假设应急救援所使用的供应商所提供的救援设备型号为同一型号。

4)虽然救援过程中道路损毁度不同所导致的救援设备行驶速度并非全程保持一致,但整个过程救援设备的平均行驶速度一定,载重容量已知。

5)救援设备完成配送后必须返回应急分拨中心。

6)由于应急救援初期以满足主要的食品、药品和医疗器材为主,因此不考虑其他多样化物资种类,救援设备所配送的主要为应急物资包。

1.3 符号定义

参数和决策变量如表1所示。

表1 符号定义

1.4 数学模型

通过对现有相关文献的研究发现,由于地震灾害时效性较强,灾后应急救援物资及其他应急设施越早抵达灾区,灾区受灾群众的生命健康就能越早得到保障,因灾害遭受的损失就会越小。因此,第1个目标总配送时间f1为

(1)

其中:t1,t2,…,tn为不同时段(t1,t2,…,tn∈T),具体规定为在不同的时段,道路通畅度不同,每一时段代表24 h。t1表示震后24 h;t2表示震后48 h;t3表示震后72 h,tn表示震后24nh;其中,考虑救援车辆和直升机在不同时段配送方案中具有不同的卸货时间tpk和tpz,如在第一时段配送方案下,救援车辆卸货时间为tpk1,直升机卸货时间为tpz1。即在时段背景下,救援车辆从分拨中心出发,首先到达所负责的车辆需求点i,完成卸货任务后转向下一个车辆需求点j,最后返回;同时救援直升机从分拨中心出发,到达救援需求急迫但道路损毁的直升机需求点i,完成卸货任务后转向下一个点j,最终返回分拨中心。

第2个目标考虑因应急配送而产生的成本f2,包括应急分拨中心的成本、救援车辆的成本及救援直升机的成本,即f2=C1+C2+C3。应急分拨中心的成本包括使用成本和人员工资费用等,设定F5Mh为决策变量,表示应急分拨中心h是否启用。故应急分拨中心的成本C1为

(2)

救援设备的固定成本C2包括车辆的固定成本F1(租赁费、维护费等)以及直升机的固定成本(租赁费、驾驶员工资、维护费等)F3,故救援设备固定成本C2为

(3)

救援设备的运行成本C3包括救援卡车每公里运行成本F2及救援直升机每公里的飞行成本F4,故救援设备运行成本C3为

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

约束(6)表示救援设备r在到达某个物流网络节点后必须从该物流网络节点离开;约束(7)表示每个受灾点仅获得救援设备的一次配送,即要么救援车辆配送该点,要么救援直升机配送该点;约束(8)表示每个灾区受限点仅被救援直升机配送1次;约束(9)确保救援设备从应急分拨中心出发,经过所负责的需求点完成配送任务后最终返回应急分拨中心;约束(10)表示应急分拨中心负责的受灾点总需求不超过该中心的可用容量;约束(11)表示每条路线的受灾点物资总需求量不超过该救援设备的最大容量。

2 遗传模拟退火算法设计

对于多目标优化问题,传统的求解方法已难以解决日渐复杂的多目标规划问题。遗传算法等启发式算法逐渐成熟并被广泛应用,但由于遗传算法易早熟、早期个体差异较大,容易导致种群进化停滞。救援设备的联合配送问题涉及路线更新和路线规划等多个复杂方面,因此考虑将遗传算法和模拟退火算法进行结合,充分发挥模拟退火算法的局部搜索能力和遗传算法的全局搜索能力,克服遗传算法的易早熟现象和模拟退火算法效率不高的问题。算法流程图如图3所示。具体操作步骤如下:

图3 遗传模拟退火算法流程图

1)设置初始参数:群体个数n、交叉概率Pc、变异概率Pm、最大迭代次数i、初始温度T和降温系数α;

2)随机生成初始救援设备路线方案,并计算每条路线;

3)经过轮盘赌选择、交叉变异操作产生新的救援设备路径方案;

4)计算新方案中某一片段的适应度值并与旧片段的适应度进行比较,若新片段适应度fe1>fe,则用新片段替换旧片段;否则,以min{1,exp(-ΔE/T)}>rand[0,1]的概率接收新片段或舍弃;

5)设置救援设备容量约束和路线片段约束条件,若不满足约束条件则返回,继续优化迭代;

6)设定算法终止条件,满足一定迭代次数后算法终止,输出最优解。

2.1 编码方式

采用二维矩阵实数编码方式进行染色体编码,假设有3辆卡车和2架直升机进行配送任务,共需配送19个受灾点,且染色体在初始化种群和变异交叉的过程中必须确保道路不畅的受灾点只能分配给直升机来配送。道路不畅的受灾点编号为2,3,5,7,8,编号为1,4,6,…等的为卡车配送点,可能的编码方式如图4所示。由于救援设备有相应的容量限制,因此,在子路径划分上必须按照容量限制进行译码。如卡车3的路径可能是0-12-16-19-0和0-18-13-2-7-0。

图4 时段对比方案

2.2 适应度函数

种群个体的适应度是由模型部分的目标函数通过计算得出,本文最优值函数为考虑时间和成本标准化处理后的加权,所以最优值越小适应度值越大。针对种群中的个体x,适应度函数应为

2.3 遗传算子设计

1)选择算子采用轮盘赌算法,通过个体被选择的概率与其适应度成比例来确定选择的几率大小,轮盘赌算法是一种有放回的随机抽样选择法,一般来说,适应度越大,选择概率也越大。

2)交叉操作采用2点交叉的方式进行。如图5所示,首先随机配对种群中的个体,然后在所选择的个体中随机设置2个交叉点位,将所配对个体2个随机交叉点位中的基因进行互换,所生成的即为新个体。但由于交叉点位随机产生,因此互换后的2个个体中可能会存在相同的基因片段,对此采取映射的方法对相同基因进行消除。

图5 交叉操作

3)变异方式采用两点互易方法,包含2种变异策略。

策略a:首先对救援工具负责的点组进行变异操作,假设卡车1负责5个点,卡车2负责6个点,卡车3负责3个点,此时选择卡车2和卡车3进行点组变异,即卡车1负责5个点,卡车2负责3个点,卡车3负责6个点,如图6所示。

图6 策略a示意

策略b:除了对救援工具所负责点组进行变异操作外,对点组内部也进行相应的变异操作。采用2点互易方式,随机产生2个自然数并交换其对应的点值,如图7所示。

图7 策略b示意

4)将模拟退火算子引入遗传算法中,设置算法终止条件。通过模拟退火算法中的降温操作寻找全局最优解,并根据模拟退火算法中的Metropolis准则进行新解e1和原解e的适应度值比较,ΔE=fe1-fe,若ΔE>0,则新解将被接收,用新的解e1替换当前解e,若ΔE<0则按照min{1,exp(-ΔE/T)}>rand[0,1]的概率选择接收或舍弃该解。

3 案例分析

3.1 算例设置

表3 配送中心与各受灾点间的相对距离

表4 救援设备参数

图8 震中区域需求点位置

3.2 算例结果与分析

将遗传模拟退火算法的参数设置如下:群体个数N= 200,交叉概率= 0.8,变异概率= 0.06,最大迭代次数Gen = 300,初始温度T0= 1 000,降温系数= 0.99。由于地震灾害具有很强的时效性,因此将最小配送总时间设置较高的权重,最优值为最小配送时间和最小成本经过标准化处理后进行加权的综合考量。使用Python软件进行传统遗传算法与本文遗传-模拟退火算法(GA-SA算法)的对比求解,最优值的变化收敛情况如图9所示。

图9 算法迭代对比

由图9可以看出,本文GA-SA算法相对于传统遗传算法收敛效果更好。图10为第三时段下的结果路径对比图,通过表5与遗传算法相比较,总配送成本降低了9.53%,配送总时间减少了7.03%,表明在考虑道路损毁修复的震后多时段应急物资配送背景下,本文算法具有更好的求解效果,所得出的路径图比传统遗传算法路径图更加合理,车辆分区规划更加明确,配送时间更短。

表5 算法结果对比

图10 第三时段下路径对比

以第三时段下不同算法具体路径方案为例,对表5中的路径结果相关含义进行简要阐述。第三时段下,表示有5辆车和1架直升飞机所各自负责的点,如第1辆车负责点为[9,2,1,3,19,15,…,12,6,5,4]中的[9,2,1],第2辆车负责点为[3,19,15,14,13],其他救援设备负责路径与上述规划相应,不再过多赘述。具体路径方案如表6所示。

表6 第3时段下具体路径方案

3.3 考虑时段情景分析

由于地震灾害应急救援是一项时效性较强的工作,越短时间内完成配送任务越能够救治更多的伤员,因此,对震后“黄金72小时”采取划时段安排救援方案尤有必要。划分时段的方法能够及时获取道路的通畅程度变化,及时对配送方案的路线进行更新,以更短的时间完成配送任务,提高应急救援物资配送的效率。为了验证考虑时段因素情景下应急物资配送更有效率与否,本文对比了考虑时段和不考虑时段情景的结果,如表7所示。

表7 考虑时段和不考虑时段情景结果对比

通过对比发现,考虑时段情景下的应急物资配送任务在配送总时间上比不考虑时段情景下减少了6.33%;在配送总成本上比不考虑时段情景降低了18.9%。

本文方法将灾后救援物资配送阶段进行了时段划分,考虑了道路通畅程度与震中位置关系,对震后一定时段及配送路径方案进行设计,结合地震实例相关数据进行对比分析,验证了本文算法及模型的有效性。

4 结 论

在震后应急物资配送情景下,本文以应急物资总配送时间最小为主,将最小化配送成本考虑在内,采取划分多时段的方法对配送方案进行更新和优化。由于地震灾害的强时效性,通过划分时段的方法构建模型能够提高救援物资配送效率,及时将抵达灾区的救援物资送至需求点,避免资源的停滞浪费。将遗传算法与模拟退火算法相结合对所构建模型进行求解,使用地震实例相关数据进行算例验证和对比分析,得到以下结论。

1)考虑划分时段的方式构建模型,更具有解决震害后物资配送问题的针对性,结合道路损毁条件,能够为特定情景提供物资配送方案。

2)采用联合配送的方式,不但能够满足一般受灾点的物资需求,还能够应对特殊情景下的需求,当仅依靠车辆无法到达时,联合配送能够提供一种更有效的解决方法。

3)混合算法优于传统遗传算法,具有更好的收敛性,在特定情景下能够减少配送时间和降低配送成本,具有更强的实效性。

本文主要对震害后应急物资联合配送进行研究,但未考虑次生灾害造成的二次道路损害及需求量的动态变化等方面,这些方面还具有较大的研究空间,将成为后续研究的工作重点。

参考文献/References：

[1] 马亚伟,臧阳,韩颜颜,等.2022年震情述评[J].中国地震,2023,39(1):213-218.

MA Yawei,ZANG Yang,HAN Yanyan,et al.A review of seismicity in 2022[J].Earthquake Research in China,2023,39(1):213-218.

[2] FIKAR C,GRONALT M,HIRSCH P.A decision support system for coordinated disaster relief distribution[J].Expert Systems with Applications,2016,57:104-116.

[3] 闫森,齐金平,张儒.考虑道路受损的震后应急物资运输路径优化[J].科学技术与工程,2022,22(28):12598-12604.

YAN Sen,QI Jinping,ZHANG Ru.Optimization of the transportation route of emergency supplies after the earthquake considering the road damage[J].Science Technology and Engineering,2022,22(28):12598-12604.

[4] 狄卫民,张鹏阁,杜慧莉.考虑道路状况的应急配发站启用以及配送优化问题[J].中国安全生产科学技术,2020,16(9):12-17.

DI Weimin,ZHANG Pengge,DU Huili.Opening of emergency distribution stations and optimization of distribution considering road conditions[J].Journal of Safety Science and Technology,2020,16(9):12-17.

[5] 孟燕萍,申慢慢.考虑灾后道路恢复情况下动态应急物资选址问题[J].重庆交通大学学报(自然科学版),2019,38(1):89-96.

MENG Yanping,SHEN Manman.Location of dynamic emergency materials in the case of road rehabilitation after disaster[J].Journal of Chongqing Jiaotong University(Natural Science),2019,38(1):89-96.

[6] 张梦玲,王晶,黄钧,等.基于手机定位数据的突发事件下道路修复和物资配送集成优化研究[J].中国管理科学,2021,29(3):133-142.

ZHANG Mengling,WANG Jing,HUANG Jun,et al.Research on the integrated optimization of road repair and relief distribution based on mobile phone location data[J].Chinese Journal of Management Science,2021,29(3):133-142.

[7] 谭洁,李文莉,刘康康.考虑二次灾害的开放式应急物流车辆路径问题[J].系统工程,2021,39(2):61-71.

TAN Jie,LI Wenli,LIU Kangkang.The open vehicle routing problem of emergency logistics considering secondary disasters[J].Systems Engineering,2021,39(2):61-71.

[8] 赵建有,肖宇,朱欣媛,等.考虑需求紧迫度的应急车辆路径优化方法[J].哈尔滨工业大学学报,2022,54(9):27-34.

ZHAO Jianyou,XIAO Yu,ZHU Xinyuan,et al.Route optimization method for emergency vehicles considering demand urgency[J].Journal of Harbin Institute of Technology,2022,54(9):27-34.

[9] AHMADI M,SEIFI A,TOOTOONI B.A humanitarian logistics model for disaster relief operation considering network failure and standard relief time:A case study on San Francisco district[J].Transportation Research Part E:Logistics and Transportation Review,2015,75:145-163.

[10] 曲冲冲,王晶,黄钧,等.考虑时效与公平性的震后应急物资动态配送优化研究[J].中国管理科学,2018,26(6):178-187.

QU Chongchong,WANG Jing,HUANG Jun,et al.Dynamic emergency materials distribution optimization with timeliness and fairness objective for post-earthquake emergency rescue[J].Chinese Journal of Management Science,2018,26(6):178-187.

[11] 张立,贺明玲,尹秋霜,等.不确定条件下多周期应急物资配送优化研究[J].系统仿真学报,2023,35(8):1669-1680.

ZHANG Li,HE Mingling,YIN Qiushuang,et al.Research on period emergency supply distribution optimization under uncertainty[J].Journal of System Simulation,2023,35(8):1669-1680.

[12] 韩孟宜,丁俊武,陈梦覃,等.基于混合遗传算法的应急物资配送路径优化[J].科学技术与工程,2021,21(22):9432-9439.

HAN Mengyi,DING Junwu,CHEN Mengqin,et al.Optimization of emergency material distribution path based on hybrid genetic algorithm[J].Science Technology and Engineering,2021,21(22):9432-9439.

[13] 谭印,朱芸芸,苏雯洁,等.多目标应急物流双向配送的关联反馈模型仿真[J].计算机仿真,2023,40(4):134-138.

TAN Yin,ZHU Yunyun,SU Wenjie,et al.Simulation of correlation feedback model of multi-objective emergency logistics[J].Computer Simulation,2023,40(4):134-138.

[14] 李卓,李引珍,李文霞.应急物资运输路径多目标优化模型及求解算法[J].计算机应用,2019,39(9):2765-2771.

LI Zhuo,LI Yinzhen,LI Wenxia.Multi-objective optimization model and solution algorithm for emergency material transportation path[J].Journal of Computer Applications,2019,39(9):2765-2771.

[16] 孙华丽,李泽平,马腾.道路修复联合应急设施选址-路径鲁棒优化研究[J].系统工程理论与实践,2023,43(9):2701-2713.

SUN Huali,LI Zeping,MA Teng.Robust optimization of joint road restoration and emergency location-routing[J].Systems Engineering-Theory &Practice,2023,43(9):2701-2713.

[18] 沈晓冰,杨保华.基于双层混合联运的震后应急物资配送模糊多目标优化[J].工业工程,2017,20(3):113-117.

SHEN Xiaobing,YANG Baohua.A fuzzy multi-objective optimization of post-earthquake emergency logistics systems based on bi-level programming and mixed transportation[J].Industrial Engineering Journal,2017,20(3):113-117.

[19] HU Shaolong,HAN Chuanfeng,DONG Z S,et al.A multi-stage stochastic programming model for relief distribution considering the state of road network[J].Transportation Research Part B:Methodological,2019,123:64-87.

[20] 薛星群,王旭坪,韩涛,等.考虑通行约束和运力限制的灾后应急物资联合调度优化研究[J].中国管理科学,2020,28(3):21-30.

XUE Xingqun,WANG Xuping,HAN Tao,et al.Study on joint dispatch optimization of emergency materials considering traffic constraints and capacity limits[J].Chinese Journal of Management Science,2020,28(3):21-30.

[21] 祁明亮,秦凯杰,赵琰.雪灾救援物资车辆-直升机联合运送的调度问题研究[J].中国管理科学,2014,22(3):59-67.

QI Mingliang,QIN Kaijie,ZHAO Yan.Research on problem of scheduling of helicopter coordinated with vehicle for resources distribution in snowstorm[J].Chinese Journal of Management Science,2014,22(3):59-67.

[22] 李双琳,马祖军,郑斌,等.震后初期应急物资配送的模糊多目标选址-多式联运问题[J].中国管理科学,2013,21(2):144-151.

LI Shuanglin,MA Zujun,ZHENG Bin,et al.Fuzzy multi-objective location-multimodal transportation problem for relief delivery during the initial post-earthquake period[J].Chinese Journal of Management Science,2013,21(2):144-151.

[23] 唐悦琳.考虑道路损毁度的地震应急物流选址-路径优化研究[D].重庆:重庆大学,2021.

TANG Yuelin.Research on Earthquake Emergency Logistics Location Routing Problem Considering Road Damage Degree[D].Chongqing:Chongqing University,2021.

[24] LIU Hongbin,SONG Guopeng,LIU Tianyu,et al.Multitask emergency logistics planning under multimodal transportation[J].Mathematics,2022,10(19).DOI:10.3390/math10193624.