最短路问题与标号算法(label correcting algorithm)研究(6) - 扩展阅读

前文回顾

这是全文第四章拓展阅读，也是全篇的最后一个章节。在前三章的内容里，我们详细介绍了最短路问题及其数学模型、最短路径求解算法以及单源、多源Label Correcting Algorithms的核心内容。本章将介绍如何利用前文介绍的算法求解多目标最短路径问题以及如何处理大规模网络。点击下方链接回顾往期内容：

最短路问题与标号算法(label setting algorithm)研究(1) - 开篇介绍

最短路问题与标号算法(label correcting algorithm)研究(2) - 最短路径问题简介

最短路问题与标号算法(label correcting algorithm)研究(3)

最短路问题与标号算法(label correcting algorithm)研究(4)

最短路问题与标号算法(label correcting algorithm)研究(5)

除此之外，本文的附录部分补充了Label Correcting Algorithm如何处理含有负环的网络最短路径问题，给出了本文所研究的简单有向图，还提供了由周学松老师开发的NeXTA软件，辅助最短路问题学习。

4

拓展阅读

4.1 多目标最短路径问题求解

在前边我们介绍最短路径问题时优化的目标是找到从节点到节点的最短路径长度，目标是单一的。但是在很多情况下我们不仅追求最短路径，还希望通过这条路径能获取最大收益，这就是多目标最短路径问题。其中最小成本-时间比问题是典型的多目标最短路径问题，是指在有向图上，每条弧都有一个成本和一个旅行时间，我们希望找到一个有向环，它的成本与旅行时间之比最小。为了清楚说明这个问题我们以"不定期船"的题举例说明：一艘不定期船从一个港口到另一个港口，载运货物和旅客，从港到港的航程赚取单位的利润，需要时间。我们想知道轮船应该去哪些港口，按照什么顺序最后回到出发点时所消耗的时间最少，获得的利益最大。我们可以通过确定一个总利润与总旅行时间之比最大的有向循环来解决这个问题。

在不定期船问题中，我们希望确定一个有向循环使得最大。我们可以将弧的成本定义为，把问题转化为希望确定一个有向循环，使得最小，其中。之后我们可以通过反复应用负环检测算法来解决这个问题：假设为最优值，对于任意的值，我们重新定义弧长，并采用负环检测算法进行搜索：

1.网络中找到一个负环：即，所以,此时为上界；

2.网络中没有负环，但是存在长度为0的环：即，所以，此时，为最优值；

3.网络中所有有向环的长度均为正值：即，所以,此时为下界；

通过前面的分析，我们提出以下的搜索步骤来解决最小成本时间比问题：①随机猜测一个的值并重新定义弧长；②采用最短路搜索算法，进行求解；③如果找到一条负环，则说明值过大，将值调小，返回第①步，如果找到一条长度为0的环，则找到最优值，结束迭代，如果找到一条长度为正值的环，则说明值过小，将值调大，返回第①步。此算法实现的关键在于如何调整的值？下面我们介绍两种常用的方法。

（1）顺序搜索

假设已知的上界为，重新定义弧长后采用最短路算法进行搜索，如果找到一条长度为0的环，则已找到最优值，结束迭代；如果找到一条负环，则下一次搜索时令。重复下去便可得到：，最终得到最优解。

（2）二分搜索

假设我们已知所在区间为[]，每次迭代时取，重新定义弧长后采用最短路算法进行搜索，如果找到一条负环，则，下次迭代时更新区间上界，如果找到一条长度为正值的环，则，下次迭代时更新区间下界，如果找到一条长度为的环，则算法结束，找到最优值。在每次迭代时取值区间都缩减为原来的，现在我们考虑如何确定初始的：令为所有弧长的最大值，则即为一个包含的区间。

4.2 大规模最短路径问题求解

在解决实际问题时我们面临的网络规模可能非常大，例如国家高速公路、省主干公路与农村公路等组成的国家公路网络，又如城市快速路、主干路、街道等主城的城市公路网络，本文所介绍的几种算法显然不太适合直接求解这样规模的网络最短路径问题。

这里介绍两种解决大规模网络最短路径问题的思路。第一种，将大规模网络依据某些网络属性进行"分解"，对"分解"后的子网络进行最短路径求解，然后"组合"子网络最短路径得到原网络的近似最短路径，这种算法称为Hierarchical Algorithm（HA）。第二种，基于并行计算框架，将算法由串行计算改进为并行计算，提高计算效率。本文以智能交通系统中近似最短路求解^[6]^为例给出第一种思路的一般步骤，第二种思路读者可参考文献^[7]^进行学习。

4.2.1基本思想

设计该算法的一个关键思想是根据交通网络的自然层次结构，建立一个层次化的网络拓扑结构。该网络拓扑结构包含两级网络：第一级为上层网络，这类网络对应交通网络中决策频率低（需求频率低），但决策权重重要的道路，例如高速公路；第二级为下层网络，这类网络对应交通网络中的决策频率高（需求频率高）的道路，例如街道、城市快速路等。上层网络中的节点和弧是整个网络的宏观体现，并且上层网络包裹的若干区域即为下层网络。下层网络是整个网络的某个局部的微观体现。通过这种分解，我们可以通过组合包含起点的下层网络的近似最短路径、上层网络的近似最短路径、包含终点的下层网络的近似最短路来求解网络中任意节点对之间的近似最短路。

