考虑洪水淹没的应急物资调运方案优化

Optimization of Emergency Material Dispatch Scheme Considering Flood Submergence

摘要: 本文研究了洪灾背景下考虑洪水淹没的应急物资调运优化问题，目标是在车辆和道路受限的情况下，将低海拔地区的应急物资快速转移到高海拔仓库。论文提出了两种求解方法：遗传算法和一种分阶段的混合算法(近似解法)，并通过一个25个物资储备库的算例进行了对比分析，得出混合算法在求解效率和结果优越性方面更具优势的结论。

Abstract: This paper investigates the optimization problem of emergency material transportation considering flood inundation in the context of flood disasters. The objective is to quickly transfer emergency supplies from low-altitude areas to high-altitude warehouses under the constraints of limited vehicles and road access. The paper proposes two solution methods: a genetic algorithm and a phased hybrid algorithm (an approximate solution method). Through a comparative analysis using a case study of 25 material reserve depots, it concludes that the hybrid algorithm has advantages in both solution efficiency and result superiority.

1. 引言

近年来，由于全球气候变暖导致极端天气事件频发，如暴雨、台风等，随着水位的不断上涨会引起洪涝灾害发生，一旦发生洪灾，低海拔地区的应急物资储备库就容易被淹没，从而不但阻碍了接下来的救援工作，而且影响之后对受灾群众的物资供给。中国是洪涝灾害特别严重的国家，这些事件往往导致严重的人员受难和物资损失，和对应急物资需求的急速增加。在洪灾来临前，将现有应急物资转运至相对安全地区以防止物资受损，进而更好地开展接下来的救援工作。其中，由于低海拔地区容易积水导致物资储备库被淹，所以可以将物资转运至高海拔安全地区以减少应急物资受损。因此，探究洪灾下考虑洪水淹没的应急物资转运是一个重要的课题。

应急物资调运问题是一个典型的组合优化问题，涉及车辆路径规划、任务分配和资源调度等多个方面的问题，由于其NP难特性，近年来，启发式算法[1]-[6]逐渐成为解决应急物资调运问题的主流方法，这些算法通过模拟自然进化或群体行为，能够在较短时间内找到近似最优解，但其随机性较强，容易陷入局部最优解。

逐渐地，混合算法的出现逐渐弥补了启发式算法的不足，徐超毅和刘晓絮[7]为减少洪涝灾害时的经济损失，构建考虑灾区对应急物资的需求程度约束和软时间窗约束的路径优化模型，考虑车辆行驶速度受天气差异影响的变化，设计混合遗传算法求解；黄晨煜[8]结合当前交通路网的路段受损率来计算配送区域内路径的广义运输距离，建立应急物流车辆配送路径优化模型，针对模型特点提出了考虑“先分区，后规划”思想的二阶段混合算法来完成求解算法设计；钟媛媛[9]构建了综合多环境因素影响的带软时间窗的应急物资配送车辆路径问题模型，并设计了一种混合蚁群禁忌搜索算法进行求解；金瑜杰[10]将应急物资调运问题分成物资分配和车辆路径规划两部分，并分别用遗传算法和蚁群算法求解；Zhang等[11]提出了一种结合人工免疫算法和蚁群算法的混合算法来求解应急车辆路径问题，在较短时间内得到了更优的解；Wu等[12]提出了一种基于蚁群算法和变邻域搜索算法相结合的混合算法，并将其与常用优化算法进行比较，验证了该混合算法可以在较短时间内求得问题的解。

本文针对现有研究提出一种混合算法，并将应急物资调运问题分成运输问题、任务分配问题和车辆路径规划问题三部分，建立不同的模型并用不同的方法求解。

2. 考虑洪水淹没的应急物资调运问题

2.1. 问题描述

在车辆有限，道路通行受限和洪水即将来临的背景下，以最短的时间内将低海拔点的应急物资全部运输至高海拔点仓库为总目标，规划应急物资调运方案，以防止应急物资被即将来临的洪水淹没和受损。该问题的描述及相关假设如下：

1) 物资情况：有$m$ 个低海拔物资储备点$A_1,A_2,\cdots ,A_m$ ，各低海拔点的现有物资量分别为$a_1,a_2,\cdots ,a_m$ 。有$n$ 个高海拔物资储备点$B_1,B_2,\cdots ,B_n$ ，各高海拔点的物资容量分别为$b_1,b_2,\cdots ,b_n$ 。${a^{\prime }}_i$ 为低海拔点的剩余物资量，${b^{\prime }}_i$ 为高海拔点的储存物资的剩余空间。高海拔点的物资总容量大于低海拔点的物资总量，即$\sum a_i\le \sum b_i$ 。

2) 路网：任意两点$P_i\left(x_i,y_i\right)$ 与$P_j\left(x_j,y_j\right)$ ($P_i$ 和$P_j$ 可是任意低海拔点或是高海拔点)间的运输距离为$d_{ij}$ ，距离使用欧几里得公式求解：

$\begin{array}{c}{d}_{ij}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}\end{array}$ (1)

