基于动态网络图和泛洪算法的联合投送问题建模与优化

Modeling and Optimization of Joint Delivery Problem Based on Dynamic Network Graph and Flood Fill

摘要: 联合投送能力是信息化背景下联合作战的重要基础保障。本文首先基于层次分析法建立了关于总投送时间、编队投送时间、总投送里程、道路负荷等因素的投送方案评价指标模型。然后以完成总任务时间最少为目标，引入了动态网络图模型，建立了基于泛洪算法的联合投送规划方案，进而引入遗传算法降低了模型运算复杂度，最后结合网络图关键节点路径稳定性分析，对于投送方案模型进行了优化。

Abstract: Joint projecting capability is an important basic guarantee for joint operations under the back-ground of information technology. Firstly, based on the analytic hierarchy process (AHP), this paper established the evaluation index model of delivery scheme for factors such as total delivery time, formation delivery time, total delivery mileage, road load and so on. Secondly, with the goal of minimizing the total task time, a dynamic network graph model was introduced, and a joint project planning scheme based on flooding algorithm was established. Furthermore, the introduction of genetic algorithm reduced the computational complexity of the model. Finally, combined with the analysis of the path stability of the key nodes in the network diagram, the delivery scheme model was optimized.

1. 任务想定

1.1. 问题背景

联合投送 [1] 是联合作战的重要组成部分，高效的联合投送能力是联合作战、联勤保障的客观要求。“联合”是手段，而“投送”是目的，为了高效、快速、有序地完成投送任务，必须全方位多角度综合各因素进行考虑，多元化投送模式对于如何实现联合作战的兵力投送部署提出了严峻的挑战，所以研究联合投送问题对于提升战斗力至关重要。

1.2. 任务想定

想定以战时状态下，通过公路、铁路实现由若干梯队构成的编组投送，并且模拟一定的规则，包括道路通行规则、连续投送规则、路段容量限制规则和装卸载规则，用以限制投送方案的制定，使其更贴近军事任务现实需要。

综合考虑总任务完成所需要的时间、各编组投送所需要的时间、总投送成本、总投送的里程数以及投送任务对于道路所造成的负荷情况，设计相应的投送方案，建立相应的投送方案模型，从而完成特定要求下各梯队投送的路线、出发时间、编组的投送分组等方案设计。

1.3. 任务分析

首先将投送方案设为目标，结合层次分析法确定一个评价模型，找出最优投送方案相应的评价体系；在此基础上，由于作战任务通常具有紧急性和时效性，我们考虑将投送任务完成总时间最短作为评判投送方案优劣的最主要指标；考虑到为了使相应的总时间最少，每条投送路线所用的时间都需要尽可能得少，并且由于决定总时间长短的为时间最长或者最慢完成的投送路线，所以本文选择研究各投送任务出发点以及目标点之间的最短时间的路径，并且将时间越长、路途最远的投送任务路线优先考虑，使其尽量满足最短路径的要求，在其基础上考虑其他相对时间较短的投送路线；由于道路容限以及装卸载限制原则，本文考虑在最短路径的基础上引入动态网络图 [2] 概念，根据限制原则进行网络图动态结构修正，并且综合考虑投送要求，得到总时间最短的最优投送方案。

2. 基于层次分析法的投送方案评价指标模型

在一次联合投送行动中，评价其方案好坏的指标有很多，包括任务完成总时间、各编组完成投送的时间、总共投送行进里程、投送成本、道路的负荷与损害，甚至包括作战任务的保密程度，运输安全等都会列入对于一项联合投送任务的评价体系中。然而由于各指标的重要程度不同，对于任务评价的影响度不同，根据任务不同评价因素也不同，建立一个较为普遍适用的联合投送方案评价体系是确保投送方案的有效性和高效率的基础。

当前军队担当的需要联合投送的任务主要分为演练演习、抗洪救灾、换防移防等。针对演练演习所涉及到的联合投送任务，通常涉及部队多，军种多，并且作战任务的秘密级别较高，且前期均会经过周密的计划。在此类联合投送任务中，总完成时间的重要性就有所下降，同时其他因素的重要性相应有所上升，投送里程较多容易造成部队疲惫，影响后期演习任务的完成，所以针对此类作战任务投送兵力的设计方案重心就会有所改变。