这里需要解释下为什么对下层网络求解的最短路径称为近似最短路径。因为在求解任意两点间的最短路径时应该考虑网络中所有的弧，而求解下层网络内节点间的最短路径时仅考虑了局部范围内的弧，因此可能得到的是局部最优解，故称为近似最短路径更为合适。

4.2.2关键步骤

步骤一：网络分解（Decomposition）

从原始网络G中提取一条强连接，但不一定是完全稠密的道路，称为上层网络，，为非负弧长函数，中的节点称为上层节点（宏节点），中的弧称为上层弧，上层网络中的路径称为上层路径。根据上层网络所包裹的区域，将原始网络划分为个下层网络，,,。中的节点称为下层节点，中的弧称为下层弧，下层网络中的路径称为下层路径。此外，对于下层网络的划分方法不唯一，只要满足每个下层网络至少包含一个上层节点即可。注意：在划分下层网络时，上层网络的节点被包含在某些下层网络中。

对于任意上层弧都对应原始网络中从节点到节点的某些下层路径（不一定是最短路径，也可能是近似最短路径，具体取决于网络结构），其弧长为。

步骤二：约束最短路（Constrained Shortest Paths）

分别求解上层网络和下层网络中任意节点对的最短路径（或者根据实际问题需求求解所有最短路径，或者部分最短路径）：

上层网络最短路径：

下层网络最短路径：

步骤三：组合（Combination）

假设节点，节点，如果，则节点i和j属于同一下层网络，因此从节点到节点的近似最短路为步骤二所求结果。如果，则分以下情况进行最短路径组合：

(i)从下层网络下层节点i到上层网络上层节点的最短路径，且。也就是说上层节点是上层网络和下层网络共享节点；

(ii)上层网络中从节点到节点的最短路径，且上层网络节点属于上层网络和下层网络的共享节点；

(iii)下层网络中从共享节点到下层节点的最短路径。

这里的(i)和(iii)中的上层节点和其实也是下层网络中的节点。简单来说在求解原网络任意两个节点间的最短路径时分两种情况考虑：起点和终点在同一个下层网络，起点和终点不在同一个下层网络。我们注意到在步骤三组合最短路径时可有多种方法选择，由此衍生出不同类型的HA算法。在下一章节将进行介绍。

4.2.3步骤解读

（1）网络分解方法

在层次算法的分解阶段，显然有许多可能的方法来选择上层节点、上层弧和下层网络。然而，在一个特定的应用场景中，弧通常有一个自然的层次结构。例如，在一个交通网络中，上层网络可以是由高速公路和主干公路组成，上层节点可以是高速公路的出入口，上层弧段可以是高速公路和主干公路。下层网络可以是由这些高速公路和主干公路包裹的子交通网络。有时候为了从原始交通网络中提取一个具有强连接、高密度的上层网络可以适当调整网络分解规则。

（2）最短路组合规则

如果在组合阶段，不同的下层网络分别包含起点和终点，如果每个下层网络只包含一个上层节点，那么如何根据HA的描述来构造近似路径是很明确的。然而，在实际中，下层网络中可能包含多个上层节点。在这种情况下，我们需要在这些上层节点中做出选择。一个直观的想法是选择最近的上层节点。换句话说，我们选择距离起点最近的上层节点，距离终点最近的上层节点。假设节点为起点，节点为终点，可以按以下规则选择上层节点（8）:

基于以上节点选择规则的HA算法称为Nearest HA。

显然，在所有HA变体中，就所获得的解决方案的质量而言(但就计算时间而言，也是最昂贵的一个)，最好的选择规则是选择产生最短近似路径的一对上层节点（9）：

基于以上节点选择规则的HA算法称为Best HA。

有时会有多个下层网络包含起点(或终点)。在这种情况下，我们将调整Nearest HA的上层节点选择规则（10）：

4.2.4案例解读

假设某交通网络如图4-1（a）所示，接下来我们按照上述步骤求解其任意节点间的近似最短路：

步骤一：网络分解。这里我们以枢纽节点及主干道构成的网络为上层网络，被上层网络所包裹的区域为若干子网络，"分解"结果如图4-1（b）所示。4-1（b）中共有4个下层网络，即H=4，分别命名为下层网络1,2,3,4：下层网络1共包含普通节点1-1,1-2,1-3,1-4,1-5以及上层节点I,II,III,IV；下层网络2共包含普通节点2-1,2-2,2-3以及上层节点III,IV,V；下层网络3共包含普通节点3-1,3-2,3-3,3-4以及上层节点II,V；下层网络4共包含普通节点4-1,4-2,4-3,4-4以及上层节点VI,VII。对于如何将上层网络节点分配到下层网络中没有严格要求，但应保证每个下层网络至少含有1个上层节点。而且分配结果将影响解的质量。