3) 运输车辆：有$K$ 辆卡车($K\le m$ )，每辆车的最大容量为$Q$ ，卡车平均速度为$V$ 。

4) 运输规则：卡车$k$ 可去任意地点装卸货，每次装卸货的时间为固定值$T$ ；卡车$k$ 形成一个由装卸货任务构成的运输方案$s_k$ ：

$\begin{array}{c}{s}_k=\left\{s_{k,1},\cdots ,s_{k,i},\cdots ,s_{k,n}\right\}=\left\{\left(P_1,L_{k,1}\right),\cdots ,\left(P_i,L_i\right),\cdots ,\left(P_n,L_n\right)\right\}\end{array}$ (2)

上式中$s_{k,i}$ 表示第$i$ 次装卸货任务，$\left(P_i,L_i\right)$ 即为本次装卸货任务的物资点以及具体的装卸量。当$L_i>0$ 时表示在点$P_i$ 装货，当$L_i<0$ 时表示在点$P_i$ 卸货。当完成一次装卸货任务时，需该物资储备点的货物量更新。当该点是低海拔点时，更新物资量$a_i$ ：

$\begin{array}{c}{a}_i=a_i-L_i\end{array}$ (3)

当该海拔点是高海拔点时，更新物资容量$b_i$ ：

$\begin{array}{c}{b}_i=b_i+L_i\end{array}$ (4)

卡车$k$ 在运输全程中任意时刻的容量需小于等于最大容量$q$ 。即对于任一次装卸货任务$s_{k,j}$ ，执行完该任务后卡车总容量应不超过$q$ ：

$\begin{array}{c}\forall s_{k,j},{\displaystyle \sum }_{i=1}^j{L}_i\le q\end{array}$ (5)

当$s_k$ 执行完成时，卡车应当清空：

$\begin{array}{c}{\displaystyle \sum }_{i=1}^n{L}_i=0\end{array}$ (6)

根据运输方案$s_k$ ，可求得卡车$k$ 的运输总时长$t_k$ 为：

$\begin{array}{c}{t}_k={\displaystyle \sum }_{i=1}^{n+1}\frac{d_{i,i+1}}{V}+nT\end{array}$ (7)

5) 初始情况与结束条件：初始情况为卡车$k$ 在空车时，同时在某低海拔点开始执行$s_k$ 。完成条件为所有低海拔点的物资全部运输完成且所有卡车完成运输任务：

$\begin{array}{c}\sum a_i=0\text{ and }{\displaystyle \sum }_{i=1}^n{L}_i=0\end{array}$ 8)

6) 目标函数：所有卡车的总运输时间最小：

$\begin{array}{c}\min z=\max \left(\left\{t_k:k=1,2,\cdots ,k\right\}\right)\end{array}$ (9)

2.2. 问题分析

该问题是一个典型的组合优化问题。当我们关注其中一辆车的运输方案$s_k$ 时，可近似看作是由一系列车辆路径问题(Vehicle Routing Problem, VRP)组成的集合。

VRP的基本假设如下：

1) 假设有一个中心仓库(起点)，以及若干个客户点，每个客户点有固定的需求量。

2) 设计一组车辆的行驶路径，使得每辆车从仓库出发，经过若干个客户点，再返回仓库。

3) 每辆车的行驶路线需要满足容量限制(即每辆车的最大载货量不能超过其容量)，并且路径应当尽量优化(通常是最小化总距离、总时间或总成本)。

VRP的约束条件如下：

1) 容量约束：每辆车的运输能力有限，每次只能运输一定数量的货物。

2) 路径约束：每个客户点必须由一辆车访问，且每个客户点仅能被访问一次。

$s_k$ 中的运输方案与VRP的主要区别在于每次完成卸货之后，车辆无需返回中心仓库，而是去往下一个仓库，且并无“每个客户点必须由一辆车访问，且每个客户点仅能被访问一次”的约束，因此每辆车的运输方案比VRP问题中的单车运输方案具有更大的组合空间，可将此问题归约为一个VRP问题。由于VRP问题是一个NP难问题，因此考虑洪水淹没的应急物资调运问题本质上也是一个NP难问题，不可在多项式时间内求解该问题，通常可使用启发式算法，如贪心算法、遗传算法、蚁群算法等进行求解。

3. 遗传算法求解

1) 概述

本研究采用遗传算法(Genetic Algorithm, GA)来求解物资运输调度问题，旨在找到一种最优的车辆运输方案，使得所有低海拔物资储备点的物资在最短时间内被清空并运输至高海拔物资储备点。遗传算法通过模拟自然选择和遗传机制，在解空间中搜索最优解。

2) 编码方式

每个个体(运输方案)由K辆车的运输路线组成，其中每辆车的运输路线被编码为一个长度为L的整数序列，序列中的每个整数表示物资储备点的编号，范围从0到$m+n-1$ ，其中0到$m-1$ 代表低海拔点，m到$m+n-1$ 代表高海拔点。例如，对于第k辆车，其运输路线为$\left\{p_1,p_2,\cdots ,p_L\right\}$ ，其中$p_i$ 车辆k在第i步访问的物资储备点编号。

