最短路線與公交線路和時間表

我正在尋找一個解決方案，因爲天，但無法找到解決辦法。最短路線與公交線路和時間表

我的目標是根據公交車在兩個公交車站之間的時間找到兩個公交車站之間的最短路線。

所以我有公交線路和每個人的時間表。成本由實際公共汽車站和下一個公交車站之間的時間差（以秒爲單位）表示。源和目標是巴士站的ID

問題是：我有一些並行鏈接，因爲每個總線每天都會多次執行他的行，每次都以相同的方式運行。

我已經嘗試過使用pgrouting的shortest_path函數，但由於並行鏈接它會返回很多次錯誤的解決方案。

我見過關於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），但一小時後

，這裏是得到這個請求：

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

來源

2013-07-22 theplayer777

你的問題中沒有任何內容說「並行鏈接」與你的問題有關。由於沒有給出絕對時間戳，所以每條公交路線只需要*一份*副本。只是消除重複... –

不，因爲我必須知道在什麼時間必須乘坐這輛巴士準時到達特定的巴士站...... – theplayer777

那麼，這不是你的問題。 –

多個實例的用於一條總線擱置的問題，這個查詢與rCTE (recursive Common Table Expression)解決如所陳述的問題：

我的目標是根據巴士在他們之間所乘坐的時間爲，找到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 demo.

您可以輕鬆地收集沿途的更多信息。

該算法遍歷每個連接並檢查之前（放棄）或者是否已到達（成功）。然後選擇最短的成功路線。

這適用於小到中等的基數。它並沒有很好的規模很大大表，但是，因爲每可能的路線（不進入圈）被嘗試。遞歸CTE無法在更短的時間內檢查另一條路由是否成功。通過消除已經花費太長時間的所有路線，專用算法可以表現得更好。你可以用plpgsql函數做到這一點，但在C中執行速度要快得多。

來源

2013-07-22 20:53:23

是的，你的解決方案對你的例子很好，但是我有500多個關係......有沒有最短路徑的解決方案？ – theplayer777

最短路線與公交線路和時間表

回答

相關問題