基於索引技術之淹水區域路徑規劃 The Route Planning in Flooded Areas Based on The Indexing Technique 三位審查委員大家好 我是研究生洪蔚齊 報告的論文題目是基於索引技術之淹水區域路徑規劃 指導教授 張雅惠 研究生 洪蔚齊 國立臺灣海洋大學資訊工程研究所 2018/11/28 DBLAB @ NTOU

大綱 研究目的與問題定義 Baseline作法 Cloud作法 實驗 結論與未來方向 2018/11/28 DBLAB @ NTOU

研究目的 假如我們從起點到目的點，需要規劃一條最短路徑，但台灣因颱風與豪雨事件所帶來的降雨，造成道路積水，因此規劃出來的最短路徑可能經過淹水區域 在之前的研究裡，已經建置Google Map路徑規劃，不過我們可以進一步提升效率，因此本論文提出基於索引方法來規劃迴避淹水區域之最短路徑 研究目的是，假如我們從起點到目的點，需要規劃一條最短路徑，但台灣因颱風與豪雨事件所帶來的降雨，造成道路積水，因此規劃出來的最短路徑可能經過淹水區域，如圖所示 在之前的研究裡，已經建置Google Map路徑規劃，不過我們可以進一步提升效率，因此本論文提出基於索引方法來規劃迴避淹水區域之最短路徑 2018/11/28 DBLAB @ NTOU

問題定義 本論文定義路網圖為一個有方向性的連通圖(connected graph)；V代表路口點的集合、E代表道路集合、灰色矩形代表淹水區域，每條路表示成(Vi,Vj)，路長表示成w(Vi,Vj)。本論文假設V1作為起始點Vs，V5作為目的點Vt 首先進行問題定義，定義路網圖為一個有方向性的連通圖(connected graph)；V代表路口點的集合、E代表道路集合、灰色矩形代表淹水區域，每條路表示成(Vi,Vj)，路長表示成w(Vi,Vj) 2018/11/28 DBLAB @ NTOU

問題定義(續) UnFlooded Shortest Path (USP) Problem：給定一個G(V, E, W)及淹水區域F ={F1、F2、…、Fk}，針對起點Vs至目的點Vt，查詢Vs至Vt的最短路徑，但此路徑不得有任何部分與Fi相交 Ex：查詢V1→V5迴避淹水區域的路徑 UnFlooded Shortest Path (USP) Problem定義為：給定一個G(V, E, W)及淹水區域F ={F1、F2、…、Fk}，查詢起點Vs至目的點Vt的最短路徑，但此路徑不得有任何部分與Fi相 例如查詢V1→V5迴避淹水區域的路徑，如表所示，共有三條路徑，其中組合1的路徑距離為最短，也就是USP 組合 路徑 距離 1 <V1,V2,V3,V4,V5> 5.5 2 <V1,V2,V3,V6,V5> 6 3 <V1,V9,V8,V7,V6,V5> 6.5 2018/11/28 DBLAB @ NTOU

Baseline作法 先建立索引，找出未經過淹水區域的路段，然後交由Dijkstra演算法進行路徑規劃 方法一：BaseRI 利用道路資料建立RTree，淹水區塊先與道路MBR做空間交集，如果有重疊，再與道路做空間交集 好處：可預先建立，減少Online階段所花的建立時間 缺點：通常道路數目較多，需較長時間建立，而過程中可能發生overlap，影響查詢時間 方法二：BaseFI 利用淹水區塊建立RTree，淹水區塊先與道路MBR做空間交集，如果有重疊，再與道路做空間交集 好處：淹水數目較少，可以加快建立時間 缺點：需在online階段建立，增加online階段時間 以下說明Baseline作法 先以R-TREE建立索引，找出未經過淹水區域的路段，然後交由Dijkstra演算法進行路徑規劃 有二種方法： 方法一是BaseRI 利用道路資料建立RTree，淹水區塊先與道路MBR做空間交集，如果有重疊，則與道路做空間交集 方法一是BaseFI 利用淹水區塊建立RTree，淹水區塊先與道路MBR做空間交集，如果有重疊，則與道路做空間交集 2018/11/28 DBLAB @ NTOU