而针对抗洪救灾任务，此类任务通常发生突然，并且较为紧急，需要部队尽快赶往相应任务地点，此时兵力投送方案的评价指标就必须着重考虑总任务完成时间以及各编队完成任务的时间。相对而言，换防移防工作对于时间的要求就较低，反而对于总投送里程以及道路负荷量的要求较高，此类任务通常进行周期较长，参与人数较多，为了减少对于地方交通的影响，通常会采取速度较慢的方式进行。

2.1. 联合投送指标分析

2.1.1. 时效性

联合投送任务通常具有时效性。投送部队任务完成的速度，直接影响到战局中能否抢占先机，或者能否占领有利地势对敌实施打击等，尤其是如部队需对于敌方实行突击埋伏等类型的作战任务时，最大程度减少投送总时间是对敌实施有效打击的基础；同时，考虑联合作战任务的配合性，联合投送任务需要尽量综合各个编队完成投送任务的时间，以有效进行衔接配合。

2.1.2. 节能性

联合投送任务通常要求节能性。在真正的作战环境下，后方补给容易出现困难，所以作战任务需要尽量减少能耗，这就包括减少各编组完成投送任务的里程数、投送总成本、对于道路的负荷以及损害程度。完成投送兵力任务消耗的里程数越多，对于油料的消耗会增多，对于部队后期的机动能力容易造成影响。同时由于现阶段部队投送及运输相关活动均使用与地方公用的交通线路，如果对于道路负载较大，容易造成拥堵，对于地方车辆行驶造成影响，并且道路负荷较大容易损坏道路，这会影响之后的兵力运输与投送，并且道路修复也需要花费较大时间精力。

2.1.3. 安全性

联合投送任务通常考虑安全性。一般情况下，考虑到军事活动的特殊性，为了保障部队安全，联合投送对于任务的保密性及安全性要求较高，说明其不能完全暴露以防造成军事秘密泄露的情况。对于部分联合投送兵力的编组对于其出发时间以及在道路上行驶的时间需要加以限制，尽量在黑夜车流量较少的情况下进行。此外，还应考虑运输途中可能发生的运行事故，包括自然灾害、交通事故及敌情分布等。

综合以上考虑，建立如图1所示的联合投送方案评价体系。

2.2. 利用层次分析法建立评价体系

层次分析法(AHP)主要根据专家打分原理，利用两个指标间的相对重要性得出判断矩阵，在验证矩阵满足一致性要求后，计算出特征向量并作为各指标的权重。以下为层次分析法的一般步骤：

Step 1：建立判断矩阵。首先由熟悉问题的专家独立给出如表1所示的判断矩阵 $C={\left(C_{ij}\right)}_{n\times n}$，其中C_ij表示指标i和指标j相对重要值。

Figure 1. The project evaluation system of joint delivery

图1. 联合投送方案评价体系

Table 1. Judgment matrix

表1. 判断矩阵

Step 2：检验矩阵一致性。在多指标的条件下下，矩阵极易出现不一致的情况，因此本文采用计算矩阵CR值的方法判断矩阵一致性是否符合要求：若CR < 0.10，则认为矩阵通过一致性检验。其中

$CR=CI/RI$ (2.1)

n维矩阵的CI值计算公式：

$CI=\frac{{\lambda }_{\max }-n}{n-1}$ (2.2)

其中l_max为矩阵最大特征值。

n维矩阵的RI值如表2：

Table 2. RI value of n-dimensional matrix

表2. n维矩阵的RI值

计算层次总排序。

3. 基于动态网络图及泛洪算法的联合投送模型

想定任务为多出发地、多目的地且多批次的动态网络优化问题，既要对于各梯队的投送路线进行优化，也要对与各梯队的投送批次安排进行优化，并且要综合考虑道路通行能力对于兵力运输投送的限制，本文引入动态网络图对于联合投送方案进行动态的优化分析，并在此基础上利用泛洪算法 [3]，在优化分析的基础上寻求充分利用道路容限能力以及时间最短的最优投送方案。考虑到时间的硬性要求，本文以总时间最短为目标进行方案设计。

3.1. 基于动态网络图与泛洪算法的投送方案模型

