重大突发事件下应急物流车辆路径优化模型与算法

王娟 谭康业

摘  要：重大突发事件如新冠疫情、地质灾害等的爆发对我国应急物流的及时响应性与运转稳定性提出严峻挑战与要求。针对重大突发事件下应急物流配送时效性不足、系统总成本过高等问题，以车辆配送走行成本、时间成本、早到/迟到惩罚成本和出车固定成本最小化为目标，考虑各需求点收货软时间窗、车辆额定载重量、容积、车辆单次配送最大行驶里程等约束条件，构建面向重大突发事件的应急物流车辆路径优化模型;引入收敛速度改进策略、粒子搜索改进策略、精英保留改进策略，设计了一种适于求解全局优化问题的改进粒子群优化算法。仿真结果表明，利用改进的粒子群优化算法求解面向重大突发事件的应急物流车辆路径问题时，能够得到更加优化的结果。

关键词：应急物流;车辆路径优化;软时间窗;改进的粒子群优化算法;重大突发事件

中图分类号：F252.8    文献标识码：A

Abstract： A major epidemic situation such as COVID-19 or geological disaster brings severe challenges and requirements for the timely response and operational stability of emergency logistics. Basing on the problems of insufficient timeliness and high total system cost of emergency logistics distribution in major epidemic situations， taking the minimum of vehicle distribution travel cost， time cost， early/late punishment cost， and fixed cost of vehicle as the target， the soft time window for receiving goods at each demand point， the rated load of the vehicle， the volume， the maximum travel of the vehicle in a single delivery as constraints， the emergency logistics vehicle routing problem optimization model for major epidemics was constructed. The convergence speed improvement strategy， particle search improvement strategy， and elite retention improvement strategy were introduced to improve particle swarm optimization algorithm suitable for solving global optimization problems. The simulation results show that， the improved particle swarm optimization algorithm designed to solve the emergency logistics vehicle routing problem for major epidemic situation can reach optimal results.

Key words： emergency logistics; vehicle routing problem optimization; soft time window; improved particle swarm optimization algorithm; major epidemic situation

应急物流通常指的是为应对自然灾害或灾难性的突发事件，对生活用品、救援物资和人员的紧急调运安排的一类特殊的物流管理活动[1]。应急物流是应急事件反应体系中至关重要的一环，而应急车辆路径优化又是应急物流活动能否快速、准确、稳定运行的关键，是应急物流的重要组成部分。国家重大应急事件包括公共卫生事件、地质灾害、重大自然灾害等，如新冠病毒疫情期间武汉采取封城策略，对城市应急物流提出了极大挑战。SARS期间造成的损失总额约176亿美元，其中应急物流的损失高达30亿美元[2];据人民日报报道，新冠疫情爆发初期武汉出现了因物资配送中心管理不善导致应急物资发放出现诸如分配不当、分配时间过长等问题，集中体现了我国应急物流发展的短板。