3) 初始种群的生成

通过随机生成r个个体来构建。对于每个个体，每辆车的运输路线通过随机选择L个物资储备点编号来生成，如公式(10)所示：

$\begin{array}{c}\text{population}={\left\{{\left({\left[\text{randint}\left(0,m+n-1\right)\right]}_{i=1}^L\right)}_{k=1}^K\right\}}_{j=1}^r\end{array}$ (10)

其中，population是初始种群，j表示种群中的个体编号，k表示车辆编号，i表示车辆运输路线中的步骤编号。

4) 适应度函数设计

适应度函数用于评估每个个体(运输方案)的优劣。根据适应度对个体进行排序，记录当前代的最优适应度和最优个体。

在本问题中，适应度定义为所有低海拔物资储备点清空时的时间，若在模拟过程中低海拔物资储备点未清空，则适应度为无穷大(∞)。

具体计算过程如下：

对于每个个体(即K辆车的运输方案)，初始化低海拔点的现有物资量a、高海拔点的物资容量b、每辆车的当前任务索引ti、当前负载tl和下一更新时间点$t^{\prime }$ ，以及全局时间t。

在模拟过程中，每辆车按照其运输路线依次访问物资储备点。当车辆到达低海拔物资储备点时，它会装载尽可能多的物资，直到车辆满载或该低海拔点物资清空。装载量load由公式(11)确定：

$\begin{array}{c}\text{load}=\min \left(Q-tl\left[k\right],a\left[\text{loc}\right]\right)\end{array}$ (11)

其中，$a\left[\text{loc}\right]$ 是当前低海拔点的现有物资量，loc是是当前访问低海拔点编号。

若load > 0，则更新低海拔点现有物资量$a\left[\text{loc}\right]$ 和车辆载货量$tl\left[k\right]$ ，并增加装货时间T，如公式(12)、(13)、(14)所示：

$\begin{array}{c}a\left[\text{loc}\right]=a\left[\text{loc}\right]-\text{load}\end{array}$ (12)

$\begin{array}{c}tl\left[k\right]= tl\left[k\right]+ \text{load}\end{array}$ (13)

$\begin{array}{c}T=T+t^{\prime }\end{array}$ (14)

当车辆到达高海拔物资储备点时，它会卸载尽可能多的物资，直到车辆空载或该高海拔点物资容量已满。卸载量unload由公式(15)确定：

$\begin{array}{c}\text{unload}=\min \left(tl\left[k\right],b\left[\text{loc}-m\right]\right)\end{array}$ (15)

若unload > 0，则更新高海拔点物资容量$b\left[\text{loc}-m\right]$ 和车辆载货量$tl\left[k\right]$ ，并增加卸货时间T，如公式(16)、(17)所示：

$\begin{array}{c}b\left[\text{loc}-m\right]=b\left[\text{loc}-m\right]-\text{unload}\end{array}$ (16)

$\begin{array}{c}tl\left[k\right]= tl\left[k\right]-\text{unload}\end{array}$ (17)

每次车辆移动到下一个物资储备点时，计算移动时间$t^{″}$ ，移动时间$t^{″}$ 由公式(18)确定：

$\begin{array}{c}{t}^{″}=\frac{d\left[\text{loc}\right]\left[{\text{next}}_{\text{loc}}\right]}{V}\end{array}$ (18)

其中，$d\left[\text{loc}\right]\left[\text{next}\_\text{loc}\right]$ 是当前位置$\text{loc}$ 到下一个位置$\text{next\_loc}$ 的距离。

更新下一更新时间点$t^{\prime }\left[k\right]$ 和当前任务索引$ti\left[k\right]$ ，如公式(19)、(20)所示：

$\begin{array}{c}{t}^{\prime }\left[k\right]= t^{\prime }\left[k\right]+t^{″}\end{array}$ (19)

$\begin{array}{c}ti\left[k\right]= ti\left[k\right]+1\end{array}$ (20)

重复上述过程，直到所有低海拔物资储备点清空或确认无法清空。若所有低海拔物资储备点清空，则适应度为当前全局时间t；若未清空，则适应度为∞。适应度函数fitness可表示为公式(21)：

$\begin{array}{c}\text{fitness}=\{\begin{array}{c}t,{\displaystyle {\sum }_{i=0}^{m-1}{a}_i}=0\\ \infty ,{\displaystyle {\sum }_{i=0}^{m-1}{a}_i}\ne 0\end{array}\end{array}$ (21)

5) 选择算子

采用基于适应度排序的选择策略，选择适应度较好的个体进入下一代种群，以保留优良基因。

6) 交叉算子

使用单点交叉操作，在每对父代个体(每辆车的运输路线)中随机选择一个交叉点，交换交叉点之后的部分，生成两个子代个体。

7) 变异算子

对每个个体(每辆车的运输路线)以一定的变异概率进行变异操作。变异时随机选择运输路线中的一个位置，将其对应的物资储备点编号替换为一个随机生成的编号。

