postgresql - 带有公交线路和时间表的最短路径

Question

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

我的目标是根据公共(public)汽车在两个公共(public)汽车站之间花费的时间，找到它们之间的最短路线。

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

问题是:我有一些并行链路，因为每辆公共(public)汽车每天多次运行他的线路，每次都以相同的方式运行。

我试过 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

Answer 1

抛开一条公交线路的多个实例的问题，这个查询带有rCTE (recursive Common Table Expression)按照说明解决问题:

My goal is to find the shortest way between 2 bus stops, based on the time the bus takes between them.

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 demo.

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

算法遍历每一个连接，并检查它是否已经存在(放弃)或者是否已经到达(成功)。然后选择通向成功的最短路线。

这适用于中小型基数。不过，它不能很好地扩展 用于大表，因为每 可能的路径(不绕圈子)都已尝试。递归 CTE 无法检查另一条路线是否已经在更短的时间内成功。通过消除已经花费太长时间的所有路线，专门的算法可以表现得更好。您可以使用 plpgsql 函数执行此操作，但在 C 中实现它会快得多。