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

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

但是怎样才能(快得多)呢?

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

有启发式解决方案，也有精确解决方案，将图(路网)分层组织，两者都有优缺点，主要解决速度和RAM问题。我在这个回答中列出了其中的一些。

对于GraphHopper，我决定使用收缩层次结构，因为它相对“容易”实现，并且不需要花时间来准备图表。它仍然会导致非常快的响应时间，就像你可以在我们的在线实例GraphHopper Maps上测试一样。例如，从南非到中国东部，距离23000公里，汽车行驶时间近14天，在服务器上只需要0.1秒。

像Dijkstra算法这样的图算法将无法工作，因为图是巨大的。

这个论点并不一定成立，因为Dijkstra通常不会查看完整的图，而只是一个非常小的子集(图的互联性越好，这个子集就越小)。

对于行为良好的图，Dijkstra实际上可能表现得相当好。另一方面，通过仔细的参数化，A*总是表现得一样好，甚至更好。您是否已经尝试过它对数据的处理方式?

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

我已经在路由方面工作了几年，最近由于客户的需求而引起了大量的活动，我发现a *很容易就足够快了;真的没有必要去寻找优化或更复杂的算法。在一个巨大的图上路由不是问题。

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

The other important thing is to be able to re-use the network for as many routing calculations as you like. If your algorithm has marked the nodes in some way to record the best route (total cost to current node, and best arc to it) - as it has to in A* - you have to reset or clear out this old information. Rather than going through hundreds of thousands of nodes, it's easier to use a generation number system. Mark each node with the generation number of its data; increment the generation number when you calculate a new route; any node with an older generation number is stale and its information can be ignored.

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

然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括为他们的卡车车队提供调度和路由应用程序。然而，我们对路线的标准远比建筑、交通减速或车道封闭的地方更具体。

我们采用了一种称为ACO(蚁群优化)的技术来调度和路线卡车。该技术是一种人工智能技术，应用于旅行推销员问题来解决路由问题。ACO的技巧是基于路由的已知事实构建错误计算，以便图求解模型知道何时退出(当错误足够小时)。

你可以谷歌ACO或TSP找到更多关于这个技术。然而，我没有使用过任何开源AI工具，所以不能推荐一个(尽管我听说SWARM非常全面)。

事实上，我已经做过很多次了，尝试了几种不同的方法。根据地图的大小(地理位置)，您可能会考虑使用haversine函数作为启发式方法。

我的最佳解决方案是使用带有直线距离的A*作为启发式函数。但接下来你需要地图上每个点(交集或顶点)的某种坐标。您还可以为启发式函数尝试不同的权重，即。

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

k是一个大于0的常数。

Probably similar to the answer on pre-computed routes between major locations and layered maps, but my understanding is that in games, to speed up A*, you have a map that is very coarse for macro navigation, and a fine-grained map for navigation to the boundary of macro directions. So you have 2 small paths to calculate, and hence your search space is much much smaller than simply doing a single path to the destination. And if you're in the business of doing this a lot, you'd have a lot of that data pre-computed so at least part of the search is a search for pre-computed data, rather than a search for a path.