安聪琢,王玖河,2*
(1.燕山大学经济管理学院,秦皇岛 066004; 2.燕山大学京津冀协同发展管理创新研究中心,秦皇岛 066004)
近年来,突发性公共卫生事件频繁发生,从2003年的非典、2019年的埃博拉病毒到2020年蔓延至全球的新型冠状性肺炎。突发公共卫生事件严重影响了国际经贸往来,危及了人类的健康和安全。公共卫生事件发生后如何高效有序的展开应急救援工作已成为全球的重要问题,其中最重要的是如何确保医疗资源的供给性和可得性,通过救援行动效率的最大化来实现生命损失的最小化[1]。相对于商业物流来说,医药物资的应急配送更为复杂,它不仅仅表现在时间的紧迫性,还要求在设计物流配送系统时不仅仅要考虑成本,更重要的是要兼顾效率与公平[2],因此,采用何种配送方式高效的将应急物资配送到各疫区以控制疫情扩散是我们需要解决的关键问题,具有重要的理论意义和现实价值。
目前,中外学者对于应急物资的配送问题已经有了较为深入的研究。戚孝娣等[3]以调配系统损失最小化为目标建立了三级调配网络下的供需不平衡条件下区域应急物资调配模型,并将惯性权重非线性变化策略(nonlinear inertia weight,NIW)与粒子群优化算法(particle swarm optimization,PSO)相结合,采用PSO-NIW算法进行求解。Yu等[4]针对灾害后的应急资源分配调度问题,建立了考虑人道主义的动态规划模型,并提出了一种具有循环序列特征的最优配送模式。Zhang等[5]以最小配送成本为目标,建立了考虑驾驶员连续工作能力的应急物资路径优化模型,并采用了蚁群算法进行求解。康斌等[6]将救援公平性、道路可靠性考虑在内,建立了突发事件下多目标应急物资配送路径规划模型。唐红亮等[7]以地震应急救援为背景,建立了以配送效率最大化、负载率最大化、公平性最大化为目标函数的多目标调度优化模型,并采用了粒子群算法进行求解。朱莉等[8]将受灾者和决策者的异质性行为考虑在内,建立了多阶段灾后物资救援分配与路径优化模型。
在以突发性公共卫生事件为背景的医疗资源优化配置方面,He等[9]改进了易感者-潜伏者-感染者-痊愈者传染病动力模型(susceptible-exposed-infected-recovered,SEIR),提出了基于改进的SEIR模型的应急物资时变预测模型,并使用了线性规划模型用于公共卫生事件快速反应的分配决策。Dasaklis等[10]以天花疾病为背景,提出了一种将预定的疫苗储备最优分配给疫区的线性规划模型,用于解决多个区域的有限可用资源的调度问题。吴亚琼等[11]基于SEIR模型以延迟成本最小化为目标构建了应急救援时空网络模型用以优化救援车辆路径和物资调配问题,并采用了Benders算法对模型进行了求解。李智等[12]以传染病扩散模型作为研究出发点,建立了救援物资的储备和配送模型,用以研究应急救援物资的运输时间、疫苗接种率与疫情扩散之间的影响关系。胡晓伟等[13]针对新冠肺炎疫情防控中物资分配不合理问题,建立了考虑物资运输距离与受灾点需求满足率的医疗物资动态分配模型,并通过算例验证了模型的合理性。
综上,以往对于灾害发生后的应急物资配送问题的研究中,大多数都是单纯地考虑物资分配中心对各受灾点的纵向配送,鲜有研究考虑各受灾点之间的横向物资调配问题。事实上,当某地发生公共卫生事件后可能会导致疫情在一定范围内扩大,若单纯的考虑物资分配中心对各受灾点的纵向配送模式,可能会出现配送时间过长的问题,难以满足受灾点对应急物资的时间紧迫性需求。基于此,现考虑横纵结合的配送模式,将物资分配中心对各受灾点的纵向配送与受灾点之间相互的横向配送相结合,建立横纵结合的应急物资配送模型,并采用引入逆转操作的遗传算法进行求解,通过算例分析对该模型的有效性及可行性进行验证。
假设某地发生突发性公共卫生事件,致使10个疫区感染。外界物资运送至总物资分配中心,由物资分配中心再进行二级配送至各个疫区受灾点的物资接收点。由于重大卫生事件需要考虑救援的时效性,在物资分配中心收到物资之前,可令各疫区受灾点之间先相互进行横向配送,使得距离物资分配中心较远的疫区优先得到一部分物资以缓解疫情,待外界物资送达物资分配中心后,再进行从物资分配中心到疫区受灾点之间的纵向配送,以补足各疫区受灾点的物资缺额。本文主要研究的是在各疫区受灾点和物资分配中心的地理位置及物资需求量已知的情况下,在满足一定的约束条件下,采用纵横结合的应急物资配送模式下成本最低时的具体配送方案。
1.2.1 模型假设
(1)选用不同型号的车量进行配送。
(2)车辆匀速行驶。
(3)每个物资接收点在每一环节只能接受一次配送车辆且配送结束后必须返回物资分配点。
(4)不考虑偶然因素影响。
(5)只考虑医药物资的配送问题。
(6)各疫区在疫情发生之前就已储备一定的应急物资以备不时之需。
1.2.2 参数设定
K表示车辆类型的集合,K={1,2,…,l},k∈K;
M表示车辆编号的集合,M={1,2,…,p},m∈M;
I表示节点编号的集合,I={0,1,2,…,n},i,j∈I,其中0表示物资分配中心,其余节点表示疫区受灾点I′,I′={1,2,…,n},i′∈I′;
dij表示任意节点i到节点j的距离(i≠j);
gk表示k类型车辆完成配送任务所需固定成本;
sk表示k类型车辆单位距离内的运输成本;
vk表示k类型车辆的单位行驶速度;
a表示单位车辆单位时间的延迟惩罚成本;
Lk表示k类型车辆的最大载重量;
Qi表示疫区受灾点i的物资需求量;
t表示发车时刻;
[—,—,LTi,LLTi]表示疫区受灾点i的时间窗要求;
1.2.3 配送成本分析
(1)固定成本。主要包括车辆驾驶员、装卸人员等各种工作人员的工资以及车辆的正常损耗。车辆的固定成本仅与发车数目相关。所有车辆完成配送任务所需的固定成本为
(1)
(2)运输成本。主要包括车辆的油耗费用以及轮胎损耗费用。车辆的运输成本与运输距离成正比。所有车辆完成配送任务所需的运输成本为
(2)
(3)惩罚成本。由于突发性公共卫生事件对于应急物资的时效性要求较高,物资越早到达越能尽快缓解疫情,因此,不设置时间窗的最早到达时间,只设置延误送达时间为[LTi,LLTi],其中LT为期望到达时间,LLT为最迟到达时间。若车辆送达时间早于LTi,则惩罚成本为0,若车辆送到时间晚于LLTi则物资起不到作用,拒绝接受配送。所有车辆延迟到达所有疫区受灾点的惩罚成本为
(3)
1.2.4 模型建立
综上所述,研究问题可以表示为
(4)
s.t.
(5)
∀k∈K,∀j∈I
(6)
(7)
(8)
(9)
(10)
(11)
(12)
在该模型中,式(4)为目标函数,其目标是使总成本最小,其中总成本包括车辆的固定成本、运输成本、惩罚成本;式(5)表示车辆的载重约束,表示每辆车都不能超载;式(6)表示车辆到达疫区受灾点后必须离开疫区受灾点;式(7)和式(8)表示每个疫区受灾点只能被一辆车进行配送服务;式(9)表示车辆必须最迟到达时间前完成配送;式(10)~式(12)表示0-1决策变量。
遗传算法(genetic algorithm,GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法的优点在于操作简单,搜索从群体出发,具有潜在的并行性和全局搜索能力。
考虑到常规的变异算子可能出现陷入局部最优解、忽略较小概率的个体等不稳定情况,本文选用改进的变异算子,将变异步骤分为交换变异、逆转变异和插入变异三步。改进后的遗传算法步骤如下。
Step 1染色体编码。在本研究设计的遗传算法中,选用实数编码,0表示物资分配中心,1~10表示物资接收点。如0~1~7~4~0表示该次配送从物资分配中心出发,依次经过第1、7、4号物资接收点后返回物资配送中心。
Step 2计算适应度。适应度越大被选择概率越高,由于目标函数是求最小值,因此选取目标函数的倒数作为适应度函数,即1/C。
Step 3选择。采用保留最佳个体与轮盘赌选择法相结合的方式选择染色体[14],具体操作过程如下。
(1)以适应值函数的值为序,使染色体由好到坏进行重排,fh越大,则染色体h越好,其序号越小。设参数a∈(0,1)给定,定义基于序的评价函数为
eval(hi,fhi)=a(1-a)i-1,i=1,2,…,n
(13)
i=1时染色体最好,i=n时染色体最差。选择序号为1的染色体复制到下一代,其余染色体按以下步骤操作。
(2)对每个染色体hi计算累计概率pi,即
(14)
(3)产生随机实数r∈(0,pn)。
(4)若pi-1 (5)重复(3)和(4)n-1次,得到n-1个染色体。 Step 4交叉。选用两点交叉,即所选父代染色体交叉点间的基因互换。 Step 5变异。选用改进的变异算子,将变异步骤分为交换变异、逆转变异和插入变异三步。 (1)交换变异,即常规的变异算子,在染色体内随机取两个不稳定基因进行互换,假设变异位为第2基因位与第6基因位,则 (2)逆转变异,即随机选取逆转区间,对逆转区间的基因取倒序后重新计算该染色体的适应度,并与原适应度比较,若适应度得到提升则保留新染色体,否则保留原染色体。逆转操作有助于提高种群的多样性,防止陷入近亲繁殖。假设逆转区间为第3~7位基因,则 (3)插入变异,考虑到轮盘赌选择法容易漏掉小概率个体,故在逆转变异后进行插入操作,将按适应度降序排列染色体的前n条(n为父代与子代种群规模的差值)选中,与上述步骤形成的子代种群结合,形成新的种群,示例如下。 ①插入前。 父代种群: 127298116349211527461 子代种群: 19856311742861 父代种群3条染色体对应适应度分别为9、12、8,进行降序排列后为12、9、8,分别代表第2、1、3条染色体。 ②插入后。 163492119856311742861 Step 6终止 当算法计算过程中多次输出同一结果或算法运行到达最大迭代次数时终止计算,输出最优解。 假设某地发生了一起传染病事件,共致使10地发生感染。各疫区受灾点以及物资分配中心的地理位置如表1所示,其空间位置分布如图1所示;各疫区受灾点的物资需求情况以及时间窗要求如表2所示;车辆及算法的相关参数如表3所示。 表2 各节点物资需求情况与时间窗要求 表3 车辆及算法相关参数 图1 各节点空间位置分布 3.2.1 横纵结合的配送模式 1)聚类分析 在进行物资配送之前,先对各疫区受灾点进行聚类分析,聚类依据是各受灾点与物资分配中心的距离,聚类方法是组间连接法。根据表1中的数据,采用SPSS软件进行聚类分析,聚类结果如图2所示。 表1 各节点地理位置 由图2可知,当选取距离为13时,按照与物资分配中心的距离,可将疫区受灾点分为3类,分类结果如表4所示。其中类别1为一类疫区受灾点,距离物资分配中心最近,类别2为二类疫区受灾点,距离物资分配中心适中,类别3为三类疫区受灾点,距离物资分配中心最远。 表4 各疫区受灾点分类结果 图2 各疫区受灾点聚类分析 2)横向配送分析 由于此时是物资到达之前的内部横向配送,故此阶段配送暂不考虑时间窗问题,由于横向配送所运物资量小,故选用固定成本为50元的小型车辆进行配送。一类疫区受灾点和二类疫区受灾点在物资满足率高于50%时,可以将部分物资调配至三类疫区受灾点,当物资满足率低于50%时,为保障该点的日常救灾需求则不再从该点调出物资。当二类疫区受灾点和三类疫区受灾点的物资满足率低于50%时,可接受由其他疫区受灾点调配来的物资,当物资满足率高于50%时,则不接受各疫区受灾点的物资援助。 由表2可知,各疫区受灾点的物资满足率如表5 所示。 表5 各节点物资满足率 由表5可知,物资满足率高于50%的疫区受灾点编号为2、4、7、8、10,由于2、7号为三类疫区受灾点,故不向其他受灾点配送物资;4、10号受灾点可向二、三类疫区受灾点进行配送,8号受灾点可向三类疫区受灾点进行配送。即编号为4、8、10的疫区受灾点给编号为1、3、5、6、9的疫区受灾点进行配送。配送采用就近原则,即先向距离近的需求点配送,若配送完毕仍有余量,再依次配送远距离需求点。部分疫区受灾点之间的距离如表6所示。 表6 各疫区受灾点间的距离 对上述数据进行分析计算,横向配送结果如下:受灾点4给受灾点3配送70 kg物资,受灾点10给受灾点3配送10 kg物资,此时受灾点4和受灾点10的物资满足率均低于50%,故不再为其他受灾点(1、9、5)进行物资援助。受灾点8给受灾点1配送40 kg物资,给受灾点5配送30 kg物资,此时受灾点8的物资满足率低于50%,也不再为其他受灾点提供物资援助,横向配送结束。 运行模型,依据式(1)~式(11)运用MATLAB2019a 编程计算可知横向配送方案成本对比如表7所示。 表7 横向配送方案成本对比 通过表7的比较分析,最终确定的横向配送方案为:共派出两辆车,1号车行驶路线为10-4-3,配送成本为83.03元;2号车行驶路线为8-1-5,配送成本为134.48元,横向配送总成本为217.51元。 3)纵向配送分析 经过各疫区受灾点之间的内部横向配送后,疫区受灾点1、3的物资缺额为0,无需再进行纵向配送,疫区受灾点5的物资缺额变为90;疫区受灾点4、8、10由于为其他受灾点输送物资,物资缺额分别变为90、100、75,此时物资分配中心只需给编号为2、4、5、6、7、8、9、10的疫区受灾点进行纵向配送。各疫区受灾点的物资需求及时间窗要求如表8所示;采用MATLAB2019a进行编程计算,计算结果如表9所示;纵向配送路径如图3所示。 图3 纵向配送路径图 表8 各疫区受灾点的物资需求及时间窗要求 表9 纵向配送方案 因此,纵向配送的总成本为1 733.512元,横向配送总成本为217.510元,故横纵结合配送模式下的总成本为1 951.022元。 3.2.2 常规配送模式 常规配送模式即为单配送中心的车辆路径问题中仅考虑物资分配中心与疫区之间的配送问题,不涉及疫区与疫区之间的横向配送。本文将常规配送模式与纵横结合的配送模式进行对比研究,以表2中各疫区的初始需求量数据及时间窗要求为依据,运用MATLAB2019a进行编程,计算常规配送模式下的配送方案,计算结果如表10所示;常规配送模式下的配送路径图如图4所示。 图4 常规配送模式下配送路径图 表10 常规配送模式下的配送方案 因此,常规配送模式下的总成本为2 185.376元。 3.2.3 两种配送模式比较分析 横纵结合配送模式与常规配送模式对比分析如表11所示。 由表11可知,相比常规配送模式,所提出的横纵结合的配送模式可使总成本降低234.354元,降低率为10.72%,其中惩罚成本降低率为52.98%,这充分说明了该配送模式更能满足应急物资的时效性要求。各疫区之间的内部横向配送,可以使一些距离物资分配中心较远的疫区受灾点更早获得救援物资,避免因救援不及时而带来各大的损失,缓解了救援压力,降低了配送成本。 表11 两种配送模式成本对比 以突发性公共卫生事件为背景,考虑到应急救援物资的时效性问题,提出了横纵结合的应急物资配送模式,在横向配送中,根据疫区受灾点与物资分配中心的距离进行聚类分析,实现不同类别的疫区与疫区之间的内部横向配送,在救援物资到达物资分配中心后进行纵向配送,以补足各疫区之间的物资缺额。根据该配送模式,以总成本最小为目标函数,建立了应急物资配送模型,并采用改进的遗传算法进行求解,最后通过算例分析验证了该模型的有效性。 通过算例模拟可知,本文提出的横纵结合的配送模式相比于常规配送模式,惩罚成本降低了52.98%,总成本降低了10.72%。由于横向配送会使部分疫区受灾点的需求量得到满足,因此相比于常规配送模式,在纵向配送中需要服务的疫区受灾点会变少,所以,在其他参数不变的情况下,横纵结合的配送模式所节约的成本会随着节点距离及数量的增加而增加。 本文是在各疫区受灾点物资需求量已知的情况下进行物资配送的,实际上,由于突发性公共卫生事件具有衍生性和传染性的特点,各受灾点的物资需求量是动态变化的,对于应急物资尤其是医药物资的需求也不能简单的通过一次性配送而完成,因此,考虑时变需求下的多周期的应急物资配送问题将是未来的研究方向。3 算例分析
3.1 参数确定
3.2 模型求解
4 结论