联合投送运输网络中关键路段的识别模型

Identification Model of Critical Road Sections in Joint Delivery Transport Network

摘要: 本文首先针对部队联合投送的需求和特点，描述了关键路段的特征；从风险和脆弱性的角度描述了薄弱路段；从中断后影响的角度定义了重要路段；最后给出联合投送关键路段的准确定义和相关建议。

Abstract: Firstly, according to the requirements and characteristics of joint delivery of troops, this paper describes the characteristics of key sections; Weak road sections are described from the perspective of risk and vulnerability; Important sections are defined from the perspective of impact after interruption; Finally, the accurate definition and relevant suggestions of key sections of joint delivery are given.

1. 引言

联合投送 [1] 是指运用两种以上运输方式，将人员、武器装备、后勤物资等分批次快速送达作战地域的大型军事行动，其具有距离远、任务多、道路约束强等特点，对投送方案制定提出了较大的挑战。在联合投送行动中，道路可能会受到各种自然或人为因素的影响而中断，如恶劣天气、自然灾害、被敌摧毁等。不同的道路发生中断的可能性不同，中断后对整体运输效率造成的影响程度也不同。事实上，大部分的路段发生中断不会对整体运输效率有太大的影响，只有少部分“关键”的路段发生中断才会引起周围的路段产生级联效应，进而拖延整体投送进度。因此如何快速有效地识别关键路段并采取相应措施保证运输效率成为了联合投送的热点问题。

目前国内外对于关键路段的研究，主要分为对其描述和定义的研究、识别模型研究和应对策略研究三个方面。总体来看，呈现国外较多，国内较少，定义模型较多，应对策略较少，理论研究较多，算法实践较少的特点。

描述和定义研究方面，Mine和Kawai [2] 早在1982年首先定义了连通可靠性，他们将复杂路网中的所有路段根据连通状态分为0、1两种状态，即路段连通时记为1，不连通时记为0，该定义与计算机中的二进制原理相仿，用来表示路网任意两个节点间连通的状态。Sanso [3] 考虑了随机事件造成的影响或者破坏，认为可以通过路段受到灾害影响前后对整体路网的影响程度的大小来判断关键路段。Erik Jenalin S.等人采用用户均衡模型，首先对路段失效前和失效后的交通网络进行配流，然后比较失效前和失效后路网中的出行费用的增减量，确定各个路段的重要性程度。

识别模型的研究方面，Michael G. H. Bell [4] 根据图论的基本原理，使用直接度量的方法建立了重要路段的识别模型。Glen M. D. Este [5] 将路段选择的概率和重要程度联系起来，建立了Logit模型并使用迭代法对模型进行求解，得出路网中每个路段被选择的概率，结论是选择概率大的路段失效后对路网的影响也更大。D. M. Scott [6] 综合考虑路网特性，从对全局影响大小的角度定义了路网鲁棒性指数并建立了模型，有效地避免了饱和度这一指标的缺陷。黄正锋 [7] 则使用了路段重要度和通行可靠度两个指标衡量路段的通行质量，并结合基于随机用户的均衡配流模型，构建了路段质量的求解模型。涂颖菲 [8] 等使用了最小割频度向量这一指标评价路网拓扑结构的脆弱性；江伟等 [9] 给出两种识别关键路段的思路：从网络拓扑结构的静态性角度，描述了非拥挤状态下的关键路段；从动态传播角度，确定了拥堵状态下的关键路段。连冰通过计算连接度、介数和饱和度三个指标求解关键路段。张勇等则从道路的排队容量及断面通行能力两方面入手，建立基于鲁棒性指数的道路脆弱性评价模型，用于识别导致路网脆弱的关键路段。

应对策略方面，郭翔研究了在汶川地震中道路中断情况下的铁路军事运输路径优化，他提到设计运输路线时，要从风险角度考虑到突发事件的情况，如对灾害发生的地点、强度的预判，尽可能避免危险的发生，并且将可能造成的损害降至最低。安实采用博弈论的方法，把潜在威胁和管理者作为攻防博弈的双方，建立了关键路段的博弈模型。尹旭日研究了公路军事运输线路中断情况下的时间优化问题，他提出基于线路完全或部分中断的情况，车队可采取迂回、修复、倒运或直接通行的措施。