当算法的迭代次数大于预先设置的迭代数值时，便输出最优解，结束运算。具体结构流程如图1所示。

Figure 1. Flowchart of genetic algorithm

图1. 遗传算法流程图

4. 模型构建及求解方法

本文从车辆使用的角度出发，提出一种考虑洪水淹没的应急物资调运问题的近似解法。该解法的总体思路可描述为：让所有车辆尽可能高效运行，不同车辆的运输工作量尽可能相同，且优先保证大部分物资(如80%以上)的运输任务。为实现上述思路，将该问题拆分为依次求解的3个子问题：

1) 运输问题：为保证车辆高效运行，应使货物的总体运输的时间成本最小。可先不考虑车辆运输过程中的约束，将该问题看作由$m$ 个产地(低海拔点)和$n$ 个销地(高海拔点)的运输问题，使得整体运输方案的距离成本最小，完成低海拔点和高海拔点的匹配。

2) 任务分配问题：为保证不同车辆的运输工作量尽可能相同，将低海拔点聚成$K$ 簇，使得簇内点间的距离尽可能小、簇间的距离尽可能大，且不同簇对应的总运输量尽可能相同。每辆车负责一个簇的运输任务，完成车辆任务的分配。

3) 车辆路线规划问题：为优先保证大部分物资的运输任务，车辆将按照低海拔点物资量的顺序，从大到小、由近及远的依次完成簇内运输任务。

接下来将分别介绍各子问题的数学模型及其求解方法。

4.1. 运输问题模型

1) 决策变量

$x_{ij}$ 为从低海拔点i到高海拔点j的运输量；$y_{ij}$ 为低海拔点i是否运输至高海拔点j，是为1，否则为0。

2) 模型建立

$\begin{array}{c}\min z={\displaystyle \sum }_{i=1}^m{\displaystyle \sum }_{j=1}^n{d}_{ij}{x}_{ij}\end{array}$ (22)

$\begin{array}{c}{\displaystyle \sum }_{j=1}^n{x}_{ij}=a_i,i\in m\end{array}$ (23)

$\begin{array}{c}{\displaystyle \sum }_{i=1}^m{x}_{ij}\le b_j,j\in n\end{array}$ (24)

$\begin{array}{c}{\displaystyle \sum }_{j=1}^n{y}_{ij}\le \lceil \frac{Q}{a_i}\rceil ,i\in m\end{array}$ (25)

$\begin{array}{c}{x}_{ij}\le M{y}_{ij},i\in m,j\in n\end{array}$ (26)

$\begin{array}{c}{x}_{ij}\ge 0,y_{ij}\in \left(0,1\right),i\in m,j\in n\end{array}$ (27)

目标函数(22)为运输总路径最短；约束条件(23)为运输量等于低海拔点的现有物资总量；约束条件(24)为运输量不大于高海拔点的最大物资总容量；约束条件(25)为低海拔点$A_i$ 向高海拔点$B_j$ 运输的节点数不

能超过$\frac{Q}{a_i}$ 的上取整函数，以减少车辆的运行路线；约束条件(26)为运输量与决策变量的关系，M是一个

足够大的常数，用于确保当$y_{ij}=0$ 时，$x_{ij}=0$ ；约束条件(27)为非负约束。

3) 模型求解

运用表上作业法求解该应急物资分配模型，算法如下：

Step 1：列出平衡表。基于$d_{ij}$ 得到一个$m\times n$ 的距离表，并将距离表填入最终的平衡表。将配送区域内路网的各路段以“未受损可通行”和“完全受损不可通行”两种情况，若某节点路段为完全受损中断通车状态，在程序运行时将其距离设定为一个无限大的正数M，如表1所示。

Table 1. Balance sheet

表1. 平衡表

	$B_1$	$B_2$	$\cdots$	$B_n$	$a_i$
$A_1$	$d_{11}$	$d_{12}$	$\cdots$	$d_{1n}$	$a_1$
$A_2$	$d_{21}$	$d_{22}$	$\cdots$	$d_{2n}$	$a_2$
$\cdots$	$\cdots$	$\cdots$	M	$\cdots$	$\cdots$
$A_m$	$d_{m1}$	$d_{m2}$	$\cdots$	$d_{mn}$	$a_m$
$b_j$	$b_1$	$b_2$	$\cdots$	$b_n$

Step 2：运用伏格尔法确定运输方案，得到应急物资分配结果表，如表2所示。由于该模型是基于应急物资分配问题改进的运输模型，且接下来还要进行优化，因此得到基本初始可行解即可。另外，如果$x_{ij}=0$ ，可以不在表格上体现。

Table 2. Allocation table of emergency material

表2. 应急物资分配表

	$B_1$	$B_2$	$\cdots$	$B_n$	${a^{\prime }}_i$
$A_1$	$x_{11}$	$x_{12}$	$\cdots$	$x_{1n}$	${a^{\prime }}_1$
$A_2$	$x_{21}$	$x_{22}$	$\cdots$	$x_{2n}$	${a^{\prime }}_2$

续表