系統架構 BaseRI方法 BaseFI方法 2018/11/28 DBLAB @ NTOU

輸入查詢及資料 BaseRI BaseFI Offline Online Online 資料：道路 資料：淹水區塊 查詢 V1 代表起點的經緯度值 V5 代表目的地的經緯度值 BaseFI Online 資料：淹水區塊、道路資料 查詢 V1 代表起點的經緯度值 V5 代表目的地的經緯度值 2018/11/28 DBLAB @ NTOU

RTree建立與未淹水路段查詢 ex:以BaseRI為例，將路網圖10條道路建立R-tree，每個節點存放2-3條道路，將未與F1淹水區塊相交的道路輸出 R9,8 R1,9 R8,7 R2,7 R1,2 R2,3 R3,4 R7,6 R6,5 R4,5 M5 M6 R1,2 R1,9 R9,8 R8,7 M1 M2 M3 M3 M4 R2,3 R3,4 R4,5 R6,5 R7,6 R8,7 R1,9 R9,8 R1,2 R8,7 R2,7 R2,3 R7,6 R2,3 R3,4 R4,5 R6,5 R7,6 2018/11/28 DBLAB @ NTOU

RTree建立與未淹水路段查詢(續) ex:以BaseFI為例，使用以下路網圖5個淹水區塊建立R-tree，每個節點存放2-3個淹水區塊，將未與淹水區塊相交的道路輸出 R1,9 R9,8 R1,2 R2,3 R2,7 M1 M2 R3,4 R4,5 R8,7 R7,6 F1 F2 F3 F1 F4 F5 R6,5 2018/11/28 DBLAB @ NTOU

Dijkstra路徑規劃模組 Single Source Shortest Path (SSP) Problem:給定一個G(V, E, W)、起點Vs和目的點Vt，查詢Vs至Vt的最短路徑 Dijkstra演算法是走訪路網圖中的每個節點V，保留目前為止所找到從Vs到各節點V的最短路徑 舉例來說，將未淹水道路建立Adjacency List並執行Dijkstra演算法，可以得出避開淹水最短路徑P1,5 2018/11/28 DBLAB @ NTOU

Dijkstra演算法過程 路徑 距離 P1,5 =<V1,V2,V3,V4,V5> 5.5 V1 V2 V3 V4 V5 V6 步驟 節點距離 新增節點 V1 V2 V3 V4 V5 V6 V7 V8 V9 1 - 2 V2、V9 3 2.5 4 5 4.5 6 5.5 7 8 2018/11/28 DBLAB @ NTOU

顯示路徑 Baseline作法最後輸出路徑利用Google Map網頁的顯示，畫面如下圖 2018/11/28 DBLAB @ NTOU

Cloud作法 利用網際網路上開放的路網圖和服務進行路徑規劃 作法是整合圖資網站既有的路徑規劃功能，淹水區域資料與GSP演算法，快速輸出迴避淹水區域的路徑 2018/11/28 DBLAB @ NTOU

相關問題 Generalized Shortest Path (GSP) Problem：給定一個G(V, E, W)路網圖，並對路口點做分類，接著依序從每一個種類Ci選取一點節點走訪，在不考慮淹水情況下，找出所有可能路徑中具有最短長度的路徑 2018/11/28 DBLAB @ NTOU

架構 2018/11/28 DBLAB @ NTOU

Google路徑查詢模組 本論文使用Google Maps Directions API服務，並輸入SearchURL查詢，交通工具選為開車DRIVING ，而此URL分為兩種，一種是Vs到Vt最短路徑，另一種是從Vs經過Waypoints集合到Vt的最短路徑，回傳格式為JSON，並剖析得到結果， SearchURL片段如下 https://maps.googleapis.com/maps/api/directions/json?origin=Vs&destination=Vt &mode=driving&language=zh-TW https://maps.googleapis.com/maps/api/directions/json?origin=Vs&destination=Vt &waypoints=points&mode=driving&language=zh-TW 2018/11/28 DBLAB @ NTOU