综上我们可以看出，目前国内外对于关键路段的研究较少，很多研究考虑因素单一，缺乏一定的实用性，尤其是针对联合投送运输网络中关键路径的定义和描述仍然存在较大的完善空间，对于如何识别关键路径和应该采取何种措施的相关研究较少。本文将结合路段的脆弱性和重要性两个指标，建立联合投送路网关键路段的识别模型。

2. 关键路段的识别模型

2.1. 关键路段的特征与定义

综合考虑联合投送任务要求和投送网络的一般特点，“关键路段”应具有如下三个基本特征：

1) 最优性：联合投送任务一般要求时间最短、里程最短或成本最少，故运输线路须事先规划，利用网络拓扑图和相关算法，选择“费用”最少的最优路径，因此关键路段必定位于在投送网络图的最短路径上；

2) 脆弱性：即抗干扰性，“关键路段”容易受到自然灾害、恶劣天气或敌军火力打击的影响，表现为路段的脆弱性，中断几率越高的路段，脆弱性越高，更加可能对整体路网造成影响；

3) 重要性：中断后对整个投送任务产生较大的影响，多条路线需要调整，任务总时间、里程或成本显著增大，投送路线网的整体效率明显下降，这种特性为路段的重要性，重要性越高的路段，中断后产生的影响越大。

具有这些特征路段之间的关系如图1。

Figure 1. Relationship diagram of characteristic sections

图1. 特征路段关系图

其中，集合A——运输网络中所有路段的集合，包含联合投送线路上的所有路段；

集合B——最短路径上所有路段的集合，包含所有利用网络拓扑图和相关算法筛选出来的路段；

集合C——脆弱路段的集合，包含联合投送任务中易中断的路段；

集合D——重要路段的集合，包含对联合投送整体效率有较大影响路段；

因此，综合考虑以上三个特征，将原来最优路径上易遭到破坏且在中断后对投送任务影响程度较大的路段定义为联合投送任务的关键路段。即为图1中的集合E，代表关键路段的集合。

因此，对于关键路段的描述研究，应该从以下两个层次综合考虑：首先，估测投送线路中各路段的中断的可能性，并使用概率量化这种可能性，以此表征其脆弱性；其次，量化各路段的重要程度，即中断后的影响大小；最后将两个方面综合起来，形成关键路段的识别模型。

2.2. 基于贝叶斯网络的路段脆弱性分析

首先分析关键路段的脆弱性。在战时情况下，联合投送运输线路部分路段存在一定的风险，这种风险主要来自于敌军打击破坏导致的线路瘫痪、恶劣天气导致的运输受阻或者是自然灾害导致的道路中断。每个路段中断的可能性不同，为了方便研究，本节将基于贝叶斯网络将这种可能性量化为概率 ${\lambda }_i$。

贝叶斯网络(也称有向无环图模型)，是一种概率图模型，具有概率论与图论的双重优势，可以用来准确地推理和描述问题的结构。一般来说，贝叶斯网络中的节点表示随机变量，节点之间的有向弧表示变量间的因果关系，通过图形表达不确定性，因此可以很好得描述运输网络中各路段中断不确定性。贝叶斯网络既可以通过先验概率计算后验概率，也可以根据后验概率推算出先验概率。

贝叶斯网络的基本条件概率公式：

$P\left(A|B\right)=\frac{P\left(B|A\right)P\left(A\right)}{P(\; B\; )}$

其中：A，B代表2个事件， $P\left(A|B\right)$ 表示后验概率； $P\left(B|A\right)$ 表示似然率， $P\left(A\right)$ 表示先验概率， $P\left(B\right)$ 表示全概率。

假定存在一个变量A，其存在 $a_1,a_2,\cdots ,a_n$ 共n个状态，那么根据全概率公式可以得到：

$P\left(B\right)={\displaystyle \underset{i}{\sum }P\left(B|A=a_i\right)}P\left(A=a_i\right)$

根据此公式可以进一步计算出后验概率。