$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$
$A_m$	$x_{m1}$	$x_{m2}$	$\cdots$	$x_{mn}$	${a^{\prime }}_m$
$b_j$	${b^{\prime }}_1$	${b^{\prime }}_2$	$\cdots$	${b^{\prime }}_n$

4.2. 任务分配问题模型

本阶段需要将总区域的m个低海拔点分为K类：对m个低海拔点使用改进的K-means算法将所有的低海拔点划分至K个子区域，并将与低海拔点有运输量的高海拔点划分至该低海拔点所属的子区域中。

1) 问题定义

给定的数据集$A=\left\{A_i|i=1,2,\cdots ,m\right\}$ ，给定的数据的容量为$a_i$ ，目标数据块数目为K；平衡容量约束聚类将根据预先定义的距离将目标样本集A平衡地划分为K簇，每个簇都具有一个聚类中心点，共有K个聚类中心点，记为$B=\left\{{\mu }_k|k=1,2,\cdots ,K\right\}$ ；聚类结果中所有的簇信息存储在$C_k$ 中，${C^{\prime }}_K$ 表示簇的容量；$e_{ik}$ 为指示变量，若节点i被分配到$C_k$ ，则为1，否则为0；$l_{ik}$ 表示节点i到簇中心点${\mu }_k$ 的距离；$s_{min}$ 表示每个簇至少包含的数据点个数；β表示容量平衡惩罚系数，用于平衡距离成本和容量偏差。

2) 模型建立

本问题在传统K-means算法的基础上，提出了一种基于容量平衡的K-means聚类算法，其目标函数由两部分组成：节点到簇中心点的距离成本以及簇容量与目标容量之间的偏差惩罚。每个簇的总容量尽可能接近平均容量。对于每个簇的$C_K$ ，计算其总容量与平均容量的差值的绝对值，进而对所有簇的这些绝对值求和。

$\begin{array}{c}F=\min {\displaystyle \sum }_{k=1}^K\left({\displaystyle \sum }_{i\in C_K}{l}_{ik}+\beta \cdot \left|{C^{\prime }}_K-\frac{{{\displaystyle \sum }}_{i=1}^m{a}_i}{K}\right|\right)\end{array}$ (28)

$\begin{array}{c}\left|C_k\right|\ge s_{\min },k=1,2,\cdots ,K\end{array}$ (29)

$\begin{array}{c}{\displaystyle \sum }_{k=1}^K{e}_{ik}=1\end{array}$ (30)

目标函数(28)为使每个聚类的大小尽可能接近平均值，避免某些聚类过大或过小；约束条件(29)为每个簇至少包含的数据点个数；约束条件(30)为每个节点只能分配到一个簇。

3) 优化步骤

Step 1：初始化中心点。采用K-means++方法初始化簇的中心点，并确保初始中心尽可能分散，随机初始化K个聚类中心${\mu }_k$ 。

Step 2：节点分配。对于每个节点，计算其到所有簇中心点的距离，并结合容量惩罚项，选择使总成本最小的簇进行分配。分配点到最近的聚类中心。根据点与聚类中心的加权距离分配仓库到各聚类。

$\begin{array}{c}{d}_i=\sqrt{{\left(x_i-{\mu }_{kx}\right)}^2-{\left(y_i-{\mu }_{ky}\right)}^2}\end{array}$ (31)

Step 3：中心点更新。对于每个簇，重新计算其中心点，使其为簇内节点的加权距离最小点。聚类中心取属于该簇的点的加权平均。

$\begin{array}{c}{\mu }_k=\frac{{{\displaystyle \sum }}_{i\in C_k}{w}_i\left(x_i,y_i\right)}{{{\displaystyle \sum }}_{i\in C_k}{w}_i}\end{array}$ (32)

Step 4：调整簇的容量。若当前容量小于最佳容量，更新最佳簇和最佳容量，确保每个簇容量接近目标容量。

Step 5：迭代优化。重复上述Step 2和Step 3，直至达到最大迭代次数或目标函数收敛，输出最优解，结束运算。具体结构流程如图2所示。

Figure 2. Clustering algorithm flowchart

图2. 聚类算法流程图

4.3. 车辆路径规划问题模型

根据3.1和3.2，得到卡车$k$ 的运输任务集合$T_k$ 如下：

$T_k=\left\{\left(A_i,B_j,x_{ij}\right)|A_i\in C_k\right\}$ (33)

为优先保证大部分货物的运输任务，卡车$k$ 按照如下贪心算法运行：

Step 1：抵达运输量$x_{ij}$ 最大的低海拔点$A_i$ ，转入Step 3。

Step 2：找到所有运输量$x_{ij}\ge Q$ 的运输任务，若为空集，转入Step 1；若不为空集，则抵达离当前节点最近的低海拔节点$A_i$ ，转入Step 3。

Step 3：若$x_{ij}\ge Q$ ，转入Step 4；若$x_{ij}<Q$ ，转入Step 5。