淹水路口查詢模組 CloudFI CloudRI 輸入 輸出 淹水區塊建立RTree，判斷Google回傳路徑是否與淹水索引內的節點重疊 Google回傳路徑建立RTree，判斷淹水區塊是否與路徑索引內的節點重疊 輸入 Google回傳路徑資料、淹水區塊 輸出 路徑淹水路口點集合 2018/11/28 DBLAB @ NTOU

鄰近節點篩選模組 目的是路徑能從起點經其中鄰近點到終點，達到迴避淹水區域目標 做法給定一個淹水路口點、threshold範圍值及路網圖，找出以淹水路口點為中心，threshold範圍之內的道路路口點 方法 使用BaseRI方法道路索引，簡稱CloudFRI 好處：不需花額外時間建立索引 缺點：道路MBR面積大，可能會發生overlap，影響查詢時間 根據路網圖的路口點資料建立RTree，簡稱CloudFPI 好處：路口點MBR面積比道路MBR小，可能會降低overlap，加快查詢時間 缺點：需多花額外時間建立索引 2018/11/28 DBLAB @ NTOU

鄰近節點篩選模組(續) 為了尋找鄰近點，我們定義 篩選過程 淹水路口的範圍圓，以淹水路口為中心，threshold t為半徑形成的圓 節點外接圓，以節點中心表示外接圓中心，節點中心與MBR端點距離表示外接圓半徑 篩選過程 若淹水路口與外接圓中心距離扣除半徑後小於threshold t，表示淹水範圍圓與節點外接圓相交，節點的某些路口點可能在淹水的範圍園內，因此進一步尋找在範圍內的路口點，反之節點路口點在淹水路口範圍園外，不是我們要尋找的替代點，如下圖所示 2018/11/28 DBLAB @ NTOU

鄰近節點篩選模組(續) Ex:查詢V7鄰近點集合 假設threshold值為1.5，使用道路索引查詢，從根節點開始往下尋找，由圖得知M5、M6節點外接圓與V7範圍圓(圖中的實線圓)相交，因此尋找小孩節點M1、M2、M3和M4，由圖得知V7範圍圓與M2、M3、M4外接圓相交，因此在M2、M3、M4內的路口點尋找V7的鄰近點，由於V7與V2、V3、V5、V8距離大於threshold，與V4和V6距離小於threshold，因此V4、V6為V7鄰近點 2018/11/28 DBLAB @ NTOU

GSP建立模組 我們將點分類為C0={Vs}、C1~CN為N個淹水路口鄰近點、CN+1={Vt}，接著利用GSP演算式計算最短路徑 i=0 代表起點，所以距離為0 整個X矩陣皆計算完成後，選出每個種類內最短距離的一個點成為代表節點 起點→{各種類代表節點}→目的地 2018/11/28 DBLAB @ NTOU

GSP演算法過程 Ex:起點與目的地及兩個淹水路口點替代節點建立4個種類表，C0={V1}、C1={V3、V8}、C2={V4、V6}、C3={V5} Matrix Step min_dis VisitID X[0,1] - X[1,1] X[0,1]+ Distance (C0,1 , C1,1)= 0+2=2 2 C0,1 X[1,2] X[0,1]+ Distance (C0,1 , C1,2)= 0+2.5=2.5 2.5 X[2,1] X[1,1]+ Distance (C1,1 , C2,1)= 2+2=4 X[1,2]+ Distance (C1,2 , C2,1)= ∞ 4 C1,1 X[2,2] X[1,1]+ Distance (C1,1 , C2,2)= ∞ X[1,2]+ Distance (C1,2 , C2,2)= 2.5+3=5.5 5.5 X[3,1] X[2,1]+ Distance (C2,1 , C3,1)= 4+1.5=5.5 X[2,2]+ Distance (C2,2 , C3,1)= 5.5+1=6.5 C2,1 2018/11/28 DBLAB @ NTOU

