2

几天以来我一直在寻找解决方案，但找不到解决方法。

我的目标是根据巴士在它们之间的时间找到两个巴士站之间的最短路径。

所以我有公交线路，以及每条线路的时间表。成本由实际公交车站和下一个公交车站之间的时间差表示（以秒为单位）。源和目标是公交车站的ID

问题是：我有一些平行的链接，因为每辆公共汽车每天都有很多次线路，每次都以相同的方式运行。

我尝试过使用 pgrouting 的 shortest_path 函数，但由于并行链接，它多次返回错误的解决方案。

我已经看到了shooting_star，但我认为我不能在没有几何的情况下使用它。

我有 PostGreSQL 9.1.9 和 PostGIS 2.0.1。这是我的数据库提取的示例：

        id        |      idcourse     |    source    |    target    |    cost    |
        1         |           1       |       62     |      34      |      60    |
        2         |           1       |       34     |      16      |     360    |
        3         |           1       |       16     |      61      |      60    |
        4         |           1       |       61     |      60      |      120   |
        5         |           2       |       62     |      34      |      60    |

这里的最后一排是与其他线路相同的公交线路（idcourse = 1）但一小时后

这是获取此信息的请求：

select hc.idhorairecourse as id, c.idcourse,
hc.idarret as source,
(select hc2.idarret from horairecourse hc2 where hc2.idcourse = c.idcourse and hc2.heure > hc.heure order by hc2.heure limit 1) as target,
(extract(epoch from ((select horairecourse.heure from horairecourse where horairecourse.idcourse = c.idcourse and horairecourse.heure > hc.heure order by horairecourse.heure limit 1) - hc.heure))) as cost
from course c
inner join horairecourse hc on c.idcourse = hc.idcourse
where (select horairecourse.idarret from horairecourse where horairecourse.idcourse = c.idcourse and horairecourse.heure > hc.heure order by horairecourse.heure limit 1) is not null
order by c.idcourse, hc.heure
4

1 回答 1

1

除了一条总线的多个实例的问题之外，这个带有rCTE（递归公用表表达式）的查询解决了上述问题：

我的目标是根据巴士在它们之间的时间找到两个巴士站之间的最短路径。

WITH RECURSIVE
   from_to AS (SELECT 34 AS _from, 60 AS _to)  -- insert from & to once

,  route AS (
   SELECT target, ARRAY[_from, target] AS stops, cost
       , (target = _to) AS arrived
   FROM   from_to, bus
   WHERE  source = _from

   UNION ALL
   SELECT b.target, r.stops || b.target, r.cost + b.cost
       , (b.target = _to) AS arrived
   FROM   from_to, route r
   JOIN   bus   b ON b.source = r.target
   WHERE  b.target <> ALL(stops) -- don't circle
   AND    r. target <> _to       -- we arrived
   )
SELECT stops, cost
FROM   route
WHERE  arrived
ORDER  BY cost
LIMIT  1;

-> SQLfiddle演示。

您可以在此过程中轻松收集更多信息。

该算法遍历每个连接并检查它之前是否存在（放弃）或是否已经到达（成功）。然后选择通往成功的最短途径。

这适用于中小基数。但是，它不适用于大桌子，因为尝试了所有可能的路线（不绕圈子）。递归 CTE 无法检查另一条路由是否已经在更短的时间内成功。通过消除所有已经花费太长时间的路线，专门的算法可以表现得更好。您可以使用 plpgsql 函数来做到这一点，但在 C 中实现起来会快得多。

于 2013-07-22T20:53:23.197 回答