Step 4：执行任务$\left\{\left(A_i,+Q\right),\left(B_j,-Q\right)\right\}$ ，$x_{ij}=x_{ij}-Q$ ，若$x_{ij}<Q$ ，即无法装满一辆车，转入Step 5；若$x_{ij}\ge Q$ ，转入Step 4。

Step 5：若$x_{ij}\ge \lambda Q$ ，则转入6；若$x_{ij}<\lambda Q$ ，将$\left(A_{i,}{B}_j,x_{ij}\right)$ 从任务中删除，若删除后任务列表为空，则结束，否则转入Step 2。

Step 6：执行任务$\left\{\left(A_i,+x_{ij}\right),\left(B_j,-x_{ij}\right)\right\}$ ，将$\left(A_{i,}{B}_j,x_{ij}\right)$ 从任务中删除，若删除后任务列表为空，则结束，否则转入Step 2。

以上算法中，$\lambda$ 为物资储备点剩余物资系数，当剩余物资量超过$\lambda Q$ 时，车辆选择将该低海拔点的物资清空，否则将不处理该点的剩余物资，转而重新进入Step 1完成运输量最大的任务。经过Step 1之后，每个低海拔点的物资剩余量将不超过$\lambda Q$ 。

5. 算例分析

5.1. 数据准备

本文选取某市25个物资储备库进行算例分析，通过查找相关统计资料、新闻资讯以及专家评估等方式获取各个物资储备库的数据，如表3和表4所示。对于个别无法获取的数据，结合已有数据和实际情况进行虚拟设置，不影响模型的有效性和实际意义，本文设定车辆最大容量Q为30吨，车辆运行速度V为50 km/h，物资点剩余储备物资系数λ为0.1，装卸货时间T为0.3 h。

Table 3. Specific data for low altitude points

表3. 低海拔点具体数据

$A_i$	坐标	$a_i$
$A_1$	(−29.730, 64.136)	54
$A_2$	(−30.664, 5.463)	38
$A_3$	(51.642, 5.469)	40
$A_4$	(−13.171, 69.336)	55
$A_5$	(−67.413, 68.323)	54
$A_6$	(48.907, 6.274)	41
$A_7$	(5.243, 22.260)	34
$A_8$	(−65.002, 77.234)	52
$A_9$	(−4.175, −1.569)	39
$A_{10}$	(23.029, 11.639)	49
$A_{11}$	(25.482, 6.287)	55
$A_{12}$	(−42.615, −26.392)	65
$A_{13}$	(−76.672, 99.341)	56
$A_{14}$	(−20.673, 57.892)	47
$A_{15}$	(−52.039, 6.567)	52
$A_{16}$	(−41.376, 50.824)	38

Table 4. Specific data for high altitude points

表4. 高海拔点具体数据

$B_j$	坐标	$b_i$
$B_1$	(−37.756, −33.325)	99
$B_2$	(23.767, 29.083)	138
$B_3$	(−43.030, 20.453)	89
$B_4$	(−35.297, −24.896)	93
$B_5$	(−54.755, 14.368)	88
$B_6$	(−49.329, 33.374)	79
$B_7$	(57.404, 23.822)	92
$B_8$	(−22.754, 55.408)	83
$B_9$	(−56.622, 73.340)	108

基于表3和表4节点的坐标信息，可绘制运输区域内的坐标分布图，如图3所示。

Figure 3. Location distribution map of all coordinate points within the transportation area

图3. 运输区域内所有坐标点的位置分布图

5.2. 分阶段求解

1) 运输问题

本文主要通过随机生成的方式来对路段受损情况做假设，确定某节点路段为完全受损中断通车状态，并在程序运行时将其距离设定为一个无限大的正数M，由此即完成了对路段通行信息数据的调整得到平衡表，如表5所示。

Table 5. Balance sheet

表5. 平衡表

	$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$B_6$	$B_7$	$B_8$	$B_9$	$a_i$
$A_1$	97	63	45	89	55	36	96	M	28	54
$A_2$	M	59	19	30	25	33	89	50	72	38
$A_3$	97	36	M	92	106	M	19	89	127	40
$A_4$	105	54	57	96	68	50	83	16	43	55
$A_5$	M	99	53	98	55	39	132	46	11	54
$A_6$	95	33	93	M	M	101	19	86	125	41
$A_7$	70	19	48	62	60	55	52	43	80	34
$A_8$	113	100	60	106	63	46	M	47	9	52
$A_9$	M	41	44	38	53	57	66	59	91	39
$A_{10}$	75	17	66	68	77	75	M	63	M	49
$A_{11}$	74	22	69	68	80	79	36	68	106	55
$A_{12}$	8	86	M	7	42	60	111	84	100	65

续表

$A_{13}$	138	122	85	M	87	71	153	69	32	56
$A_{14}$	92	52	43	84	55	37	M	3	39	47
$A_{15}$	42	M	16	35	8	26	110	56	66	52
$A_{16}$	84	68	30	75	38	19	102	19	27	38
$b_j$	99	138	89	93	88	79	92	83	108

基于得到的平衡表和运输模型得到的结果为20,911，具体的应急物资分配方案如表6所示。

