algorithm - 什么算法计算地图上从 A 点到 B 点的方向？

Question

地图提供商（例如 Google 或 Yahoo! Maps）如何建议路线？

我的意思是，他们可能有某种形式的真实世界数据，当然包括距离，也可能包括行驶速度、人行道的存在、火车时刻表等。但假设数据采用更简单的格式，比如一个非常大的有向图边缘权重反映距离。我希望能够快速计算从一个任意点到另一点的方向。有时这些点会靠近（在一个城市内），而有时它们会相距很远（越野）。

像 Dijkstra 算法这样的图算法将不起作用，因为图是巨大的。幸运的是，像 A* 这样的启发式算法可能会起作用。但是，我们的数据非常结构化，也许某种分层方法可能有效？（例如，存储相距较远的某些“关键”点之间的预先计算的方向，以及一些局部方向。那么两个远点的方向将涉及到一个关键点的局部方向，到另一个关键点的全局方向，然后是局部方向再次指示。）

在实践中实际使用了哪些算法？

PS。这个问题的动机是发现在线地图方向的怪癖。与三角不等式相反，有时谷歌地图认为XZ比在 XYZ中使用中间点需要更长的时间和更远的距离。但也许他们的步行方向也针对另一个参数进行了优化？

聚苯乙烯。这是对三角不等式的另一个违反，这表明（对我而言）他们使用某种分层方法：XZ与XYZ。前者似乎使用了著名的 Boulevard de Sebastopol，尽管它有点偏僻。

编辑：这些示例似乎都不再有效，但在原始帖子发布时都有效。

score 539 · Accepted Answer

作为一个在地图公司工作了 18 个月的人，其中包括研究路由算法……是的，Dijkstra确实有效，但有一些修改：

不是从源头到目的地做一次Dijkstra，而是从每一端开始，然后扩展两边，直到它们在中间相遇。这消除了大约一半的工作（2*pi*(r/2)^2 vs pi*r^2）。
为避免探索源和目的地之间每个城市的小巷，您可以拥有多个地图数据图层：仅包含高速公路的“高速公路”图层，仅包含次要街道的“次要”图层，等等。然后，您只探索更详细层的较小部分，并根据需要进行扩展。显然，这个描述遗漏了很多细节，但你明白了。

通过按照这些方式进行修改，您甚至可以在非常合理的时间范围内进行跨国路由。

score 114 · Accepted Answer

这个问题在过去几年一直是一个活跃的研究领域。主要思想是对图进行一次预处理，以加快所有后续查询。有了这些附加信息，可以非常快速地计算行程。尽管如此，Dijkstra 算法仍然是所有优化的基础。

Arachnid描述了基于分层信息的双向搜索和边缘修剪的用法。这些加速技术工作得很好，但最新的算法无论如何都优于这些技术。使用当前算法，可以在大陆道路网络上以不到一毫秒的时间计算出最短路径。Dijkstra 未修改算法的快速实现大约需要10 秒。

《Engineering Fast Route Planning Algorithms 》一文概述了该领域的研究进展。有关详细信息，请参阅该论文的参考资料。

已知最快的算法不使用数据中关于道路分层状态的信息，即它是高速公路还是地方道路。相反，他们在预处理步骤中计算自己的层次结构，该层次结构经过优化以加快路线规划。然后可以使用此预计算来修剪搜索：在 Dijkstra 算法期间，不需要考虑远离起点和目的地的慢速道路。好处是非常好的性能和结果的正确性保证。

第一个优化的路线规划算法只处理静态道路网络，这意味着图中的一条边具有固定的成本值。这在实践中并非如此，因为我们想要考虑交通拥堵或车辆相关限制等动态信息。最新的算法也可以处理此类问题，但仍有问题需要解决，研究仍在进行中。

如果您需要最短路径距离来计算TSP的解决方案，那么您可能对包含源和目的地之间所有距离的矩阵感兴趣。为此，您可以考虑使用 Highway Hierarchies 计算多对多最短路径。请注意，在过去 2 年中，这种情况已通过更新的方法得到改善。

score 19 · Accepted Answer

只是解决违反三角不等式的问题，希望他们优化的额外因素是常识。您不一定想要最短或最快的路线，因为它可能导致混乱和破坏。如果您希望您的方向更喜欢卡车友好的主要路线，并且可以应对每个卫星导航跟随的司机发送它们，您很快就会放弃三角不等式[1]。

如果 Y 是 X 和 Z 之间的一条狭窄住宅街道，您可能只想在用户明确要求 XYZ 时使用通过 Y 的快捷方式。如果他们要求 XZ，他们应该坚持主要道路，即使它有点远并且需要更长的时间。这类似于Braess 悖论——如果每个人都试图走最短、最快的路线，那么由此产生的拥堵意味着它不再是任何人最快的路线。从这里我们从图论转向博弈论。

[1] 事实上，当您允许单向道路并失去对称性要求时，任何希望产生的距离将是数学意义上的距离函数的希望都会消失。失去三角不等式也只是在伤口上撒盐。

