道路网的高效分区

2021 年 11 月 22 日 TensorFlow

发布人：Google Research 高级研究员 Ali Kemal Sinop 和 Google 地图高级软件工程师 Mahmuda Ahmed

基于传统算法的设计技巧近来在几个大规模问题的解决方案创新上显现出了效用，这些问题包括旅行路线和路线选择难题。例如，Dijkstra 算法 (Dijkstra's algorithm) 经常被用于求出计算图 (Graphs) 上的路线，但是当路线超出一个小镇的范围时，计算规模可能会迅速扩大。而如果将道路网“分区”，可以有效减少在计算时对计算图的搜索范围，由此极大提升算法的速度。

旅行路线
https://ai.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html

本文将介绍我们如何运用传统算法设计道路网的计算图分区算法 (Graph partitioning algorithm)。其中部分算法已在 WWW 2021 的“应用于道路网中近似最短路径的基于草图的算法 (Sketch-based Algorithms for Approximate Shortest Paths in Road Networks) ”一文中有所介绍。

WWW 2021
https://www2021.thewebconf.org/
应用于道路网中近似最短路径的基于草图的算法
https://www.youtube.com/watch?v=9SSqPbdq_cg

随机游走 (Random walks) 是一个经典概念，其通过大幅度缩小网络规模来帮助计算最短路径 （尽管这听起来有点反常）。借助这种概念，我们的算法可以将北美大陆整个道路网进行高质量分区。并且在输出结果质量类似的情况下，计算速度相较其他分区算法快了一个数量级^[1]。

使用计算图建立道路网模型

我们都知道，道路网和计算图 (Graphs) 之间存在对应关系，并且这种关系非常有用。这种对应关系表现为道路交叉处变为节点，而道路变为边缘。

图源：维基百科 Seven Bridges of Königsberg

若想理解分区能为路线选择带来什么好处，可以从Dijkstra 算法入手，这是一种利用广度优先搜索 (Breadth-first search) 的算法，也是最为知名的查找最快路线的解决方案。Dijkstra 算法从起点开始执行穷举搜索，直至找到目的地。因此，如果起点与目的地之间的距离变长，计算速度也会慢一个数量级。例如，相较于计算华盛顿州西雅图到加利福尼亚州旧金山的路线，计算在西雅图内移动的路线时速度更快。并且，即使是计算市内路线，Dijkstra 算法搜索的空间穷举量也会导致秒级的不必要延迟。然而，通过识别内部连接较多、而与外部连接较少的地区 （例如纽约州斯塔滕岛），就可以将计算分为多个较小的区块。

整个纽约州斯塔滕岛的路线选择问题

以计算图显示的对应分区

蓝色节点表示进出斯塔滕岛的唯一入口/出口

设想一下，由以上计算图中的 A 点开车前往 B 点。决定要从哪里进入斯塔滕岛（奥特尔大桥 Outerbridge 或者戈瑟尔斯大桥 Goethals Bridge），以及从哪里出来（韦拉札诺大桥 Verrazzano）之后，这个问题就可以进一步划分为三段车程：开往入口、开往出口以及通过最佳路线选择开往目的地。这意味着，路线选择算法在导航 A 点至 B 点的路线时，只需要考虑这些特殊点（信标），因此可以更加快速地找到最短的准确路线。

需要注意的是，只有在数量不算太多的情况下，信标才有用。信标数量越少，需要添加的快捷路线就越少，搜索的范围也越小，所以计算速度就越快。因此，对于一定数量的组件（即道路网的特定区域），信标的数量应该相对较少，这样的分区才能称为好分区。

正如斯塔滕岛示例所显示的情况一样，真实的道路网会有许多信标（特殊点，例如桥梁、隧道或者山口），这会导致一些地区的交通非常发达（例如，拥有大型街道网格），而其他地区的交通则不太便利（例如，一座岛上只有几座桥梁作为进出通道）。这个问题就变成了如何高效地定义组件以及识别连接道路网的最少数量的信标。

我们的分区算法

鉴于两个组件之间的每个连接点都可能成为一个信标，我们在划分道路网时最大限度减少了组件之间的连接点数量，从而确保信标数量不会过多。

为此，我们首先将道路网划分为两个均衡（即拥有同等大小）的组件，同时最大限度地减少连接这两个组件的道路数量，这么做确保了每个组件中的信标与道路比率都较小。之后，算法每次都将道路网一分为二，如此重复，直至所有组件达到所需的大小（以内部道路数量作为考量依据），生成有用的多组件分区。

在这里我们需要特别注意组件大小。如果组件太小，就会产生过多信标；而如果组件太大，则只适合长途路线。因此，我们将组件大小留作输入参数，待算法完成时通过实验确定。

现有的分区架构有很多种，例如 METIS（适用于一般类别的网络）、PUNCH 和 Inertial Flow，后两个架构比较适合道路网类别的网络。我们的解决方案基于 Inertial Flow 算法，并且性能得到增强，无论是小城市还是整个大陆，都能高效运行。

PUNCH
https://www.microsoft.com/en-us/research/publication/graph-partitioning-with-natural-cuts/
Inertial Flow
http://www.sommer.jp/roadseparator.htm

道路网的均衡分区

上文提及将以计算图表示的道路网划分为两个均衡组件，这种做法该如何实现？首先将紧密连接的节点分为一组，以缩小计算图，这样可以加快以下双向分区阶段的速度。在这里，随机游走 (Random walk) 将派上用场。

随机游走理论具备众多有用的特性，这也是人们将其用于研究森林中蚊子的运动、热传导等各种问题的原因。而在这些特性中，对我们的应用而言最重要的就是，在内部交通发达但与外部的交通不便的地区，随机游走很容易被“困住”。设想一下，在斯塔滕岛的街道上执行固定步数的随机游走：由于出岛的道路相对较少，大部分的步数都是在岛内执行，且出岛的概率较低。

随机游走的图示。将蓝色的计算图设想为斯塔滕岛的道路网。以中间点作为起点，执行了 50 个随机游走。每个随机游走连走 10 步，或者直至走出整个岛为止。每个节点的数字表示随机游走经过该节点的次数。最终，随机游走经过岛内任意节点的次数都远超经过岛外节点的次数

这些小组件是高度联系的节点。找到这些组件之后，节点聚集在一起（如上述斯塔滕岛示例所示），算法会将聚集的节点压缩为一个新的单一节点。

找到聚集的节点（中图），然后将其合并为单一的“超级”节点（右图），以缩小原始计算图（左图）的大小。此处图示为手动选取，从而更好地说明算法的剩余内容

算法的最后一步就是将这个较小的计算图分为两个分区，然后优化分区，以应用于道路网的原始计算图。如此一来就最大限度地缩小了信标（即相交的边缘）和节点的比率，计算图也变得更小。然后，我们使用 Inertial Flow算法查找计算图中的交点。

Inertial Flow 算法
http://www.sommer.jp/roadseparator.htm

算法对不同方向作出评估。针对每个方向，我们找出能使前 10% 与后 10% 节点的边缘交点（例如信标）数量最少的部分

发现小计算图上的交点之后，算法执行优化步骤，将交点投射回道路网的原始计算图。

结论

这项工作表明，传统算法为解决大规模问题提供了许多有用的工具。我们可以使用计算图分区将大规模计算图问题分解为较小的子问题，然后分别处理并同步解决。这种分区算法在 Google 地图中有充分的体现，其在计算路线方面非常高效。

致谢

感谢我们的协作者，其中包括 Google Research 团队的 Lisa Fawcett、Sreenivas Gollapudi、Kostas Kollias、Ravi Kumar、Andrew Tomkins、Ameya Velingker 以及 Google 地图团队的 Pablo Beltran、Geoff Hulten、Steve Jackson 和 Du Nguyen。

[1] 此项技术可应用于任意网络结构，例如脑神经元网络结构。