Table 6. Plan table of emergency material distribution

表6. 应急物资分配方案表

	$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$B_6$	$B_7$	$B_8$	$B_9$	$a_i^{\text{'}}$
$A_1$			24		30					0
$A_2$			16	22						0
$A_3$							40			0
$A_4$			25					30		0
$A_5$			24			30				0
$A_6$							41			0
$A_7$		34								0
$A_8$									52	0
$A_9$				39						0
$A_{10}$		49								0
$A_{11}$		55								0
$A_{12}$	65									0
$A_{13}$									56	0
$A_{14}$								47		0
$A_{15}$					52					0
$A_{16}$						38				0
$b_i^{\text{'}}$	34	0	0	32	6	11	11	6	0

2) 任务分配问题

基于2.2介绍的改进K-means聚类算法，利用Python软件实现对低海拔点的聚类分析，设迭代1000次，容量惩罚函数设为30，容量期望值为202.75，每个簇至少包含的数据点个数$s_{\min }$ 为4。得到的结果如表7所示。展示聚类划分结果如图4所示。

3) 车辆规划问题

通过表7可知，每一簇有一条应急物资运输路线，根据车辆路径规划问题模型，得到每辆车的最优行驶时间，通过三阶段的分段求解得到的总行驶时间的最优值为40.09，每辆车的具体运输方案如表8所示。

Figure 4. Cluster division result chart

图4. 聚类划分结果图

Table 7. Result table of cluster division

表7. 聚类划分结果表

$C_k$	$A_i$	$B_j$	总容量	与期望值的差
$C_1$	$A_3$ 、$A_6$ 、$A_{10}$ 、$A_{11}$	$B_2、B_7$	208	5.25
$C_2$	$A_2$ 、$A_9$ 、$A_{12}$ 、$A_{15}$	$B_1$ 、$B_3$ 、$B_4$ 、$B_5$	206	3.25
$C_3$	$A_8$ 、$A_{13}$ 、$A_{14}$ 、$A_{16}$	$B_5$ 、$B_6$ 、$B_8$ 、$B_9$	189	13.75
$C_4$	$A_1$ 、$A_4$ 、$A_5$ 、$A_7$	$B_2$ 、$B_3$ 、$B_5$ 、$B_6$ 、$B_8$	208	5.25

Table 8. Plan table of transportation

表8. 运输方案表

$C_k$	$s_k$	$t_k$
$C_1$	('A10', 30), ('B2', −30), ('A10', 19), ('B2', −19), ('A11', 30), ('B2', −30), ('A11', 25), ('B2', −25), ('A6', 30), ('B7', −30), ('A6', 11), ('B7', −11), ('A3', 30), ('B7', −30), ('A3', 10), ('B7', −10)	8.72
$C_2$	('A9', 30), ('B4', −30), ('A9', 9), ('B4', −9), ('A12', 30), ('B1', −30), ('A12', 30), ('B1', −30), ('A12', 5), ('B1', −5), ('A15', 30), ('B5', −30), ('A15', 22), ('B5', −22), ('A2', 16), ('B3', −16), ('A2', 22), ('B4', −22)	9.49
$C_3$	('A14', 30), ('B8', −30), ('A14', 17), ('B8', −17), ('A16', 30), ('B6', −30), ('A16', 8), ('B6', −8), ('A8', 30), ('B9', −30), ('A8', 22), ('B9', −22), ('A13', 30), ('B9', −30), ('A13', 26), ('B9', −26)	7.56
$C_4$	('A7', 30), ('B2', −30), ('A7', 4), ('B2', −4), ('A4', 25), ('B3', −25), ('A4', 30), ('B8', −30), ('A1', 24), ('B3', −24), ('A1', 30), ('B5', −30), ('A5', 24), ('B3', −24), ('A5', 30), ('B6', −30)	14.32

5.3. 遗传算法求解

交叉概率为0.9，变异概率为0.1，初始种群大小为200，个体任务序列长度为200，迭代次数设为50。使用Python进行运算，得到目标函数最优值为64.4，具体的遗传算法运输方案如表9所示。

Table 9. Plan table of genetic algorithm transportation

表9. 遗传算法运输方案表

$C_k$	$s_k$
$C_1$	('B2', 0), ('A5', 30), ('B2', −30), ('B0', 0), ('A12', 30), ('A15', 0), ('A11', 0), ('A1', 0), ('A7', 0), ('A12', 0), ('B1', −30), ('A13', 0), ('B3', 0), ('A11', 30), ('B5', −30), ('A11', 30), ('A0', 0), ('A1', 0), ('A0', 0), ('A2', 0), ('B3', −30), ('B7', 0), ('A0', 24), ('B8', −24), ('A4', 24), ('B8', −24), ('B2', 0), ('A15', 0), ('A9', 0), ('A8', 26), ('B4', −26), ('A12', 8), ('B7', −8), ('A1', 8), ('A6', 4), ('B5', −12), ('A10', 0)
$C_2$	('B5', 0), ('A13', 17), ('A8', 13), ('A6', 0), ('B1', −30), ('B5', 0), ('A9', 19), ('A13', 0), ('B0', −19), ('B0', 0), ('B7', 0), ('A3', 30), ('A4', 0), ('A2', 0), ('A6', 0), ('A8', 0), ('B4', −30), ('A11', 5), ('A2', 25), ('A2', 0), ('B2', −30), ('A6', 30), ('A6', 0), ('B0', −30), ('A14', 0), ('A11', 0), ('A2', 15), ('B7', −15), ('A10', 25), ('A12', 5), ('A13', 0), ('B4', −30), ('A15', 0), ('A5', 0), ('A11', 0), ('A9', 0), ('A6', 0), ('A0', 0), ('A13', 0)
$C_3$	('A13', 30), ('A13', 0), ('A2', 0), ('A5', 0), ('A8', 0), ('A11', 0), ('A9', 0), ('B1', −30), ('A1', 30), ('A7', 0), ('B5', −30), ('A13', 0), ('A10', 30), ('B1', −30), ('A15', 30), ('A12', 0), ('A0', 0), ('B6', −30), ('A7', 30), ('A9', 0), ('B0', −30), ('B6', 0), ('A15', 8), ('A2', 0), ('A4', 0), ('A11', 0), ('B3', −8), ('A0', 0), ('A3', 17), ('A4', 0), ('A4', 0), ('A12', 13), ('B6', −30), ('A13', 0), ('A11', 0)
$C_4$	('A9', 30), ('A4', 0), ('A12', 0), ('A4', 0), ('B8', −30), ('A13', 0), ('B8', 0), ('B4', 0), ('A5', 11), ('B3', −11), ('B7', 0), ('A4', 30), ('A8', 0), ('B3', −30), ('B4', 0), ('A14', 30), ('B7', −30), ('A14', 22), ('B7', −22), ('A9', 0), ('B3', 0), ('A0', 30), ('B6', −30), ('A2', 0), ('A7', 22), ('A3', 8), ('A6', 0), ('A4', 0), ('A9', 0), ('A12', 0), ('A15', 0), ('B6', −2), ('B2', −28)

5.4. 对比分析

1) 运行原理对比

遗传算法：在本文的应急物资调运问题中，遗传算法通过随机生成初始种群，并通过适应度函数评估每个个体的优劣，逐步优化运输方案。然而，遗传算法的随机性较强，容易陷入局部最优解，且计算量较大，尤其是在处理大规模问题时，收敛速度较慢。

混合算法：混合算法从车辆使用的角度出发，将问题分解为运输问题、任务分配问题和车辆路径规划问题三个子问题，依次求解。通过分阶段优化，混合算法能够有效降低问题的复杂度，减少计算量，避免遗传算法的随机性，提高求解的稳定性。

2) 稳定性对比

