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

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

下面是谷歌关于这个主题的技术演讲:

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

以下是schultes所讨论的高速公路层次算法的实现(目前仅在柏林，我正在编写界面，移动版本也正在开发中):

http://tom.mapsforge.org/

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.

我对此有了更多的想法:

1)记住地图代表一个实体组织。存储每个交叉口的经纬度。除了目标方向上的点以外，你不需要检查太多。只有当你发现自己受阻时，你才需要超越这一点。如果你储存了大量的高级连接，你就可以进一步限制它们——通常情况下，你永远不会以偏离最终目的地的方式穿过其中任何一个连接。

2)根据有限的连通性将世界划分为一系列区域，定义区域之间的所有连通性点。找出您的源和目标所在的区域，从您的位置到每个连接点的起始和结束区域路由，以及连接点之间的区域映射。(我怀疑后者在很大程度上是事先计算好的。)

请注意，区域可以比大都市区域小。任何具有地形特征的城市(比如一条河)都是多个区域。

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

Arachnid描述了双向搜索和基于层次信息的边缘修剪的用法。这些加速技术工作得很好，但最新的算法在任何方面都优于这些技术。使用目前的算法，在大陆公路网上计算最短路径的时间可大大少于1毫秒。快速实现未修改的Dijkstra算法大约需要10秒。

工程快速路线规划算法概述了该领域的研究进展。有关进一步信息，请参阅那篇论文的参考文献。

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

第一个优化的路线规划算法只处理静态道路网络，这意味着图中的边缘具有固定的成本值。这在实践中是不正确的，因为我们想要考虑交通堵塞或车辆相关限制等动态信息。最新的算法也可以处理这些问题，但仍有问题需要解决，研究还在继续。

如果您需要最短路径距离来计算TSP的解，那么您可能对包含源和目的地之间所有距离的矩阵感兴趣。为此，您可以考虑使用高速公路层次结构计算多对多最短路径。请注意，在过去的两年里，这已经通过更新的方法得到了改进。

我已经在路由方面工作了几年，最近由于客户的需求而引起了大量的活动，我发现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非常全面)。