在对系统性的问题进行研究时，一般采用后验概率。将联合投送运输路线视作一个系统，该方法可以计算当投送网络中断时，该路段中断的后验概率。针对联合投送的实际情况，构建基于贝叶斯网络的路段中断概率型。其具体步骤如下：

1) 确定要研究的路段，并将其定义为贝叶斯网络的根节点，这些路段所构成的集合即为所要研究的节点变量集；

2) 构建贝叶斯网络。根据各个路段之间的连接关系建立贝叶斯网络模型，根据贝叶斯网络结构给出相应的条件概率表；

3) 通过历史数据专家经验得到每个路段中断的先验概率，当路段中断的可能性没有区别时，可以用使同一个概率值。由此可以计算出各节点中断的概率及投送路线中断的概率；

4) 假设路网失效的条件下，根据模型计算各个节点的后验条件概率即为所需的路段中断概率 ${\lambda }_i$。

2.3. 基于中断后影响程度的路段重要性分析

路段的重要性描述的是路段中断后对全局运输效率的影响。事实上，当路网中某一路段遭到破坏时，不仅会导致路网中整个交通流量的重新分配，而且可能会导致网络拓扑结构中的一个或多个节点的连接失效，从而使得整个路网的拓扑结构发生变化。因此，在从路段失效后果对路段重要度进行评估时，应当从路网本身拓扑结构的改变以及路网中流量分布的变化两个角度综合考虑。

2.3.1. 网络拓扑结构上的重要性

从拓扑结构上来衡量复杂网络中各路段重要性的方法有很多，如聚类系数、平均路径长度和度分布等，但这些指标都存在一定缺陷，有的不能有效度量路段中断对整个网络连通性的影响，有的不能反映某一个连接在网络结构中的作用大小。因此，本文使用网络效率来度量整体投送网络的通行能力，其定义为：

$E=\frac{1}{N\left(N-1\right)}{\displaystyle \underset{i,j\in V,i\ne j}{\sum }{\epsilon }_{ij}=}\frac{1}{N\left(N-1\right)}{\displaystyle \underset{i,j\in V,i\ne j}{\sum }\frac{1}{d_{ij}}}$

其中，N为网络图中的节点数量，V为所有节点的集合， $d_{ij}$ 为节点i到节点j之间的最短距离。

依据此网络效率定义，将路段重要性的计算步骤表述如下：

1) 采用原始法，构建网络拓扑结构；

2) 构建邻接距离矩阵 $A=\left\{a_{ij}\right\}$ 及连接距离矩阵 $L=\left\{l_{ij}\right\}$，计算出最短路径矩阵 $D=\left\{d_{ij}\right\}$ 及运输路网的网络效率 $E\left(G\right)$ ；

3) 移除需要评价的路段i，重新构建网络拓扑结构；

4) 再次构建邻接距离矩阵 $A_i={\left\{a_{ij}\right\}}_i$ 及连接距离矩阵 $L_i={\left\{l_{ij}\right\}}_i$，计算出最短路径矩阵 $D_i={\left\{d_{ij}\right\}}_i$ 及路网的网络效率 $E\left(G_i\right)$ ；

5) 根据去除路段前后得到的路网网络效率，通过公式计算各个路段的

网络效率变化率：

${\alpha }_i=\Delta E\left(G\right)=\frac{E\left(G\right)-E\left(G_i\right)}{E(\; G\; )}$

本文中， ${\alpha }_i$ 值的大小表征了各个路段在网络拓扑结构上对路网影响程度的大小。该值越大，说明该路段中断后对运输网络造成的影响越大，即该路段的重要性也就越高。

2.3.2. 流量分布上的重要性

在联合投送行动中，关键路段的中断造成的直接影响就是部分或整体网络的运输流量重新分配，因为原本最优的路径已被破坏，故重新选择的路径方案必定会导致整体运输费用的增大，因此，在评估路段中断后的影响时，可以使用整体运输费用之和即网络的边权和来描述网络的运输效率的变化。其计算步骤具体如下：

1) 计算初始边权和。按照原本最短路径投送进行投送，计算得到边权和为：

