[發明專利]一種基于MapReduce的公共交通出行路徑規劃索引方法

有效

• 申請號: 201811642741.4
• 申請日: 2018-12-29
• 公開（公告）號: CN109711633B
• 公開（公告）日: 2022-09-20
• 發明（設計）人: 劉玉葆;寧志清
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

本發明涉及一種基于MapReduce的公共交通出行路徑規劃索引方法，具體包括以下步驟：S1.確定時態圖G的頂點集V上的全序關系，根據確定的頂點集V的全序關系對時態圖G進行子圖的劃分；S2.對于劃分的每個子圖，分別使用MapReduce集群中的各個計算節點讀取其分區數據，然后通過Map函數計算每個子圖的弱規范路徑，并將結果以映射形式保存在弱規范路徑索引集I中；S3.使用Cleanup函數將弱規范路徑索引集I中的每個映射轉成鍵值對；S4.使用Reduce函數將鍵值對中鍵等于頂點v_i且頂點v_i是起點的映射加入集合I_out中，把鍵等于頂點v_j且頂點v_j是終點的映射加入集合I_in中，然后按照分布式時間路徑索引的定義，對集合I_out和集合I_in中的映射進行排序，最后得到時態圖G的分布式時間路徑索引。

技術領域

本發明涉及智能交通技術領域，更具體地，涉及一種基于MapReduce的公共交通出行路徑規劃索引方法。

背景技術

城市公共交通系統是現代化城市交通的重要組成部分，在當今城市社會生活中扮演著不可或缺的角色。使用公共交通工具的人們在出行前往往需要進行路線規劃，繁忙的人們已經習慣了尋找公交站點、候車、坐車、換乘的出行方式，他們對于交通工具的選擇越來越多，對于出行路線的選擇也越來越多，對于出行的便利性需求越來越迫切，希望出行的時間更少一些，希望以更快速、更精準的方式完成出行目的。現已存在一些應用軟件嘗試幫助人們達到這樣的出行目的，如百度地圖和高德地圖。然而，這些應用軟件為用戶規劃出行路徑時不考慮公共交通工具的時刻信息，用戶在出行前無法從這些應用軟件中知道在路徑上到達每個站點的準確時間，即這些應用軟件不考慮公交的時刻信息，給用戶提供靜態的路徑規劃。例如，廣州地鐵的乘客想查詢從廣州南站到廣州塔站的地鐵路線，這樣的路線有很多條，當乘客想知道最早到達廣州塔的路線時，由于靜態的路徑規劃缺乏時間信息，無法知道乘客經過沿途每個站點的到達時刻和出發時刻，也無法為乘客提供最早達到廣州塔的路線。同時由于靜態的路徑規劃提供的路線是固定不變的，即使在地鐵停運時間內也會為乘客提供不可行的路線，而無法識別哪些已經停運的地鐵路線。出現以上問題的原因是因為靜態的路徑規劃完全不考慮公共交通系統的時刻表信息，而這些時刻表信息是大量地存在于公交系統中的，許多地圖應用軟件沒有利用這些信息，挖掘其中的價值。

針對傳統的靜態圖及在其上進行靜態路線規劃的不足，Huanhuan Wu等人在VLDB2014上提出了時態圖(Temporal Graph)的概念。公共交通網絡可以看作時態圖的一種應用，時態圖比靜態圖有更強的表達能力和應用潛力，比如，帶有時刻表信息的公共汽車、地鐵、高鐵、航班飛機等公共交通網絡。不過，Huanhuan Wu等人給出的時態圖上路線規劃算法只能求出滿足給定的單個時間區間和單個起點和終點的路徑。Sibo Wang等人在SIGMOD2015上提出的TTL(Time Table Labelling)算法解決了已有算法的不足。該算法分為兩個階段：索引階段和查詢階段。在索引階段，TTL算法考慮了用戶所有可能的出行時間和所有起點、終點，為每個可能的出行需求進行路徑規劃，并把路徑規劃的結果保存到索引中。在查詢階段，根據用戶出行需求從索引中快速查詢路徑。不過，TTL算法索引建立時間往往較長，如SIGMOD論文實驗結果所示在CPU為8核，內存為64G的服務器上，在Sweden數據集(約5萬個頂點、400萬條邊)的索引時間就超過了16分鐘。

針對TTL算法索引建立效率低的不足，本發明提出了一種基于MapReduce的公共交通出行路徑規劃索引方法。這種方法比TTL算法建立索引的效率更高，且索引查詢性能與TTL算法相近。

要使用分布式計算框架MapReduce計算路徑規劃的解，其核心是實現最短路徑的分布式計算方法。現已存在一些Dijkstra和Floyd-Warshall等求最短路徑的經典算法的分布式實現方案。Dijkstra算法利用了“最短路徑的子路徑也是最短的”這一性質，能輕易地應用到簡單有(無)向圖中。但這一性質在時態圖中并不成立，因此經典最短路徑算法不能直接應用到時態圖上。