设在此次联合投送的军事行动中需要投送的编组分别部署在 $\left\{x_1,x_2,x_3,\cdots ,x_N\right\}$ 共N个出发地，需要将其投送至 $\left\{y_1,y_2,y_3,\cdots ,y_M\right\}$ 共M个出发地，其中 $r_{ij}\left(i=1,2,\cdots ,N;j=1,2,\cdots ,M\right)$ 是需要从 $x_i$ 到 $y_i$ 投送的梯队数。这些梯队分为多个不同编组，每一编组可以同时有多个梯队在不同道路上连续行进，他们共享道路的通行所有权，除了道路限制及节点装卸载限制外在行进过程中互不干涉。

想定任务要求考虑总时间最短的投送方案，故可将通过每条路的时间作为边的权值，问题即为求得满足条件的最长时间最短的联合投送方案。可以将运输网络图表示为 $G\left(V,E,C,T\right)$，其中V表示节点，E表示边，C为各边的通行能力，T为通过各边所需要的时间。

综上，可以建立如下联合投送方案优化模型：

s.t.

${\displaystyle {\sum }_{w_{ij}\in I}{r}_{i,k,m}}\le C_m$ (3.2)

$r_{i,k,m}\ge 0$ (3.3)

$trans\left(x_i,v_k\right)=\{\begin{array}{l}0当在此点未转换运载方式\\ 1当x_i出发在v_k点由铁路转换运载方式为公路\\ 2当x_i出发在v_k点由公路转换运载方式为铁路\end{array}$ (3.4)

${\displaystyle {\sum }_{k}trans\left(x_i,v_k\right)}\le 1$ (3.5)

$T_{OD}=t\left(D\right)-t_0=v^{*}$ (3.6)

$\langle w_{iq},v_k\rangle =\langle w_{ip},v_k\rangle$ (3.7)

其中，式(3.1)为目标函数，表示从出发地 $x_i$ 开始搜索用时最短的路径；式(3.2)和式(3.3)为路段容量限制， $w_{ij}$ 表示第i个编组出发第j天的梯队数，其对于第m条道路的占据量为 $r_{i,k,m}$，这个数值不能超过该条道路的容量限制 $C_m$ 且不能为0，I为当前时刻正在行进的所有编组及梯队的集合；式(3.4)和(3.5)限制了在投送途中只能由铁路转公路，且仅可转换一次；式(3.6)限制了同一批次中间节点不存在停留且连续投送；式(3.7)限制了同一编组兵力投送路线一致。

3.2. 求解步骤

Step 1：通过引入虚拟节点和删除多余节点的方法，将网络图中的边权值标准化到[0, 1]之间，并将其储存到如下所示的矩阵中：

$R=\left[a,b,t,C\right]$

其中，a表示路段起点，b表示路段终点，t表示标准化后的路段权值，C表示路段的容量。

Step 2：Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，能有效解决有权图中最短路径问题。其算法步骤如图2所示：

1) 初始时令 $S=\left\{x_i\right\}$， $\bar{S}=V-S$， $\bar{S}$ 中顶点间若与 $x_i$ 连通，则 $t\langle x_i,v_k\rangle$ 为此路径消耗的时间，若不存在则为∞。

2) 从 $\bar{S}$ 选取一个与S中顶点有关联边且时间消耗值最小的顶点v，加入到S中。

3) 当加进顶点v作为中间点时，首先判断顶点的通行能力是否代表铁路，若代表铁路，则判断标记过的定点v中是否存在代表公路的铁路，若存在，即将v加入S，若不存在，则判断 $x_i$ 到 $y_j$ 的消耗时间是否减少，当减少后，则对其余 $\bar{S}$ 中顶点的时间消耗值进行修改，同时对v进行标记。

4) 重复上述步骤，直到S中包含所有顶点，所有标记顶点即构成 $x_i$ 到 $y_j$ 的消耗时间最少路径。

5) 由于不考虑节点转运时导致的时间消耗，所以通过Dijkstra算法找出的最短耗时路径即为所需要的最短耗时路径，消耗的时间即为t，同时记该路径上的最大通行能力为P。

Figure 2. Flowchart of Dijkstra algorithm

图2. Dijkstra算法流程图