$W={\displaystyle \underset{\left(i,j\right)\in M}{\sum }{l}_{ij}}$

其中，l_ij为点i到点j的距离，M为最短路径上所有路段的集合。

2) 计算中断后的边权和。假设车辆行驶到某节点时，发现前方路段i中断，需要绕行，此时我们需要利用基于目前的进度，重新计算得到剩余路段的最短路径，此时边权和为：

$W_i={\displaystyle \underset{\left(i,j\right)\in P}{\sum }{l}_{ij}}+{\displaystyle \underset{\left(i,j\right)\in Q}{\sum }{l}_{ij}}$

其中，P表示已经行进的路段的集合，Q表示剩余未行进的路段的集合。则边权和变化率为

${\beta }_i=\Delta W=\frac{W_i-W}{W}$

3) 将每个路段对应的 ${\beta }_i$ 进行排序。由于不同的路段中断导致整体运输效率的降低程度并不相同，所以我们在预测时需要遍历移除最优路径上的每一个路段，计算运输效率的变化值，该值越大，说明路段中断后对整体运输效率的影响越大。

此外，在遍历所有路段时，为了简化计算，本文采用Bellman-Ford算法，它是求解单源最短路段问题的一种算法，原理是对图进行 $\left|v\right|-1$ 次松弛操作，其中v为顶点数，得到所有可能的最短路段，边的权值可以为负数，实现简单，适用于更多种类的输入。它可以视作是Dijkstra算法的改良，可以计算任意两点之间的最短路径，而相较于Dijkstra算法省略了一些重复计算，提升了效率。其具体步骤如下：

Step 1：初始化。把除源点外所有顶点的最优距离估计值作 $d=\left[v\right]\to +\infty ,d=\left[s\right]$ 处理。

Step 2：迭代求解。对边集E中的每条边进行多次迭代操作，让顶点集中各个顶v的最优距离估计值与最优距离(运行 $\left|v\right|-1$ 次)相接近。

Step 3：检验负权回路。分析边集E中每条边的两个端点是否收敛。如果顶点都收敛了，说明算法是正确的，并把这段距离进行保存，证明其是最优的距离；如果没有收敛，则说明算法是错误的，这段距离不是最优距离。

Step 4：对各路段进行迭代并进行排序，得到结果。

2.4. 关键路段的识别模型

在上面的分析中，分别从中断风险概率的角度，描述了路段的脆弱性程度，又各从网络结构和对全局影响的方面，量化了路段的重要性，但都具有一定的局限性，因此需要综合两个层次的研究，建立综合的识别模型。

为了更加直观、全面的识别关键路段，结合关键路段最优性、脆弱性和重要性三个特点，本文引入路段的关键度这一概念，并定义联合投送路网中编号为i路段的关键度 ${\theta }_i$ 为

${\theta }_i={\lambda }_i\left[\epsilon {\alpha }_i+\left(1-\epsilon \right){\beta }_i\right]$

其中， ${\lambda }_i$ 为路段i的中断概率， ${\alpha }_i$ 为网络效率变化率， ${\beta }_i$ 为中断后费用变化率， $\epsilon$ 为相对重要性参数，当路网负荷较大而失效后影响较小时， $\epsilon$ 较大；反之， $\epsilon$ 较小。一般情况下，取该值为0.5，也可根据实际需求，由专家评估确定。

依据此模型，计算运输网络中的每一个路段的关键度，并将最终所有路段的关键度进行排序，取关键度最高的路段为关键路段。

综上，联合投送关键路段的识别流程图如图2。

Figure 2. Flow chart for identification of key sections of joint delivery

图2. 联合投送关键路段识别流程图

2.5. 基于关键路段的投送方案调整

上节通过分析中断概率和中断后影响的方法，建立了关键路段的识别模型。而识别关键路段的最终目的是要针对关键路段，采取相应的措施，保障运输网络的稳定运行。结合联合投送的实际要求，通常有以下方法：

1) 集中资源对关键路段进行重点保护，对道路进行加固。

2) 避开关键路段。规划投送路径时，不选择原本最优的路径，而选择除去关键路径外的最优路径，防止事故的发生。

