8

我最近一直在玩OSRM路由库。它似乎在解决最短路径问题方面非常有效。但是，我没有看到如何用它计算单源最短路径。更准确地说，给定一个固定起点，计算在给定距离限制内（例如，30 分钟内可到达）到所有位置的最短距离。

OSRM 在内部使用收缩层次结构。据我了解，在计算现实世界数据中两个位置之间的距离时，这种技术要优于 Dijkstra 算法。但是，对于我的问题，Dijkstra 的算法似乎更适合，不是吗？

OSRM 是否提供 API 来计算单源最短路径问题（有距离限制）？还有其他更适合此类问题的免费路由库吗？最好是对 OpenStreetMap 数据有良好支持的一种。

4

1 回答 1

9

OSRM 正在使用收缩层次结构 (CH) 来快速实现“一对一路由”。要使 CH 正常工作，您需要一种适应的双向算法（A*、Dijkstra、...），因此单源情况更加困难。但是，如果您事先知道您想要哪些目的地，那么一对多算法相对简单。

如果您想要使用查找表的“非目标导向的双向搜索”的解决方案，还可以查看论文“ Fast Detour Computation for Ride Sharing ”或此处。

其他免费路由库？

我会建议我的 Java GraphHopper 项目；）

但当然还有更多：http ://wiki.openstreetmap.org/wiki/Routing

于 2013-01-05T17:52:18.143 回答