score 15 · Accepted Answer

以下是世界上最快的路由算法比较和正确性证明：

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

这是关于该主题的谷歌技术讲座：

http://www.youtube.com/watch?v=-0ErpE8tQbw

这是 schultes 讨论的高速公路层次算法的实现（目前仅在柏林，我正在编写界面，并且正在开发移动版本）：

http://tom.mapsforge.org/

score 9 · Accepted Answer

我以前没有在谷歌、微软或雅虎地图上工作过，所以我不能告诉你它们是如何工作的。

然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括他们的卡车车队的调度和路由应用程序。然而，我们的路线标准远比施工或交通放缓或车道关闭的地方更具业务针对性。

我们采用了一种称为 ACO（蚁群优化）的技术来安排和安排卡车路线。该技术是一种人工智能技术，应用于旅行商问题以解决路由问题。ACO 的诀窍是根据路由的已知事实构建错误计算，以便图形求解模型知道何时退出（何时错误足够小）。

您可以在谷歌 ACO 或 TSP 上找到有关此技术的更多信息。但是，我没有为此使用任何开源 AI 工具，因此无法推荐一个（尽管我听说 SWARM 非常全面）。

score 9 · Accepted Answer

就静态道路网络的查询时间而言，当前最先进的技术是 Abraham 等人提出的 Hub 标记算法。http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20。最近以 Microsoft 技术报告http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf的形式发布了对该领域的全面且出色的书面调查。

短版是...

Hub 标记算法为静态道路网络提供了最快的查询，但需要大量 ram 才能运行 (18 GiB)。

中转节点路由稍微慢一些，但它只需要大约 2 GiB 的内存并且具有更快的预处理时间。

收缩层次结构在快速预处理时间、低空间要求 (0.4 GiB) 和快速查询时间之间提供了很好的折衷。

没有一种算法是完全主宰...

彼得桑德斯的这个谷歌技术演讲可能会引起人们的兴趣

https://www.youtube.com/watch?v=-0ErpE8tQbw

还有安德鲁·戈德堡的这个演讲

https://www.youtube.com/watch?v=WPrkc78XLhw

可从 KIT 的 Peter Sanders 研究小组网站获得收缩层次结构的开源实现。http://algo2.iti.kit.edu/english/routeplanning.php

还有一篇由微软撰写的关于 CRP 算法使用情况的易于访问的博客文章... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/

score 8 · Accepted Answer

像 Dijkstra 算法这样的图算法将不起作用，因为图是巨大的。

这个论点不一定成立，因为 Dijkstra 通常不会查看完整的图，而只会查看一个非常小的子集（图的互连越好，这个子集越小）。

Dijkstra 实际上对于表现良好的图可能表现得相当好。另一方面，经过仔细的参数化，A* 将始终表现得一样好，或者更好。您是否已经尝试过它将如何处理您的数据？

也就是说，我也很想听听其他人的经历。当然，像谷歌地图搜索这样的突出例子特别有趣。我可以想象类似有向最近邻启发式的东西。

score 7 · Accepted Answer

我有点惊讶地没有看到这里提到的 Floyd Warshall 的算法。该算法的工作原理与 Dijkstra 的非常相似。它还有一个非常好的功能，即只要您想继续允许更多中间顶点，它就允许您进行计算。所以它自然会很快找到使用州际公路或高速公路的路线。

score 6 · Accepted Answer

实际上，我已经这样做了很多次，尝试了几种不同的方法。根据地图的大小（地理），您可能需要考虑使用 hasrsine 函数作为启发式方法。

我做出的最佳解决方案是使用具有直线距离的 A* 作为启发式函数。但是，您需要为地图上的每个点（交点或顶点）提供某种坐标。您还可以为启发式函数尝试不同的权重，即

f(n) = k*h(n) + g(n)

其中 k 是某个大于 0 的常数。

score 4 · Accepted Answer

可能类似于主要位置和分层地图之间预先计算的路线的答案，但我的理解是，在游戏中，为了加速 A*，你有一个非常粗略的宏观导航地图，以及一个细粒度的地图导航到宏观方向的边界。所以你有 2 条小路径要计算，因此你的搜索空间比简单地做一条到目的地的路径要小得多。如果你经常做这件事，你会有很多预先计算的数据，所以至少部分搜索是搜索预先计算的数据，而不是搜索路径。

score 3 · Accepted Answer

这纯粹是我的猜测，但我想他们可能会使用覆盖有向图的影响图数据结构来缩小搜索范围。这将允许搜索算法在所需行程较长时将路径指向主要路线。

鉴于这是一个 Google 应用程序，我们也可以合理地假设很多魔法都是通过大量缓存完成的。:) 如果缓存前 5% 最常见的 Google Map 路线请求允许通过简单查找来回答大部分请求（20%？50%？），我不会感到惊讶。

score 3 · Accepted Answer

我对此有更多的想法：