当重大应急事件发生时，应急物流需要及时响应，向需求点运送应急物资，尽快满足需求点的各类需求，其中重点和难点之一就是车辆的路径优化，如何在指定时间内运送需求物资到达指定地点，是应急物流车辆路径优化要解决的主要問题。与传统车辆路径优化明显不同的一点是，应急车辆路径优化更注重时效性和准确性等特点。车辆路径问题（Vehicle Routing Problem， VRP）最早由Dantzig和Ramser[3]提出，描述的问题可概括为一定的需求点和一个起点，已知各需求点需求量和位置坐标，如何在约束条件下，选择一条最合适的最后返回起点的路径。应用到实际场景中，衍生了许多类型的VRP问题，包括含有时间窗的VRP、开放式VRP，绿色VRP、应急VRP等。国内关于应急VRP的研究最早是由欧忠文等[4]明确开始的，其首次提出了“应急物流”的概念，并清晰阐述了其内涵与研究内容等，为应急物流发展奠定了基础。陈莹珍等[5]从地区物资平衡性方面加以考虑，提出了改进的差分进化算法求解应急物资分配问题。庞海云等[6]建立了三级应急物资运输网络并提出一种改进粒子群算法，进一步完善了应急配送网络。刘长石等[7]从系统集成化的角度来完善应急物流配送问题，构建了一个多目标模糊LRP模型，旨在协同解决定位—路径优化问题。Sheu等[8]强调了应急物流的目的性、信息化和有效性。胡忠君等[9]针对城市应急物流配送问题，考虑救灾需求点物资配送可由配送中心和转运中心多源满足的情况，在实时交通信息下，以救灾时间最小和资源分配公平性最大为目标建立模型。Gutjahr等[10]第一次在应急物流中强调了物资配送与应急灾害管理间的关系优化。Jacobson等[11]在考虑时间窗、紧要程度等的情况下建立数学模型，进一步提出了应急物流的多目标优化策略。Huang等[12]建立了物流资源应急分配模型来应对灾害发生后的场景，其中考虑了生存性、延时性、公平性等三个目标。Talarico等[13]求解了灾后伤员如何分配救护车的路径优化问题模型。Wilson等[14-15]建立了同时多个灾后伤员救治目标的数学模型，对应急物流问题进行了拓展。Xian[16]根据应急物流的特性建立了相应的体系结构，对车辆路径进行合理优化。曲冲冲等[17]建立了一种应急配送中心选址与车辆路径共同优化模型。Edrissi等[18]提出一种用于评估物流网络运作性能的方法，更系统地完善了应急物流运作网络。Meysam等[19]提出了一个多目标优化模型，用于地震响应时的车辆路径优化问题。Nikoo等[20]提出了一种用于寻找最优应急车辆路线的优化模型。杨菊花等[21]针对应急物资全程调拨时路径选择问题设计了一种改进蚁群算法。对于这类问题和模型多数学者采用的主要求解方法有遗传算法[22]、模拟退火算法[23]等启发式算法及其拓展算法。

以上文獻主要研究了地震后快速响应、应急物流车辆运输、人员救援转移等问题，现有应急物流相关研究为本研究提供了基础，但重大突发事件下应急物流车辆路径优化方面，需进一步研究优化。在重大突发事件下应急物流车辆路径优化的各项影响因素的基础上，建立含有软时间窗的应急车辆路径优化模型，引入收敛速度改进策略、粒子搜索改进策略、精英保留改进策略，提出一种改进的粒子群优化算法（PSO），最后通过实例验证了该算法的有效性。

1  重大突发事件下应急物流车辆路径优化模型

在疫情发生初期，通常由省市红十字会负责应急物资的调配与发放。应急物资在配送中心集中以后，需按照各需求点的具体需求品种和数量，在指定时间范围内及时、准确送达至需求地点，因此，如何快速制定出车辆装载和配送路径，是重大突发事件下应急物流需要解决的关键问题。以车辆走行成本、时间成本、早到/迟到惩罚成本、出车固定成本等最低为目标函数，考虑收货软时间窗、车辆额定载重量、容积、车辆单次配送最大行驶里程、每个需求点的货物只能由一辆车进行配送等约束条件，构建重大突发事件下应急物流车辆路径优化模型。模型假设如下：

（1）需求点早到/迟到惩罚函数呈线性变化;

（2）需求点的货物需求量均未超过单车额定载重量和容积。

模型中的参数定义为：i为货物编号i=1，2，…，I;j为车辆编号j=1，2，…，J;p、q为需求点编号，p，q=0，1，2，…，K，d表示需求点p到q距离;k为需求点编号，k=1，2，…，K;V表示货物i的体积，单位：m3;VV为j辆车额定容积：m3;CW为p需求点第i件货物的重量;VW为j辆车额定载重，单位：kg;M为第j辆车最大行驶里程数，单位：km;VC为第j辆车在单次运输过程中的单位运输成本，单位：元;TC为单位时间成本，T表示完成单次配送所耗费的时间，A表示车辆j到达需求点k的时间，ET表示时间窗最早允许时间，LT表示时间窗最晚时间，Z表示第k个需求点的惩罚成本。Z表示单位早到惩罚成本;Z表示单位迟到惩罚成本;C表示出车单位固定成本。

应急物流车辆路径优化模型中的决策变量定义：

x=

y=

z=

构建的应急物流车辆路径优化模型如下：

minf=xdVC+TC*T+Penaltyp+yC                       （1）

s.t.

zyCW≤VW， ？坌j=1，2，3，…，J                                        （2）