遗传算法：遗传算法的随机性较强，尤其是在初始种群生成和变异操作中，容易受到随机因素的影响，导致每次运行的结果可能存在较大差异。这种不稳定性在实际应用中可能导致求解结果不可靠，尤其是在应急物资调运这种对时间敏感的场景中，遗传算法的表现可能不够稳定。

混合算法：混合算法通过分阶段求解，每个子问题的求解过程都具有较高的确定性。运输问题模型和任务分配问题模型均基于确定性算法(如表上作业法和改进的K-means聚类算法)，能够保证每次运行的结果一致。车辆路径规划问题虽然使用了贪心算法，但其基于前两个阶段的确定性结果，整体求解过程仍具有较高稳定性。

3) 计算量对比

遗传算法：遗传算法的计算量较大，尤其是在种群规模较大、迭代次数较多的情况下，每次迭代都需要计算每个个体的适应度函数，并进行交叉和变异操作。对于本文的应急物资调运问题，遗传算法需要处理多个车辆的运输路线组合，计算复杂度较高，导致求解时间较长。

混合算法：混合算法通过分阶段求解，将复杂的问题分解为多个简单的子问题，每个子问题的求解过程相对独立，计算量较小。运输问题模型和任务分配问题模型均可以通过高效的算法(如表上作业法和K-means聚类算法)快速求解，车辆路径规划问题也通过贪心算法在较短时间内得到可行解。因此，混合算法的计算量显著低于遗传算法，如表10所示。

Table 10. Different operating schedules for two algorithms

表10. 两种算法的不同运行时间表

算法类型	混合算法	遗传算法
运行时间(秒)	0.04	422

4) 结果对比

混合算法的最优行驶时间为40.09小时，而遗传算法的最优行驶时间为64.4小时。混合算法的行驶时间显著优于遗传算法，表明混合算法能够更高效地完成应急物资调运任务。

5) 总结

通过对比分析可以看出，混合算法在稳定性、计算量和求解效率等方面均优于遗传算法。混合算法通过分阶段求解，能够有效降低问题的复杂度，减少计算量，并在较短时间内得到较优解。此外，混合算法的求解过程具有较高的确定性，适合应急物资调运这种对时间敏感的场景。因此，混合算法为洪灾应急物资调运方案优化提供了更为有效的方法。