Step 3：计算各条投送梯队完成任务所需要的最短耗时，选择其中单耗时最长的路径规划优先进行考虑，使其尽量满足最小时间消耗，从而确保最终完成派送人物的总时间最短。若多批队目标点相同时，需考虑各编组优先级，并根据最短路径上各路段的通行能力，安排相应的投送计划与梯队分配人数，改写任务矩阵。

接着标记投送任务未来每天的道路占用情况，根据矩阵中第三列代表的消耗时间，计算此时已消耗的总时间，向上取整，即可得到此动态图相应时间段后的网络图改变情况，即完成拓扑结构的实施动态更新。

为了计算剩余各条投送任务的最短耗时路径以及最短耗时，本文依据图像处理中的泛洪算法原理，对于该节点之后的路径进行遍历以确保不会出现遗漏情况，从而通过比较确定最短时间兵力投送方案。

Step 4：根据动态网络图中各个路段每天的通行能力，计算完成剩余各条投送任务的最短消耗时间，按照Step 3中原则安排并改写矩阵。重复执行以上除Step 1外所有步骤，直至完成了所有的投送任务。将最终得出来的最优最短时间投送计划进行分析，判断各节点装卸载规则是否满足题目得装卸载规则要求，若是不满足，则舍去该结果，从而获得次优时间较短运输路径，若满足，即为题目所求总任务进行时间最短得最优方案。

3.3. 基于遗传算法优化的联合投送模型

由于利用泛洪算法进行遍历从中找出最优路径所需的时间复杂度较高，通过网络计划优化在问题数量增大的情况下，复杂度会急剧提升，不适用于显示复杂的兵力投送调度问题，因而通过启发式算法进行最优路径选择即模型优化较好。

为了防止采用遗传算法在工作数量过大的情况下出现过早收敛的情况，本文选择利用自适应遗传算法来解决道路承载能力限制下的复杂多任务兵力派送问题的优化。

本题利用遗传算法找出所有编组的投送路线以及派送顺序及人数，在求解之前，需要进行染色体编码。总共有N个编组等待配送，每个编组有 $r_i$ 个编队待投送，则待投送梯队为：

$SUM={\displaystyle {\sum }_{i=1}^N{r}_i}$ (3.8)

则该染色体的长度即为SUM。

可以用 $M_k$ 表示当前种群中的第k条染色体， $P_{kj}$ 即可表示为染色体的一条基因，表示在染色体j位置上第 $P_k$ 个编队中的梯队， $M_k$ 中梯队的派遣顺序即为满足道路通行规则的前提下的任意排序。通过最小总时间优先准则作为启发式方法，以产生对于投送任务小姑最好的初始染色体。

标准遗传算法容易出现复杂问题下过早收敛的情况，此时得到的大多为局部最优值，而非全局最优解，为了解决此项缺陷，就要将遗传算法中的交叉概率 $P_c$ 与变异概率 $P_m$ 于适应函数关联起来。由于为求得方案为总时间最小方案，则确定适应函数为

$f=C_{MAX}-T_i$

即得到如下自适应参数公式：

