在网络 世界中，有模型可以解释各种应用中的观察结果。这些包括简单的任务，例如计算最短路径，这在路由网络中具有明显的应用，但也适用于生物学，例如，黏菌绒泡菌能够在迷宫中找到最短路径。另一个例子是布雷斯悖论——观察到向网络添加资源可能会产生与预期相反的效果——这不仅体现在道路网络中，也体现在机械和电气系统中。例如，修建新道路会增加交通拥堵，或者在电路中增加新链接会增加电压。电路和其他类型网络之间的这种连接已被用于各种任务，如分区网络和路由流。
在获得SIGSPATIAL 2021最佳论文奖的 “使用电流进行稳健路由”中，我们介绍了电流在道路网络路由背景下的另一个有趣应用。具体来说，我们利用电流的思想来解决在给定源和目的地之间构建多条替代路线的问题。替代路线对于许多用例都很重要，包括找到最符合用户偏好的路线和稳健路由，例如，保证在交通拥堵的情况下找到一条好路的路线。在此过程中，我们还描述了如何快速对道路网络上的电流进行建模。
现有的替代路由方法
计算道路网络上的替代路线是一个相对较新的研究领域，大多数技术依赖于两个主要模板之一：惩罚法和平台法。在前者中，通过运行最短路径算法迭代计算替代路线，然后在后续运行中对已包含在已计算的最短路径中的那些路段添加惩罚，以鼓励进一步探索。在后者中，同时构建两个最短路径树，一个从原点开始，一个从目的地开始，用于识别两棵树共有的道路段序列。然后将每个这样的共同序列（例如，预计是重要的主干道）视为从原点到目的地途中的访问点，从而可能产生替代路线。众所周知，惩罚法可以产生高质量的结果（即返回的替代路线集的平均旅行时间、多样性和稳健性），但在实践中非常慢，而平台法速度要快得多，但产生的解决方案质量较低。
替代路由的替代方案：电流
我们的方法有所不同，我们假设道路网络上的路由问题在很多方面类似于电流通过电阻网络的流动。虽然电流会流经许多不同的路径，但在其他条件相同的情况下，电阻较高的路径电流较弱，电阻较低的路径电流较强。
我们将道路网络视为一个图，其中交叉点是节点，道路是边。然后，我们的方法将图建模为一个电路，用电阻器替换边，电阻等于道路遍历时间，然后将电池连接到起点和目的地，从而产生这两点之间的电流。在这个类比中，电阻模拟了遍历一段路所耗费的时间。从这个意义上说，长而拥挤的路段具有较高的电阻。直观地说，电流的流动将分散到整个网络中，但集中在电阻较低的路线上，这对应于更快的路线。通过确定电流的主要路线，我们可以构建一组从起点到目的地的可行替代路线。
我们如何构建与道路网络相对应的电路的示例。电流可以分解为三个流，i 1、i 2和i 3；每个流都对应于从弗里蒙特到圣拉斐尔的一条可行替代路径。
为了计算电流，我们使用了基尔霍夫定律和欧姆定律，它们分别规定：1）每个交叉路口的电流代数和等于零，这意味着进入任何交叉路口的车辆也会离开该交叉路口（例如，如果三辆汽车从一条街道进入交叉路口，另一辆汽车从另一条街道进入同一个交叉路口，则总共需要四辆汽车离开交叉路口）；2）电流与端点之间的电压差成正比。如果我们写下得到的方程，我们最终会得到一个线性系统，其中包含n 个方程和n 个变量，这些变量对应于每个交叉路口的电位（即电压）。虽然电压与道路网络没有直接的类比，但它可以用来帮助计算电流的流动，从而找到如上所述的替代路线。
为了找到每根电线上的电流i（或流量），我们可以使用基尔霍夫定律和欧姆定律来获得关于电压（或电位）v的线性方程组。这会产生一个包含三个方程（代表基尔霍夫定律）和三个未知数（每个交叉点的电压）的线性系统。
因此，计算归结为计算此线性系统的变量值，涉及一个非常特殊的矩阵，称为拉普拉斯矩阵。此类矩阵具有许多有用的特性，例如，它们是对称且稀疏的——非对角非零项的数量等于边数的两倍。尽管目前有许多针对此类线性方程组的近线性时间求解器，但它们对于快速响应低延迟的路由请求而言仍然太慢。因此，我们设计了一种新算法，可以更快地解决这些线性系统，以应对道路网络1的特殊情况。
快速电流计算
这种新算法的第一个关键部分涉及高斯消元法，这可能是解决线性系统最著名的方法。当对与某些电阻网络相对应的拉普拉斯矩阵执行时，它对应于Y-Δ 变换，这会减少节点数，同时保持电压不变。唯一的缺点是边数可能会增加，这会使线性系统的求解速度更慢。例如，如果使用 Y-Δ 变换消除具有 10 个连接的节点，系统最终将有 35 个新连接！
Y-Δ 变换允许我们移除中间的连接点，并将其替换为N 1、N 2和N 3之间的三个连接（ R a、R b和R c ） 。（图片来自维基百科）
然而，如果可以识别出网络中通过极少节点与其余部分相连的部分（我们称这些连接为瓶颈），并在保留瓶颈节点的同时消除其他所有节点，那么最后形成的新边将只位于瓶颈节点之间。假设瓶颈节点的数量远小于用 Y-Δ 消除的节点数量 — — 对于道路网络而言确实如此，因为瓶颈节点（如桥梁和隧道）比普通交叉路口少见得多 — — 这将导致图形大小大幅净减少（例如，~100 倍）。幸运的是，通过对这样的网络进行分区，可以轻松识别道路网络中的此类瓶颈。通过对瓶颈2以外的所有节点应用 Y-Δ 变换，可以得到一个小得多的图形，从而可以更快地求解电压。
但是如何计算网络中非瓶颈节点的其余部分的电流呢？电流的一个有用特性是，一旦知道瓶颈节点的电压，就可以轻松计算网络其余部分的电流。网络某一部分内的电流仅取决于将该部分与网络其余部分分隔开的瓶颈节点的电压。事实上，可以预先计算一个小矩阵，这样就可以通过单个矩阵向量乘法恢复电流，这是一个可以并行运行的非常快的运算。
考虑斯塔顿岛上强加的概念道路网络（左），直接计算电流会很慢。桥梁（红色节点）是瓶颈点，我们可以通过反复应用高斯消去法（或 Y-Δ 变换）来消除岛内的整个道路网络。生成的网络（中）是一个小得多的图，可以更快地进行计算。消除部分内的电位始终是瓶颈节点的固定线性组合（右）。
一旦我们获得了给出模型网络中电流的解决方案，我们就可以观察承载最高电流量的路线并将其输出为道路网络的替代路线。
结果
以下是描述上述算法计算出的替代方案的一些结果。
为湾区找到了不同的替代方案。不同的颜色对应从出发地（底部的红色图标）到目的地（顶部的蓝色图标）的不同路线。
结论
在这篇文章中，我们描述了一种计算道路网络中替代路线的新方法。我们的方法与该领域数十年来研究中应用的主要技术有着根本的不同，通过从电路的角度研究问题，提供了道路网络中的高质量替代路线。这种方法在实际系统中非常有用，我们希望能够激发在替代路线计算和相关问题领域进行更多研究。感兴趣的读者可以在我们的 SIGSPATIAL 2021演讲录音中找到有关这项工作的更详细讨论。
致谢
我们感谢来自 Google Research 的合作者 Lisa Fawcett、Sreenivas Gollapudi、Ravi Kumar、Andrew Tomkins 和 Ameya Velingker。
评论