1

I have 2750 city centers in Belgium. I need to know the distances between every 2 city centers. But that results in an matrix of 57MB, just to remember those distances (not even the routes), so that scales terribly.

Instead, I am looking at using Highway intersections as hubs. Basically, every city knows it's nearby cities and it's nearby hubs (= highway intersection). All hubs know the distance to each other.

So the distance from 1 city A to another non-nearby city B, can be calculated by the distance of cityA -> hubX -> hubY -> cityB. Because most cities have typically 3 hubs nearby, I might need to look at all 9 combinations and take the shortest. But in any case it should scale better memory wise.

Now the problem: Can I describe a highway intersection as a single point? Think about it: a highway consist of 2 roads (one in both direction), so a highway intersection center has 4 roads (not even counting the arms).

4

1 回答 1

1

一些想法：

  1. 您可以通过 MapDB 或 GraphHopper 将这些距离存储在堆外或磁盘上，其简单的 DataAccess 实现使其独立于 RAM
  2. 你可以使用浮点数，它应该只有 ~30MB 甚至更短，只使用公里
  3. 您可以尝试按需路由，而无需存储，因为计算路由只需几毫秒。禁用指令和计算点数使其速度提高一倍。您甚至可以禁用计算距离并仅使用 path.weight - 这将为您提供另一个很好的加速，但需要使用较低级别的 GraphHopper，并且仅在您知道自己在做什么时才建议使用。

现在回答你的问题。GraphHopper 使用由节点（路口）和边（连接路口的街道）组成的图模型。仍然是一个环形交叉路口由多个节点组成。但总的来说，应该可以使用这样的“离开”节点作为“hub-id”。

我看到了两种计算这些节点的方法：

  • 通过运行 Contraction-Hierarchy 并选择最高的 1000 个节点并将它们定义为集线器 - 这将类似于“传输节点路由”文件中描述的内容
  • 或者您计算从一个城市到所有其他城市（或仅 8 个地理方向）的路线，并找到两条路线的最后一个公共节点以识别一些

对于这两种方法，您都必须更深入地研究 GraphHopper，并且您可能需要较低级别的 API。

于 2014-09-04T11:29:43.120 回答