医疗应急物资车辆配送优化调度时间窗模型研究*

吴 坷，宋英华，吕 伟

(1.武汉理工大学 中国应急管理研究中心，湖北 武汉 430070；2.武汉理工大学 安全科学与应急管理学院，湖北 武汉 430070)

0 引言

突发事件的发生不仅会对人类的正常生活造成巨大的影响，并且严重情况下还会造成社会的重大人员伤亡以及经济损失。如2020年发生的新冠肺炎疫情，截至2020年3月份，疫情仅发生2个月，武汉的新冠肺炎确诊人数就已高达48 137人，死亡2 132人，GDP增速相比2019年同期下降超过2%[1]。应急物资配送是突发事件应急过程中1项很重要的因素，其影响着整个应急环节的效率，同时，保证应急配送效率是面对突发事件采取行动成效的关键一环。

在满足时间窗约束的应急物资车辆配送研究方面，国内外学者目前已做了大量研究，对于时间窗下的应急物资配送路径问题的研究，主要包括受灾点需求时间窗约束问题[2-6]和配送成本及距离最小等问题[7-9]。在考虑时间窗的车辆配送路径研究中，Maxmilian Marius等[10]在研究考虑车辆路径问题时，最先提出了时间窗的想法，并运用启发式算法进行求解；李善俊等[11]求解多目标车辆路径优化模型时，考虑了车辆载重、时间窗、生鲜品保质期等多约束条件，并运用改进的非支配排序遗传算法进行求解；蒋禄欢[12]提出需求拆分、多时间窗和集送货同时约束的车辆配送模型，解决了考虑时间或距离的单一约束条件不足的情况；鲍伟等[13]以车辆和车辆运输及等待时间惩罚3者成本最小为目标，建立软时间窗约束下的多车型车辆配送模型；Yannis等[14]研究带时间窗的配送路径时提出了1种多自适应粒子群优化算法，该算法采用了3种不同的自适应策略；曹庆奎等[15]考虑实际交通中交通流和客户时刻发生改变的情况，对交通流的多模糊时间窗车辆路径问题展开研究；吕伟等[16]考虑不同需求点的不同时间窗，以最大化时间和需求的满意度为目标，兼顾救援的公平性原则，运用亚当斯的公平分配理论进行计算；王涛等[17]考虑车辆配送问题时，以配送费用和配送车辆数最少为条件，提出改进的智能水滴遗传混合算法；庞燕等[18]构建双目标数学模型，考虑行驶距离和车辆数最少，提出改进的2阶段禁忌搜索算法进行求解；戴意愿等[19]考虑乘客运输车辆路径规划问题时，对乘客运输需求不定以及出发站点和目标站点的随机性，提出基于粒子群算法的车辆路径规划策略。

在整个应急物资配送系统中，配送过程往往不是独立存在的，而是会受到很多因素的影响，其中考虑时间窗约束与配送车辆的数目结合，得到整体优化调度协同方案较少。在突发事件发生后，需同时考虑不同时间窗约束和最少配送车辆数即最少数目的配送通路，才能更全面地、更合理且高效地完成整体路网的应急物资配送。

本文提出的考虑时间窗影响的应急物资车辆优化调度方案，所快速得到完整的应急物资车辆优化调度模型，使得所需的应急物资能在要求的时间窗内抵达目的地，同时保证因为车辆数目及配送路径造成的成本最低。

1 问题描述

1.1 本质问题

突发事件发生后，在任一路网中，存在多个应急物资配送中心和应急物资需求点，现将储备在各个应急物资配送中心的应急物资按照时间窗的要求，由车辆配送至各个物资需求点，在多个单循环配送路径中，找到最少数目的配送车辆即配送通路(将可有1辆车完成的多个单循环配送连接起来，成为1个配送通路)。

1.2 多配送中心车辆配送问题

考虑更加符合实际城市交通路网情况的应急物资车辆配送问题，即存在多个应急物资配送中心的供给时间窗应急物资车辆配送问题。

配送示意图如图1所示。

图1 配送示意Fig.1 Schematic diagram of distribution

如图1所示，在1个路网中，有多个配送中心和物资需求点。从某1配送中心出发的车辆需在时间窗[ET，LT]抵达相对应的物资需求点后，返回该配送中心方可对下一物资需求点进行配送，同时到达各物资需求点的时间均满足该点时间窗要求。存在车辆在配送中心的等待时间，在此情况下得到多种配送方案，最终找出最少配送车辆，即最少配送通路。

