快速计算城市道路距离的方法

Question

所以我在一个城市中有一组点（比如房子或住宅），我想找到这些点和商店候选点之间的最短距离。我正在寻找最好的商店位置，将距离所有的房子在集合中最小化。因此，我将迭代地移动候选存储点，然后重新计算每个商店和房屋之间的距离（同样使用Djikstra的算法）。由于计算量太大，我不能每次迭代优化算法时都访问数据库。在

我已经使用了很多次pgrouting，这是可行的，但是它太慢了，因为点太多，而且每次都要搜索磁盘。在

有没有一个工具可以让我在内存中加载一些小的开放式街道地图，然后计算内存中的最短路线？我需要一些快速的东西，所以最好用C或python？但任何一种语言只要有效就行。在

Answer 1

这是我的主意。把所有的东西都拿出来。 以最大精度（12）计算所有点（房子和商店）的geohash，并检查任何商店的geohash是否与房子的geohash匹配。如果没有，就用较低的精度（11）计算geohash，然后冲洗并重复，直到找到一个与房子geohash匹配的商店（以后可能会有多个）。在

这是一个模糊距离计算。这将是伟大的工作和最短的处理时间。但是，如果您得到两个或多个具有相同geohash且具有一定精度的存储，则此操作将失败。所以我建议你这样做

1. 精度下降的geohash循环。当商店的geohash与房子的gohash匹配时中断
2. 如果（有多个伤口匹配）进行普通距离计算，找到最近的商店并将其退回
3. 否则返回与geohash匹配的一个存储

你的一个优点是严格的概率要求变为模糊问题。如果你有一处酸痛，很好。如果你不这样做，你至少可以减少距离计算的候选数量

这种方法的缺点：如果所有的存储都在同一个geohash中呢？我们在这里介绍同样的复杂性。在

你会寄希望于并非所有（或大多数）商店都属于同一地理哈希。现实地说，劣势只是角落里的一个劣势。所以总的来说，你应该提高绩效

Answer 2

在python中，可以使用networkx进行图形处理。 它具有广度优先搜索功能。在

https://networkx.github.io/