$P_c=\{\begin{array}{l}{P}_{c\max }{f}_0<f_{org}\\ P_{c\max }-\frac{\left(P_{c\max }-P_{c\min }\right)\left(f-f_{org}\right)}{f_{\max }-f_{avg}}{f}_0\ge f_{org}\end{array}$

$P_M=\{\begin{array}{l}{P}_{M\max }f<f_{org}\\ P_{M\max }-\frac{\left(P_{M\max }-P_{M\min }\right)\left(f-f_{org}\right)}{f_{\max }-f_{avg}}f\ge f_{org}\end{array}$

其中， $P_{c\max }$ 、 $P_{c\min }$ 分别为交叉概率的最大最小值； $P_{M\max }$ 、 $P_{M\min }$ 分别为变异概率的额最大值与最小值； $f_{org}$ 代表每代群体的平均适应度值， $f_0$ 为要交叉的两个个体中较大的适应度值；f为要变异个体的适应度值。

模型的评价指标即为完成所有兵力投送任务花费的总时间。时间越短，则说明模型越优。

4. 模型的稳定性分析及改进

为了分析联合投送方案的稳定性，首先需要衡量网络拓扑结构的稳定性，网络节点的度、平均路径长度和聚类系数是描述网络结构的基本统计指标 [4]。

在网络中，度表示与节点相邻的边的数目，度值的大小反映了节点的连通性，在图中节点 $v_i$ 的度记为 $de\left(v_i\right)={\displaystyle {\sum }_j{a}_{ij}}$，其中 $a_{ij}$ 为节点i与节点j之间的连接边的数目。平均度

$de\left(v\right)=\frac{1}{Q}{\displaystyle {\sum }_j{a}_{ij}}$ (4.1)

网络中度为 $de\left(v\right)$ 的节点数站网络节点总数的比例为度分布，Q代表节点的个数，记为

$P\left(de\left(v\right)\right)=\frac{\partial p\left(D>de\left(v\right)\right)}{\partial de\left(v\right)}$ (4.2)

用 $l_{ij}$ 定义节点i，j之间最短路径上的边数，网络中两个顶点之间的距离的平均值定义为平均路径长度L：

$L=\frac{1}{1/2Q\left(Q-1\right)}{\displaystyle {\sum }_{i>j}{l}_{ij}}$ (4.3)

网络中的聚类系数通常用来衡量节点聚类情况，节点i的聚类系数反应此节点所有相邻节点之间实际连边数目占改点的最大连边数目的比例，用 $C_i$ 表示：

$C_i=\frac{2E_i}{de\left(v_i\right)\left(de\left(v_i\right)-1\right)}$ (4.4)

$de\left(v_i\right)$ 表示此节点与其他节点的连接边数， $E_i$ 表示 $de\left(v_i\right)$ 与节点i相邻的节点之间的实际边数。取其平均值为C，当C为1时，图上所有节点相连，C为0时，图上所有节点均不相连。

一个节点或者一条边发生改变，都有可能对整个网络产生影响。由于天气条件的突发性或者作战任务中敌方对于交通线的破坏，会导致整个运输网络受到极大影响，本文对受突发因素影响后产生的运输网络的新邻接矩阵进行计算，通过聚类系数、平均路径长度、最大连通图的相对大小三个拓扑网络指标的变化趋势，来分析运输网络图在遭受突发破坏后的稳定性变化。

由于天气造成影响是随机的，对于运输网络的破坏具有一定的随机性，所以随机删除网络图少量部分边或者节点，此时重写网络图的邻接矩阵，并且对其相应指标进行计算。聚类系数下降较少，网络表现出较强的聚集性，持续增加删除数量，当删除部分占全部的40%时，网络图聚集性急剧下降，网络图聚集系数同时急剧滑落，说明网络稳定性已经遭受破坏。

若是敌方有意破坏兵力投送运输线路，即会挑选连通度较强的交通枢纽，将任务所有节点的度数进行排序，从上至下破坏节点以及相应的交通线路，可以发现，关键节点及线路被破坏后对于运输网络图的破坏是显著的，图的聚类系数以及连通性均急剧下降，最大连通子图所含节点数仅为原图的三分之一。

在此基础上，考虑最短任务完成总时间的兵力投送方案发现，该方案中设计重要路段及节点的线路方案占总线路方案的75%，所以当关键节点遭到破坏或者损坏导致相应的路线不连通或者运输承载能力下降，对于总体任务的有效安全完成会造成较大的威胁。

针对此种情况，我们对于兵力投送方案模型进行改进，综合考虑总任务完成时间、各编队投送时间、总投送里程、道路负荷等因素，建立改进过后的兵力投送模型：

目标函数改为如下：

$T=\min \left(\alpha \max \left(t\left(x_i\right)\right)+{{\displaystyle \sum }}^{\text{}}\left(\beta t\left(x_i\right)+\gamma L\left(x_i\right)+\delta r\left(x_i\right)\right)\right)$

其中 $\beta ,\alpha ,\gamma ,\delta$ 均为比例系数，由作战任务具体需求决定， ${\displaystyle \sum t\left(x_i\right)}$ 表示各编组投送时间之和， ${\displaystyle \sum L\left(x_i\right)}$ 表示总投送里程， ${\displaystyle \sum r\left(x_i\right)}$ 表示总道路负荷。

基金项目

本文由陆军工程大学基础培育项目资助(KYJBJQZL1924)。