图1中，O为配送中心；D为需求点；[ET，LT]为物资需求点的约束时间窗，其中ET为要求的物资最早到达时间(ET可以为0)，min；LT为要求的物资最晚到达时间，min；l为配送道路，km；虚线为省略的配送中心和配送需求点及配送路线。

2 模型研究

2.1 模型假设

侧重研究突发事件下，时间窗约束对应急物资配送路径的综合影响，考虑配送车辆数最少即通路数最少的情况，并作如下假设:

1)配送中心储备充足，对需求点的单独配送可满足需求量。

2)从配送中心至物资需求点配送的车辆容量足够大即单车运力可完成1次配送。

3)各物资需求点的需求物资种类不同，不存在沿路配送的可能，所有配送车辆均需完成对当前需求点的配送任务后返回配送中心，方可为新的需求点服务。

4)各物资需求点对物资的需求存在时间窗，物资必须在要求的时间窗内送达方为有效。

5)路网确定，不考虑道路损毁，交通状态良好。

6)配送车辆的配送速度一定，且均速进行配送。

7)在配送过程中需满足时间窗要求；因存在车辆从0时出发时到达需求点时不满足时间窗要求，故存在车辆在配送中心的等待时间。

8)在车辆配送时，因为车辆有限，优先配送等待时间短的需求点，即满足7)的所有需求点中，优先配送等待时间短的需求点。

2.2 模型构建

相关符号说明如下

1)集合

O={i|i=1,2,…,n}为配送中心集合；

D={j|j=1,2,…,n}为物资需求点集合；

R={m|m=1,2,…,n}为配送道路集合；

H={h|h=1,2,…,n}为物资配送车辆集合。

2)相关参数

lij表示从配送中心Oi到物资需求点Dj的距离最短路径长度，km；

dRm表示路段Rm的长度，km；

vRm表示路段Rm的车辆实际行驶速度，km/h；

wh表示车辆h在配送中心等待的时间，min。

ETj表示Dj要求物资到达的最早时间，min；

ELj表示Dj要求物资到达的最晚时间，min；

TOiDj表示从起点Oi出发，到点Dj的所用的时间，min；

FOiDj表示从起点Oi出发，到点Dj然后返回Oi点的过程所用的时间，min；

FjOiDj表示需求点Dj被完成配送时，配送车辆返回起点Oi所需的时间，其中共经过j个需求点，min；

k表示完成配送点Dj时的上1个完成配送的需求点。

3)目标函数

目标函数如式(1)所示：

(1)

式(1)目标函数表示车辆优化调度方案所使用的车辆数最小。

式(2)～(6)为约束函数：

ETj≤Fj-1OiDk+TOiDj+wh≤ELj

(2)

(3)

(4)

(5)

(6)

式(2)表示完成物资需求点Dj配送所需满足的时间窗约束，其中当j-1为0时，Fj-1ODk=0；式(3)表示对于任意车辆只能使用1次；式(4)表示对于任意1个需求点，只能被1辆车配送1次；式(5)表示对于任意1个需求点Dj只有1个配送中心点Oi为其提供物资;式(6)表示对于任意1个配送中心Oi至少对1个受灾点Dj进行物资配送。

式(2)中参数如式(7)～(8)所示：

TOiDj=dRij/vRij

(7)

FOiDj=2TOiDj

(8)

在该模型中，dRm，vRm，ETj，ELi是已知量，lij，TOiDj是可观测量。

2.3 问题求解

针对所构建的数学模型，设计如下求解方案：

1)计算路网中所有配送中心Oi到对应物资需求点Dj的所有最短路径集合R；

2)根据R计算从配送中心Oi出发到相应物资需求点Dj的所有配送时间TOiDj(从物资需求点返回至配送中心的时间与配送中心出发至物资需求点的时间一致；

3)运用MATLAB编程满足模型要求的代码，将路网信息，如时间窗约束条件，道路信息集合R，配送时间TOiDj导入编号的程序模型中，可得到车辆优化调度方案；

4)得到的优化调度方案中包括最少配送车辆、车辆对应出发点及对应配送编号、需求点等待时间集合、车在配送中心的等待时间集合；

5)对比各个优化调度方案，通过对比成本可以得到各个方案的优劣排序，从而得到最优方案。

3 情景应对分析

3.1 情景构建