xd≤M， ？坌j=1，2，3，…，J                                             （3）

zV≤VV， ？坌j=1，2，3，…，J                                            （4）

y=1， ？坌k=1，2，3，…，K                                                    （5）

x=x， ？坌j=1，2，3，…，J                                               （6）

Penaltyp=                                   （7）

x∈0，1    p，q=0，1，2，…，K; j=1，2，3，…，J                                   （8）

y∈0，1    k=0，1，2，…，K; j=1，2，3，…，J                                     （9）

z∈0，1    i=1，2，3，…，I; j=1，2，3，…，J; k=0，1，2，…，K                          （10）

公式（1）表示模型的目标函数为车辆配送走行成本、时间成本、早到/迟到惩罚成本和出车固定成本最小化;公式（2）表示每辆车装载货物总重量不超过车辆额定载重量;公式（3）表示每辆车每次配送总距离不超过车辆单次配送最大行驶里程;公式（4）表示每辆车装载货物总体积不超过车辆容量;公式（5）表示每个需求点的货物只能由一辆车完成配送;公式（6）表示车辆在完成配送任务后返回配送中心;公式（7）表示送货时间早于或晚于需求点收货时间窗的惩罚函数;公式（8）、公式（9）、公式（10）为0～1决策变量。

2  重大突发事件下应急物流车辆路径优化算法

2.1  改进的PSO数学模型

相较于传統粒子群算法收敛速度过快、粒子运动能力过差，解空间过小等特点，引入收敛速度改进策略、粒子搜索改进策略、精英保留改进策略，设计了一种适于求解全局优化问题的改进粒子群优化算法。通过将粒子及粒子群智能化处理，主动且快速地寻找解空间内最优解的地点，核心在于独特的粒子更新策略以及速度变化。改进的PSO数学模型如公式（11）至公式（18）所示。

粒子i的位置如公式（11）所示，作为优化问题潜在解：

X=x，x，…，x， i=1，2，3，…，m                                     （11）

粒子i的速度：

V=v，v，…，v， i=1，2，3，…，m                                     （12）

粒子i寻优位置：

P=p，p，…，p， i=1，2，3，…，m                                     （13）

种群寻优位置：

G=g，g，…，g， i=1，2，3，…，m                                      （14）

在d维空间中，粒子i的速度更新公式为：

v=ω*v+c*r*p-x+c*r*p-x                                （15）

在d维空间中，粒子i的位置更新公式为：

x=x+v                                               （16）

在d维空间中，插入改进的粒子优化公式：

x=c*x+c*v                                            （17）

在此过程中对于每个粒子i，有：

X∈X，X， V∈V，V                                     （18）

其中：ω为惯性权值，可以扩展粒子探索的空间，让粒子保持惯性从而进行新的探索;c和c都为认知常数，其中c表示粒子自我认知能力，c表示粒子群体的认知能力，当认知常数设定值较高时，粒子可能会越过目标区域，且一般不为0;c和

c都为粒子优化系数，当粒子优化系数设定值较高时，粒子运动能力增强，扩大了解空间，且粒子与粒子群信息交流更密切;

r和r是两个在0，1范围内变化的随机数。某一维粒子速度应满足V

2.2  改进的PSO实现步骤

改进的粒子群优化策略：（1）收敛速度改进策略。主要是调整算法的基本参数，即惯性权重ω和认知常数c和c，惯性权重对搜索范围和搜索精度会有一定程度的影响。（2）粒子搜索改进策略。引入了粒子优化公式，通过粒子同个体极值和群体极值的交叉、粒子自身变异、优化的方式来搜索最优解。（3）精英保留改进策略。概率接受粒子交叉中不满足约束的粒子作为恶劣解，协助粒子跳出局部最优。

算法基本实现步骤如下：

Step 1：种群初始化模块。初始化粒子群种群，设置改进粒子群算法的参数，假设粒子群个数为m，车辆数目是n，需求点数目为k，迭代次数为T，认知常数为c和c，粒子潜在解空间为X，X，粒子速度变化为V，V，初始化粒子的位置和速度V，粒子最优位置为P，种群最优位置为G。根据需求点生成相应的任务编号D，X为各任务对应的车辆编号，X=roundrandm，n*n-1+1，X为各车辆进行各项任务的排序，X=randm，n*k-1+1。V为车辆编号的生成速度，V

