2

何日も解決策を探していますが、解決する方法が見つかりません。

私の目標は、バスの所要時間に基づいて、2 つのバス停間の最短経路を見つけることです。

だから私はバス路線とそれぞれの時刻表を持っています。コストは、実際のバス停と次のバス停との時間差 (秒単位) で表されます。ソースとターゲットはバス停の ID です

問題は、各バスが 1 日に何度も同じ路線を走っており、毎回同じ方法で運行されているため、並列リンクがいくつかあることです。

pgrouting の shortest_path 関数を試してみましたが、並列リンクが原因で itt が何度も間違ったソリューションを返します。

私はshooting_starについて見てきましたが、私の場合、ジオメトリなしでは使用できないと思います。

私は PostGIS 2.0.1 で PostGreSQL 9.1.9 を持っています。私のデータベース抽出の例を次に示します。

        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) ですが、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

1 つのバス ラインに対する複数のインスタンスの問題はさておき、rCTE (再帰的な共通テーブル式)を使用したこのクエリは、次のように問題を解決します。

私の目標は、バスの所要時間に基づいて、2 つのバス停間の最短経路を見つけることです。

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 に答える