Google路徑規劃與畫面顯示 最後，將Vs當作起點，替代點當作waypoint，Vt當作目的地，透過Google路徑規劃產生路徑，並利用網頁顯示 2018/11/28 DBLAB @ NTOU

實驗 2018/11/28 DBLAB @ NTOU

實驗環境 個人電腦 實作工具 CPU為i5-3570四核心且核心時脈為3.4GHz 記憶體為8GB 作業系統為64位元的Windows 7企業版。 實作工具 Baseline兩個方法(BaseRI和BaseFI)以Microsoft Visual C++ 2012進行實作。 Cloud兩個方法(CloudFRI和CloudFPI)除了主程式以及替代節點篩選模組以C++實作外，雲端路徑查詢模組是利用C# API呼叫路徑查詢服務。而顯示路徑部分，則使用本機端架設IIS Web Server & ASP.NET。 2018/11/28 DBLAB @ NTOU

實驗資料集 我們實驗所使用的資料集包括交通部路網數值圖服務網提供的路網圖、國家災害防救科技中心提供的各縣市『一日暴雨600mm淹水潛勢圖』與人工產生出來的淹水區域資料 選擇基隆、台北、屏東林邊佳冬地區淹水當作真實淹水區域資料，其面積為0.25 𝑘𝑚 2 (長寬皆0.5km)的矩形區塊 人工所產生出來的淹水區域資料以整個台北地區為範圍，且根據高斯、隨機與群聚分佈不重複的產生0.01 𝑘𝑚 2 (長寬皆0.1km)的淹水區塊 2018/11/28 DBLAB @ NTOU

實驗使用資料集(續) 路口點 道路 人工淹水 真實淹水 基隆 2323 2624 101 林邊、佳冬 南州、新埤 7166 9252 台北   路口點 道路 人工淹水 真實淹水 基隆 2323 2624 101 林邊、佳冬 南州、新埤 7166 9252 台北 13193 15856 個數50、100、200 分布Gaussian、Cluster、Random 100 宜蘭 16139 21885 2018/11/28 DBLAB @ NTOU

實驗結果 實驗1-改變索引建立方法 實驗2-淹水路口查詢效率 實驗3-鄰近點查詢效率 實驗4-不同大小路網 實驗5-不同淹水數量 實驗6-規劃路徑成功率 2018/11/28 DBLAB @ NTOU

實驗1-改變索引方法 第一個實驗，我們固定台北市路網，針對Baseline方法不同索引進行比較。比較測量執行時間方式為選擇十組OD，從輸入道路後至建立、查詢和路徑規劃輸出的時間，然後取這十組平均 2018/11/28 DBLAB @ NTOU

實驗1-改變索引方法(續) 我們發現兩個索引方法的建立、查詢和路徑規劃時間皆會隨著路網圖數量增加而上升。Split方法查詢效率比Sorted方法好，但建立時間比Sorted方法慢，而Split方法有較好得查詢效率，因此本論文採用Split方法索引 2018/11/28 DBLAB @ NTOU

實驗2-淹水路口查詢效率 這個實驗主要比較淹水路口查詢索引，其中PathIndex為路徑建索引，淹水查詢。FloodIndex為淹水建索引，路徑查詢。路徑點又分為合併和未合併，合併是將小於100公尺之間的點合併成一條路，未合併是依照回傳順序，每兩個點合成一條路 2018/11/28 DBLAB @ NTOU

實驗2-淹水路口查詢效率(續) 我們選擇未合併前路徑個數與淹水個數接近OD進行比較，以及將路徑合併後的比較，發現合併後查詢效率比合併前好，由於合併後路徑個數比淹水少，通常會使用較多數目的資料建索引，因此使用FloodIndex索引 2018/11/28 DBLAB @ NTOU

實驗3-鄰近點查詢效率 這次實驗，固定threshold值為1km，探討不同路網圖大小之影響，比較道路索引和路口索引尋找鄰近點的時間，方式是隨機選取10組OD，記錄每組OD尋找鄰近時間，然後取平均 我們可以發現隨著道路個數增加，時間成線性增加，因為比對的路口點數變多，因而增加查詢時間 2018/11/28 DBLAB @ NTOU