=roundrandm，n*n-3+1，V为任务排序的速度，V=randm，n*k-1+1，生成各粒子和粒子群初始解pbestX、pbestX、gbestX、gbestX，转Step 2。

Step 2：适应度值计算模块。计算粒子群个体的适应度值，即根据需求点到配送中心的坐标位置计算两点之间的距离、车辆速度、车辆载重等计算相应的适应度。转Step 3。

Step 3：根据目标函数计算适应度值，引入粒子优化策略，扩大粒子搜索范围，找出粒子群的gbest和各粒子的pbest，如果当前适应度优于之前的最优值，则更新粒子最优值和全局最优值，即pbestX=X;pbestX=X，转Step 4;反之，則不进行最优值更新，转Step 4。

Step 4：将评估值进行存储，用于下一状态的评价，根据粒子适应度值更新个体最优粒子和群体最优粒子，更新各任务对应的车辆速度及车辆接受各任务序号的速度和位置并进行速度和位置校正，若此时粒子速度V∈V，V、粒子位置X

∈X，X且优于之前，则更新，转Step 5;否则保持不变，转Step 3;

Step 5：获取任务对应车辆编号的粒子和车辆对应任务的顺序，存储每辆车运送的货物和时间惩罚成本，对每个粒子的X和X解码后进行约束条件判断，依据各车辆的额定载重量及容量限制，评估是否可作为可行解，通过群体最优交叉，更新粒子群速度和位置，并进行目标函数的计算，转Step 6。

[9] 胡忠君，刘艳秋，李佳. 基于实时交通信息的灾后应急物流多源配送优化问题[J]. 工业工程，2018，21（1）：83-88.

[10]  Walter J Gutjahr， Pamela C Nolz. Multicriteria optimization in humanitarian aid[J]. European Journal of Operational Research， 2016，252（2）：351-366.

[11]  Jacobson E U， Argon N T， Ziya S. Priority assignment in emergency response[J]. Operations Research， 2012，60（4）：813-832.

[12]  Kai Huang， Yiping Jiang， Yufei Yuan， et al. Modeling multiple humanitarian objectives in emergency response to large-scale disasters[J]. Transportation Research Part E， 2015，75（3）：1-17.

[13]  Talarico L， Meisel F， S Rensen K. Ambulance routing for disaster response with patient groups[J]. Computers & Operations Research， 2015，56（4）：120-133.

[14]  Wilson D T， Hawe G I， Coates G， et al. A multi-objective combinatorial model of casualty processing in major incident response[J]. European Journal of Operational Research， 2013，230（3）：643-655.

[15]  Wilson D T， Hawe G I， Coates G， et al. Online optimization of casualty processing in major incident response： An experimental analysis[J]. European Journal of Operational Research， 2016，252（1）：334-348.

[16]  Xian Qiang. Vehicle scheduling model for emergency logistics distribution with improved genetic algorithm[J]. International Journal of Advancements in Computing Technology， 2012，4（18）：315-323.

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

[18]  Ali Edrissi， Mehdi Nourinejad， Matthew J Roorda. Transportation network reliability in emergency response[J]. Transportation Research Part E， 2015，80（5）：56-73.

[19]  Meysam Fereiduni， Marzieh Hamzehee， Kamran Shahanaghi. A robust optimization model for logistics planning in the earthquake response phase[J]. Decision Science Letters， 2016，5（4）：519-534.

[20]  Babaei M， Mohaymany A S， Nikoo N. Emergency transportation network design problem： identification and evaluation of disaster response routes[J]. International Journal of Disaster Risk Reduction， 2018，27（7）：7-20.

[21] 杨菊花，朱昌锋，田志强. 引入时间紧迫系数的应急物资运输路径优化[J]. 铁道科学与工程学报，2013，10（2）：103-107.

[22] 郑斌，马祖军，周愉峰. 震后应急物流动态选址—联运问题的双层规划模型[J]. 系统管理学报，2017，26（2）：326-337.

[23] 楼振凯. 应急物流系统LRP的双层规划模型及算法[J]. 中国管理科学，2017，25（11）：151-157.