同时， ，根据他们的文档，Spatialite和PgRouting仅提供Dijkstra和A *算法。我什至没有看到双向搜索，据我的经验，它可以节省两次计算时间。
是否有更好的数据库或其他应用程序算法？
#1 楼
事实是，大多数人都使用A *算法的自定义变体。您会在大多数“大佬”中看到这一点（我不能说他们在公共论坛上是谁，但是我可以告诉您您可能使用了其中的一个-保证），其中启发式的修改是非常依赖于他们使用的数据集。您已经提到过灌浆，我认为这是“传统”的选择。这对于执行简单的路由算法和大多数问题非常有用。它也易于使用，并且在后端使用传统数据库。
但是，这实际上取决于您要解决的问题的规模和类型，而布线是一个图形问题。与它们的图相关的许多数据（例如，交通数据，公交路线，人行道）会影响路由算法。这些被称为多模式旅行计划者（在这里，您还可以选择“模式”的计划-没有自行车道-只有公共交通-这种事情）。您可以考虑如何将旅行计划也变成一个时间敏感的问题（即，如果您向后走几圈，您将能够搭乘地铁，将您带到目的地的速度比您尝试向前导航的速度快得多使用最低的费用）。
“大佬”本身并不将数据存储在传统数据库中，而是使用预先计算的图形（欢迎使用hadoop / mapreduce集群！）。可以想象，这些图非常大，因此知道如何连接相邻图的边缘可能是一个挑战。无论如何，我建议您看一下一些多模式路由图项目：
Graphserver浮现在脑海。没有太多的文档，但是有很多纯粹的编码功能（AFAIK，我相信MapQuest的某些路由产品会使用此项目的变体）。
另一个选择是OpenTripPlanner，它背后有很多聪明的人（包括来自graphserver的人）。
#2 楼
不确定它是否较新，但pgRouting具有Shooting-star算法：Shooting-Star算法是pgRouting最短路径算法的最新版本。是它从
链接路由到链接，而不是像Dijkstra和A-Star
算法那样从顶点到
顶点。这样就可以为示例定义链接之间的关系，并解决其他一些基于顶点的算法问题，例如与并行链接相同的
源和目标，但成本不同。
ESRI的Network Analyst扩展使用您提到的分层方法来限制求解时间：
全国网络数据集上的最短路径很耗时，这是因为需要搜索大量的边缘。为了提高性能，网络数据集可以在交通系统中对自然层次进行建模，而在州际公路上行驶比在本地道路上行驶更可取。创建了
分层网络后，
修改了双向
Dijkstra用于计算起点和终点之间的路线。 >
ESRI站点上有非常详细的白皮书，其中包含有关此方法的示例-但是需要您登录才能下载（ArcGIS Network Analyst白皮书中的“分层路线”）。
#3 楼
收缩层次结构是一种非常快速的算法：http://algo2.iti.kit.edu/1087.php
该算法在执行时对RAM友好一个查询（要保存一个收缩的图，还需要更多的RAM以及大量的预处理）
还有其他一些算法-包括解决公交路线的算法：
http://i11www.iti.uni-karlsruhe.de/members/thomas_pajor/publications
Microsoft也在做一些研究：
http://research.microsoft.com/zh-cn/people/dadellin/
（嗯，Daniel Delling也是来自卡尔斯鲁厄）
您可以得到一个不错的介绍和可用算法概述：
http://i11www.iti.uni-karlsruhe.de/teaching/sommer2012/routenplanung/index
警告：德语（！）讲座。但是至少标题可以帮助您获取更多信息（ALT，Arc-Flags，CHASE等）或随附的文献！
update
GraphHopper现在实现了收缩层次结构和其他算法，您也可以尝试演示。
评论
您是否已将问题发布到pgRouting用户或开发人员电子邮件列表？您可能会直接从该社区获得更好的响应。用户列表：（lists.osgeo.org/mailman/listinfo/pgrouting-users）开发人员列表：（lists.osgeo.org/mailman/listinfo/pgrouting-dev）+1好问题。我不知道google用于获取路线的算法是什么。相关问题在这里。
由于Google支持Karlsruhe团队（algo2.iti.uni-karlsruhe.de/english/index.php），所以我想他们使用了他们的软件，该软件本质上是开源路由机器。