實驗3-鄰近點查詢效率(續) 這次實驗，固定台北市路網，探討不同threshold值之影響，比較道路索引和路口索引尋找鄰近點的時間，方式是隨機選取10組OD，記錄每組OD尋找鄰近時間，然後取平均值 我們可以發現隨著threshold增加，時間成線性增加，因為涵蓋範圍越多，需要比對更多路口點，因而增加查詢時間 2018/11/28 DBLAB @ NTOU

實驗4-規劃路徑成功率 這次實驗，我們探討不同threshold值，迴避淹水區域路徑的成功率，實驗中路網採用台北市的路網圖，淹水區域採用真實資料的100個淹水區域，索引則採用路索引，修正次數最多不超過三次。接著，選取40組起迄，記錄這40組是否避開淹水區域，其中CloudFRI表示路徑未修正，CloudFRI2表示路徑已修正 我們可以發現增加threshold值，成功率隨線性增加，也就是說修正次數減少，因為能選擇的路口點數較多 2018/11/28 DBLAB @ NTOU

實驗5-不同大小路網 這次實驗，固定真實資料的100個淹水區域，探討路網圖大小之影響，比較Cloud方法淹水路口查詢、替代節點篩選及GSP模組，方式是隨機選取10組OD，記錄每組OD執行模組時間，然後取平均 而Join表是尋找淹水路口及查詢替代點模組，差別在於前者使用道路索引尋找鄰近點，後者則使用路口索引 我們發現隨著道路個數增加，查詢淹水路口、替代點及GSP的時間成非線性增加 2018/11/28 DBLAB @ NTOU

實驗5-不同大小路網(續) 這次實驗，固定真實資料的100個淹水區域，探討不同路網圖大小之影響，比較BaseRI、BaseFI和CloudFRI和CloudFPI四個方法總時間，其中BaseRI表示道路索引，BaseFI表示淹水區塊索引，CloudFPI表示路口索引。針對每個路網圖，我們隨機挑選10組起迄資料，記錄每組起迄執行時間，然後取這10組平均 2018/11/28 DBLAB @ NTOU

實驗5-不同大小路網(續) 我們觀察出以下幾種結論 四個方法總時間皆會隨著路網圖數量上升而線性增加，這是因為當道路變多時R-tree的建立時間、查詢次數也會增加 BaseFI方法的整體時間比BaseRI方法還快，主要是因為路的個數比淹水個數多，因此建立RTree時間BaseRI比BaseFI慢，查詢時間差不多，所以整體時間BaseRI比BaseFI慢 CloudFPI方法的整體時間比CloudFRI方法還快，主要是因為點索引矩形重疊程度比路索引還小，因而尋找鄰近節點效率點索引比路索引好 Cloud作法明顯比Baseline作法快，主要因為判斷交集的道路個數較少，花在查詢時間低，所以整體時間比Baseline快 2018/11/28 DBLAB @ NTOU

實驗6-淹水區域數量之實驗 這個實驗固定台北路網，依據不同分布產生50、100和200個淹水區塊，比較BaseRI、BaseFI和CloudFRI和CloudFPI四個方法總時間，發現皆會隨著路淹水數量增加而上升 Clustered Random Gaussian 2018/11/28 DBLAB @ NTOU

結論與未來方向 本論文提出四個方法迴避淹水區域的路徑規劃法，也進行大量實驗比較四個方法效率 Cloud兩個方法因為判斷交集的道路個數較少，所以整體花費時間比Baseline兩個方法少。隨著道路數量增加，趨勢會更明顯，例如道路數量2269筆、100個淹水區域，Cloud整體的效率更是Baseline的1.68倍，而道路數量15874筆、100個淹水區域，Cloud整體的效率更是Baseline的6倍 本論文未來的研究方向，希望能夠提升路徑規劃準確率及成功率，並同時保持高效率 2018/11/28 DBLAB @ NTOU

報告完畢 敬請指教 2018/11/28 DBLAB @ NTOU