2020年1月23日上午10时，武汉市因新冠肺炎疫情影响，最先开始“封城”，截止1月26日，湖北城市地区都进入“封城”状态。因疫情发生，湖北省各地出现防疫物资紧缺的情况，由于“封城”影响，交通不畅。假设防疫物资集中在应急物资储备中心处，需由应急车辆统一进行防疫物资配送，湖北省疫情灾害情景如表1所示。

表1 湖北省疫情灾害情景简介Table 1 Brief introduction of epidemic disaster scenario in Hubei province

选取湖北省13个地级行政区以及4个省直辖县级行政单位作为研究对象，以湖北省经济较发达的3个市作为应急资源配送中心，分别是武汉市、宜昌市、襄阳市，以这3个配送中心向其他地区进行应急物资配送，如图2所示；然后根据实际路网信息建立拓扑图，如图3所示。

图2 湖北省防疫物资配送网络Fig.2 Distribution network of epidemic prevention materials in Hubei province

图3 湖北省配送路网拓扑Fig.3 Topology diagram of distribution road network in Hubei province

3.2 应急物资车辆优化调度方案求解

该路网共3个应急物资储备中心，14个应急物资需求点，18段路，由配送中心出发沿高速公路行驶至配送点的实际距离，可知每条配送道路的实际距离，车辆平均速度取100 km/h，根据每条道路的距离，则可得到车辆在该段道路所行驶的时间，结果取整数，路网及车辆行驶时间的具体信息如下表2所示。

表2 车辆行驶道路信息Table 2 Information of vehicle driving roads

为方便研究，随机拟定每个应急物资需求点的时间窗要求区间，允许时间窗起始时间为0，具体信息如下表3所示。

表3 防疫物资需求点信息Table 3 Information of demand points for epidemic prevention materials

运用MATLAB R2016b编程进行方案求解步骤的处理，求解目标函数进行计算，经过多次运行后得到运行结果，运行结果显示，最少配送车辆数为11辆，共有8种配送方案，车辆具体分配情况如表4所示：

表4 配送车辆分配情况Table 4 Assignation of distribution vehicles

湖北省防疫物资配送车辆优化调度方案如表5所示，括号内为车辆在配送中心等待的时间；“；”隔开的配送路径指的是从该配送中心出发，不同车辆完成的1次配送通路。

从表5可得，方案1中，第1辆车从O1，0时出发开始配送D1；第2辆车从O1，0时出发开始配送D2；第3辆同理可得方案2～方案8的车辆优化调度方案。

表5 湖北省防疫物资配送车辆调度方案Table 5 Scheduling scheme for distribution vehicles of epidemic prevention materials in Hubei province

车从O2，0时出发开始配送D3；第4辆车从O2，等待1 min后出发依次配送D4，D7；第5辆车从O2，0时出发配送D6；第6辆车从O3，0时出发配送D5；第7辆车从O3，等待5 min后出发依次配送D8，D13；第8辆车从O3，等待12 min后出发配送D9；第9辆车从O3，0时出发配送D10；第10辆车从O3，0时出发配送D12；第11辆车从O3，0时出发依次配送D14，D11。

在得到该路网在时间窗约束条件下，最少可由11辆车完成所有需求点的配送以及8种不同的配送方案，现对比这8种方案的车辆行驶距离，计算配送成本，可得到最优方案及优劣排序。表6为这8个方案的总配送距离。

表6 配送距离对比Table 6 Comparison of distribution distance

由表6可知，因方案2的配送总成本最少，所以方案2为最优方案。方案2的配送示意如图4所示，图中直线双箭头为车辆单独配送的路线，黑色曲线箭头和黑色虚线箭头为由1辆车完成的需求点配送，序号①～④表示车辆行走路线顺序。

图4 方案2配送示意Fig.4 Schematic diagram of distribution with scheme 2

4 结论

1)在原有时间窗要求的车辆路径问题基础之上突破传统的单时间窗要求对寻求最短时间路径的局限，通过考虑多时间窗的方式寻求满足实际情景要求的交通管制方式和运输路线，以寻找最优可行解。

2)将经典的LRP问题与实际道路交通配送时的车辆问题相结合，从新颖的优化车辆数的角度入手，摆脱传统理论模型拘泥于路径的重复选择和不计运输成本的假设，更加贴近于事实情景且具有现实意义。

3)在现有的基础问题之上考虑供给时间窗问题，后续研究可以继续考虑道路破损情况以及道路实时信息不断发生变化的可能，使得到的结果更加普遍及精确。