步骤二：约束最短路径。分别求出上层网络任意节点间的近似最短路径（各枢纽节点间的最短路径）、每个下层网络内任意节点间的近似最短路径。

步骤三：组合。这里需要分情况进行讨论。以节点I到节点1-5的最短路径为例，因为二者同属一个下层网络，因此步骤二中所求的最短路径即为节点I到节点1-5的近似最短路径，即对应（i）的情形；以节点1-4到节点I的最短路径为例，因为二者同属一个下层网络，因此步骤二中所求的最短路径即为节点1-4到节点I的近似最短路径，即对应（iii）的情形；以节点1-1到节点2-1的最短路径为例，因二者不在同一个下层网络，因此需要借助上层网络节点组合最短路径，首先节点1-1可以到达的上层节点有I, II, III，节点2-1可以达到的上层节点有III, IV, V。若采用Nearest HA组合规则，则分别找出距离节点1-1和节点2-1最近的上层节点，假设分别为I, III，则节点1-1到节点2-1的近似最短路径为L~1-1,I~+L~I,III~+L~III,2-1~;若采用Best HA组合规则，则需要依据（10）进行枚举求解，对应（ii）的情形。以节点1-1到节点1-5的最短路径为例，因为二者同属一个下层网络，因此步骤二中所求的最短路径即为节点1-1到节点1-5的近似最短路径，和（i）、（iii）属于同一情形。

图4-1 大规模最短路径近似算法

4.3 Time_Dependent Shortest Path Problems（时变最短路问题）

在交通领域，考虑时间因素的最短路问题是研究的热点，这类问题我们称为"Dynamic Shortest Path Problems"。这类问题具有广泛应用，如街道网络交通优化、实时智能交通系统设计等。这类问题通常具有以下特征：对于给定的有向网络，网络中的每条弧都与一个旅行时间（延迟）相关联，它表示如果在时刻从节点沿着弧出发，将会在时刻达到节点；此外，网络中的每条弧还与成本相关联，也就是说时刻从节点沿着弧出发，达到节点时花费的成本为；对于某些问题来说，如果在节点发生等待（由于某些原因需要在节点进行停留，如在转运节点进行必要的装卸作业产生的等待），则还需要考虑在对应节点处的等待费用。

这里以文献[8-9]中的例子对时变最短路问题的特点进行简要说明。如图4-2，弧（3,4）的长度为1的概率为0.1，为101的概率为0.9，可以认为弧（3，4）的状态是隐含的关于时间的函数。当我们在求解从节点1到节点4的最短路径时无法直接采用前边介绍的任何一种算法。该问题的解是由一些离散的值构成的，如：

1-2-3-4, cost=3, Pr=0.1;

1-2-3-4, cost=103, Pr=0.9;

1-2-3-1-2-3-4, cost=6, Pr=0.09;

1-2-3-1-2-3-4, cost=106,Pr=0.81;

....

我们可以计算出期望的最短路长度

图4-2 弧长不确定的有向网络

从上述例子我们可以总结出时变最短路问题的特点：在求解此类最短路径时每访问一次某些节点（如图4-2节点3）就需要根据现有信息重新估计后续路径、最短路径中可能有环的存在等等

由于时变最短路问题较为复杂性，因此我们需要根据具体问题性质，如旅行时间（延迟）和时间成本的函数性质（离散函数、连续函数）、在网络节点发生等待的概率（不发生等待、每个节点都发生等待、只有部分节点发生等待）、从源节点出发时间的选择（固定时刻出发、不考虑出发时间、在任意可能时刻出发）以及具体问题类型来建立数学模型并设计算法求解。

一般可将时变最短路问题分为以下具体经典问题：

（1）Minimum time for a specific departure time

在给定网络源节点，出发时刻的条件下找出从源节点到达其他非源节点的最早达到时间。

（2）Minimum time for all departure times

在给定网络源节点的条件下找出任意时刻从源节点出发时，到达其他非源节点的最小成本路径。

（3）Time windows

网络中的每个节点都与一个时间窗口[]相关联，并且只能在该时间窗口内到达该节点和离开该节点。有时候，问题也允许到达节点的时刻早于，并等待至时刻。求从源节点到达其他非源节点的最早达到时间。

关于Dynamic Shortest Path Problems的具体内容读者可以参考相关文献[10-11]学习，这里不再深入研究。

4.4 基于ADMM框架的VRP问题求解

在VRP问题的精确算法中，学者们通常使用不同的算法框架对问题进行分解，如：分支定价(Branch and Price)、分支切割定价（Branch and Cut and Price）、拉格朗日分解（Lagrangian Decomposition）和交替方向乘子法（Alternating direction method of multipliers, ADMM）等。然而，这些方法分解得到的子问题最终都指向了一类问题，那就是Elementary Resource Constrained Shortest Path Problem (ESPPRC)。本文所介绍的Label Correcting Algorithm可以有效解决此类问题。接下来，本节简要介绍ADMM的框架以及Label Correcting Algorithm 在其中的应用。有兴趣的读者可以通过文献[2]了解等多信息。

表4-1 ADMM算法框架