0

我正在使用 Postgres/PostGIS/pgRouting 为我正在做的分析准备数据集。我需要准备的数据集中的一个字段是 100,000 个家庭的数据集（点数据）和几十个活动中心的数据集（也是点数据）之间的最短道路距离。为此，我创建了一个节点和网络数据集。我还更新了我的家庭和活动中心数据集，其中的列包含最近节点的 id 值。

到目前为止，我已经能够使用driving_distance() 函数来计算从中央商务区（CBD）到每个家庭的道路距离，但我希望一次性为所有中心执行此操作，而不必制作单独的距离数据集为每个中心。

更重要的是，我最终将不得不对每个家庭和最近的火车站之间的道路距离做同样的事情。

有解决方案吗？

非常感谢，

罗

4

1 回答 1

1

我不知道我是否解决了您的问题。如果是这样

  • 你有 10 万个家庭
  • 其他兴趣点（活动中心、火车站等）数量较少（可能为 1k）
  • 目的是在不进行过多运行时间计算的情况下显示从/到其中一个家庭到/从兴趣点的最短路径。
  • 我进一步假设您拥有的道路数据是定向的，即可能存在单向道路。
  • 这些点变化不会太频繁，

那么你可以尝试这样的方法：

  1. 准备一个以所有 100+1k 个节点和道路为边的有向图。道路将从一个节点指向另一个节点，其权重与它们的距离成正比。
  2. 准备一个相同的反向图 - 即只需切换 from 和 to 节点，保持相同的权重。
  3. 对于每个兴趣点 P，做一个 Dijkstra，它将返回 100+1k 个点的完整前驱图（最短路径树作为数组），它给出了从 P 到所有其他点的最短距离。这是一个包含 100+1k 个值的整数数组。
  4. 在反向图上重复此操作。这会给你一个前身地图，它给出每个兴趣点 P 与所有其他点的最短距离。
  5. 现在你有 2 * 1k 个数组，每个数组有 100+1k 个值。对于每个数组，您还知道点 P 在其中的位置。

运行时计算：

  • 要计算从 P 到任何其他点的最短路径，请使用第一个数组。转到数组上目标点的位置，看看它的对应值是什么，然后转到数组上的那个元素，重复直到到达 P 的位置。

示例：如果 P 位于第 7 位并且您的终点位于第 12 位，则转到数组元素 12 ，读取其值 array_val[12]=10，现在使用 10 ，例如 array_val[10]=7 ，那么您的路径为 7 -10-12。

  • 同样，如果您对第二个数组执行此操作，则最短路径将是相反顺序的路径，即 12-10-7。

观察：

  1. 以上两个步骤在运行时（毫秒）执行起来要快得多。对于这些，您在运行时不需要 Dijkstra，一个 .
  2. 2 * 1k 最短路径树的第一次计算总共需要大约 2*1000*0.8 =1600 秒（在具有 4 GB RAM 和 i5 处理器的 linux 笔记本电脑上）。
  3. 您可能想直接使用 boost-graph 来执行此操作，但是..

使用 pgrouting：

如果您想使用 pgrouting，您可能需要修改 boost_wrapper.cpp 函数 boost_dijkstra 以返回完整的前任地图，而不是仅返回一个最短路径（将其复制到 path_vect）。这将使 pgrouting dijkstra 始终返回最短路径树，而不仅仅是最短路径。我还没有对此进行测试（请注意，pgrouting 在内部会进行索引重新排序，但此方法应该会返回您的原始索引 ID）。

于 2012-09-04T16:52:19.710 回答