1) 请记住，地图代表一个物理组织。存储每个交叉点的纬度/经度。除了目标方向上的点之外，您不需要检查太多。只有当你发现自己被封锁时，你才需要超越这一点。如果您存储高级连接的叠加层，则可以对其进行更多限制-通常您永远不会以远离最终目的地的方式遇到其中一个。

2）将世界划分为由有限连接定义的一大堆区域，定义区域之间的所有连接点。查找您的源和目标所在的区域，从您的位置到每个连接点的起始和结束区域路线，对于连接点之间的简单映射之间的区域。（我怀疑很多后者已经预先计算过了。）

请注意，区域可以小于大都市区。任何具有将其划分的地形特征（例如河流）的城市都将是多个区域。

score 3 · Accepted Answer

我对所使用的启发式方法非常好奇，不久前我们得到了从圣罗莎附近的同一个起点到优胜美地国家公园的两个不同露营地的路线。这些不同的目的地产生了截然不同的路线（通过 I-580 或 CA-12），尽管这两条路线在最后 100 英里（沿 CA-120）汇合，然后在最后再次分叉了几英里。这是相当可重复的。这两条路线相距最多 50 英里，大约 100 英里，但距离/时间非常接近，如您所料。

唉，我无法重现 - 算法一定已经改变了。但这让我对算法感到好奇。我所能推测的是，有一些定向修剪恰好对从远处看到的目的地之间的微小角度差异非常敏感，或者通过选择最终目的地选择了不同的预计算段。

score 3 · Accepted Answer

说到GraphHopper，一个基于 OpenStreetMap 的快速开源路线规划器，我阅读了一些文献并实现了一些方法。最简单的解决方案是 Dijkstra，一个简单的改进是双向 Dijkstra，它大约只探索一半的节点。使用双向 Dijkstra 穿越整个德国的路线已经需要 1 秒（对于汽车模式），在 C 语言中可能只有 0.5 秒左右；）

我在这里创建了一个带有双向 Dijkstra 的真实路径搜索的动画 gif 。还有一些让 Dijkstra 更快的想法，比如做 A*，这是一个“面向目标的 Dijkstra”。我还为它创建了一个gif 动画。

但是如何（很多）更快地做到这一点？

问题是，对于路径搜索，必须探索位置之间的所有节点，这确实非常昂贵，因为在德国已经有数百万个节点。但 Dijkstra 等的另一个痛点是此类搜索使用大量 RAM。

有启发式解决方案，也有将图形（道路网络）组织在层次结构中的精确解决方案，两者都有优缺点，主要解决速度和 RAM 问题。我在这个答案中列出了其中一些。

对于 GraphHopper，我决定使用Contraction Hierarchies，因为它相对“容易”实现并且不需要很长时间来准备图表。它仍然会产生非常快的响应时间，就像您可以在我们的在线实例GraphHopper Maps上进行测试一样。例如，从南非到中国东部，这导致了 23000 公里的距离和近 14 天的汽车驾驶时间，并且在服务器上仅花费了 ~0.1 秒。

score 2 · Accepted Answer

我从事路由工作已有几年了，最近由于客户的需求引起了活动的爆发，我发现 A* 很容易就足够快了；确实没有必要寻找优化或更复杂的算法。在巨大的图表上进行路由不是问题。

但是速度取决于整个路由网络，我的意思是弧和节点的有向图，分别代表路线段和路口，在内存中。主要的时间开销是创建这个网络所花费的时间。一些基于运行 Windows 的普通笔记本电脑的粗略数据，并在整个西班牙进行路由：创建网络所需的时间：10-15 秒；计算路线所需的时间：太短而无法测量。

另一件重要的事情是能够重用网络进行尽可能多的路由计算。如果您的算法以某种方式标记了节点以记录最佳路线（到当前节点的总成本，以及到它的最佳弧线） - 正如它在 A* 中所必须的那样 - 您必须重置或清除这些旧信息。与其通过数十万个节点，使用代号系统更容易。用数据的代号标记每个节点；计算新路线时增加世代编号；任何具有较老代号的节点都是陈旧的，可以忽略其信息。

score 1 · Accepted Answer

我看到了 OP 中的地图是怎么回事：

查看指定中间点的路线：由于那条路不直，路线稍微向后退。

如果他们的算法不会回溯，它就不会看到更短的路线。

score 0 · Accepted Answer

全对最短路径算法将计算图中所有顶点之间的最短路径。这将允许预先计算路径，而不是每次有人想要找到源和目的地之间的最短路径时都需要计算路径。Floyd-Warshall 算法是一种全对最短路径算法。

score -4 · Accepted Answer

地图从不考虑整个地图。我的猜测是：- 1. 根据您的位置，他们加载一个地方和那个地方的地标。2.当你搜索目的地时，他们加载地图的另一部分并用两个地方制作一个图表，然后应用最短路径算法。

此外，还有一种重要的技术动态编程，我怀疑它被用于计算最短路径。你也可以参考一下。

algorithm - 什么算法计算地图上从 A 点到 B 点的方向？

18 回答 18

Related

Reference