3) 减少关键路段上的运输量。在规划路径时，人为减少关键路段的权值，使其运载荷量较少，以此减轻中断后的影响。

3. 案例分析

3.1. 任务想定

某次联合投送任务计划以公路和铁路为主要投送方式，要求在时间最短的情况下，将物资和兵力从若干源点投送到若干目的地。其投送规则如下：

1) 投送分为A、B、C三个编组，同一个编组只能在同一条路线上行进，且A组优先用铁路进行投送，B组在发生冲突时具有优先通过权；

2) 各编组在是运输途中不能停留，必须连续投送；

3) 单个编组只允许铁路转公路，且最多中转一次；

4) 不能超过各个路段的最大容量；

5) 投送起点和终点需进行装卸载：铁路为18梯队/每天，公路为15梯队/每天。

各个路段编号及相关信息见表1。

Table 1. Road section information table

表1. 路段信息表

3.2. 计算路段关键度

按照第二章和第三章中的步骤，首先根据路径连接情况建立如图3所示的投送网络拓扑图。

其中，圆圈为运输网络节点， $\left\{{\text{a}}_1,\cdots ,{\text{a}}_{13}\right\}$ 代表十三个出发源点， $\left\{{\text{b}}_1,\cdots ,{\text{b}}_8\right\}$ 代表八个目的地， $\left\{{\text{c}}_1,\cdots ,{\text{c}}_8\right\}$ 代表可能经过的节点，节点之间的实线表示通过公路运输，虚线表示通过铁路运输，其长度不代表实际里程，标识的数字表示通过该方式运输的时间期望值。

基于以上所构建的网络拓扑图，求解关键路段和最优路径，具体步骤如下：

Step 1：数据预处理。首先根据网络拓扑图中的连接关系和边权值，建立并利用matlab软件分别储存通过公路和铁路运输时间的邻接矩阵和距离矩阵。由于矩阵较大，图4和图5故只截取了通过公路运输的部分节点之间邻接矩阵和距离矩阵，其中inf在matlab中表示无穷大，即代表两个节点不相邻。

Figure 3. Network topology diagram

图3. 网络拓扑图

Figure 4. The adjacency matrix between partial nodes

图4. 部分节点间的邻接矩阵

Figure 5. The distance matrix between partial nodes

图5. 部分节点间的距离矩阵

利用matlab软件中的shortestpath函数计算单个编组投送的最短时间(表2)。

Table 2. The minimum delivery time for each group

表2. 各编组的最短投送时间

Step 2：脆弱性评估。根据贝叶斯网络模型分析路段的脆弱性。图中共有13个出发点，8个目的地，因此贝叶斯网络模型的OD对共有104个，规模较大。通过计算或使用贝叶斯推理软件，得到各路段的后验条件概率，即路段的失效概率。

Step 3：重要性评估。依次移除每个路段，并计算网络结构上的重要性和流量分布上的重要性。

Step 4：识别关键路段。根据模型计算出关键路段并从大到小进行排序，所有路段关键度的分布图见图6。

关键度最高的10个路段见表3。

因此，关键度最高的路段是编组为75的路段，即为本文要求的关键路段。

Figure 6. Section criticality distribution map

图6. 路段关键度分布图

Table 3. The criticality of some sections

表3. 部分路段的关键度

4. 总结

本文结合联合投送的实际要求和特点，从路段的最优性、脆弱性和重要性对关键路段进行了描述和定义，建立了关键路段的识别模型，此模型为关键路段的识别提供了理论依据，对提升联合投送运输路线的稳定性和抗干扰性有一定的帮助。同时，此模型仍然有以下不足之处：

1) 此模型需要遍历投送网络中的所有路段，因此对于大规模的运输网络，效率较低，可考虑预先对路段进行专家评估，减少需要计算关键度的路段数量，以此提升模型效率。

2) 此模型依赖于在复杂网络中快速搜寻最短路径的算法，因此算法的复杂度和运算速度决定了模型的效率，可考虑对路段进行标记，避免重复计算。

基金项目

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

NOTES

^*通讯作者。