求解应急物资配送问题的层次樽海鞘群算法

段晓红

（北方工业大学经济管理学院，北京 100144）

在应急救援中，多车型应急车辆的使用能够有效地缩短物资配送时间，同时有助于控制救援成本，对多车型问题的讨论是十分必要的。田晓光[1]将多车型因素引入应急物资调度中，考虑运力、装载能力、限制期等约束，构建以灾害损失最小为目标的物资调度模型。但兵兵等人以总配送时间最短、安全性最高和成本最低为目标，构建应急物资调度模型。

对于灾害事件下的多车型应急物资调度，学者多假设需求点仅能被单车保障。然而，灾害事件后的应急物资需求大，单车保障显然不符合实际需求。基于此，本文针对多车型的应急物资配送问题构建模型，并设计一种层次樽海鞘群算法实现模型的求解。

一、问题描述与建模

本文研究的应急物资配送问题包括应急车辆分配和车辆路径规划两个方面。数学描述为：一种应急物资的体积为s，供给点r的可用物资量为w。K种车型构成集合G，第k种车型gk∈G的载重量为lk，容积为Vk。供给点可用的gk型车辆构成集合Ck，其中ck,o,o=1,2,…,Ok表示第o辆gk型车辆，Ok为gk型车辆的总数。I个受灾点构成集合A，第i个受灾点ai∈A的物资需求为qi，时间窗上限为Tiu。供给点到受灾点ai的行程时间为，受灾点aα∈A到aβ∈A，α≠β的行程时间为Tα,βa。单位应急物资的装载时间为tl，卸载时间为td。

（一）决策变量

模型存在两种决策变量：一是由ck,o运往ai的应急物资重量，二是ck,o对于其所服务受灾点的运送顺序

（二）目标函数

模型的救援满意度目标如式(1)，使不满足时间窗约束的应急物资总量最小。

其中，为模型的中间变量。当ck,o向其服务的受灾点umk,o配送物资所需的时间超过时，=1，否则=0。

由应急物资的装载时间、运输时间和卸载时间三部分组成，如式(2)所示。

（三）约束条件

规定ck,o对同一个受灾点最多服务一次，如式(3)所示。

如式(4)所示，配送至受灾点ai的物资总量应等于需求qi。

如式(5)所示，ck,o的载重量应不超过lk。

如式(6)所示，由ck,o运输的物资总体积应不超过Vk。

如式(7)所示，供给点派出的gk型应急车辆总数应不超过Ok。

其中，χk,o为调度模型的中间变量。当ck,o被派出时χk,o=1，否则χk,o=0。

二、基于层次樽海鞘群算法的模型求解

樽海鞘群算法由Mirjalili于2017年提出[3]，是一种模拟樽海鞘群体觅食行为的新型群体优化技术，数学模型见文献[4]。参数定义为：樽海鞘总数为N，搜索空间的上下界为ub和lb，最大迭代次数为Φ。

（一）求解应急车辆分配方案的樽海鞘群算法

采用真值编码，将决策变量编码为向量

适应度函数决定于约束条件(4)-(6)，适应度函数为

（二）求解应急车辆路径规划的樽海鞘群算法

ck,o的运输路径为其所服务的M个受灾点组成的序列，采用整数编码，将其编码为：

适应度函数决定于目标函数(1)和约束条件(3)，适应度函数为

（三）层次樽海鞘群算法基本流程

分别将2.1和2.2节所述算法定义为上、下层算法，则层次樽海鞘群算法求解步骤为：

步骤1.上层算法初始化应急车辆分配种群。分别以ub和lb为搜索空间的上下界，随机生成N个樽海鞘个体构成种群P，每一个个体En,n=1,2,…,N代表一种应急车辆分配方案。

步骤2.将En输入下层算法，并计算最优运输路径。对于每一个En执行以下步骤：

步骤2.1.分别以ub’和lb’为搜索空间的上下界，随机生成N1个樽海鞘个体构成种群P1，每一个个体Un,z,z=1,2,…,N1代表一种应急物资运输路径。

步骤2.2.根据式（10）和（11）所示的编码方案和适应度函数，采用樽海鞘群算法获得最优运输路径Un。

步骤3.将Un及其适应度值传递给上层算法，计算各方案{En,Un}的适应度值B=B1+B2，根据适应度B从优到劣的顺序对种群排序。

步骤4.上层算法种群位置更新。根据樽海鞘群算法步骤更新上层算法中个体位置En。

步骤5.重复步骤2-4直至完成最大迭代次数Φ，输出最优配送方案{Enb,Unb}。

三、算例分析

应急物资的体积为6m3/T。应急车辆车型参数如表1；供给点的g1、g2和g3型车辆数分别为3、4和2；受灾点a1、a2和a3的应急物资需求分别为6T、3T和7T，救援时间窗分别为3600s、5400s和5400s。应急物资的装载和卸载时间均为300s/T。供给点到各受灾点的最短行程时间如表2。

表1 应急车辆车型参数

表2 行程时间

运行层次樽海鞘群算法获得最优配送方案如表3-4。

表3 应急车辆最优分配方案

表4 最优运输路径

分析表3和4可知，应急车辆分配方案满足受灾点需求和应急车辆载重约束，最优路径符合同一受灾点最多服务一次的要求。

四、结束语

本文构建了多车型多受灾点应急物资配送模型，设计一种层次樽海鞘群算法，通过上下层变量传递实现模型求解。算例验证结果表明层次樽海鞘群算法能够获得满足车辆载重、物资需求等约束且救援满意度最大的物资配送方案。