A Study of Real-Time Pre-Trip Route Planning Algorithm

「出發，總有個方向」，但「條條道路通羅馬」，該往哪條路？ 在人們從事社會經濟活動時，移動過程不具經濟意義，會希冀越快或越準時抵達目的地投入社經活動。以往最短路徑問題研究以距離等定值資料作為路徑成本，其靜態交通資訊未能真實地反映交通擁擠程度，路徑效益將大打折扣。時間是駕駛者最能直接感受的指標，尤其是塞在車陣中，最容易感到時間流逝，因而「行前路徑規劃」較「途中變換路徑」在決策上更有彈性。 依時性最短路徑問題分為「依時性前推式最短路徑問題」和「依時性後推式最短路徑問題」。以往相關研究皆著重於「依時性前推式最短路徑問題」，甚少文獻探討「依時性後推式最短路徑問題」，然而通勤者往往受限於學校、公司或大眾運輸工具制定的抵達時間，以「依時性後推式最短路徑問題」作路徑規劃建議較符合實際需求。 由於交通蒐集資料屬於離散型資料，然而「離散型依時性後推式最快路徑演算法」會存在時間間隙問題，偏估了預測的可行出發時間或導致路徑搜尋無法收斂情形，因此必須利用擬合模式連續化離散型交通資料，避免時間間隙問題產生。 綜合以上所述，本研究模擬離散型依時性路段旅行時間資料，利用線性擬合模式連續化離散型交通資料，以最短路徑演算法為路徑規劃基礎，建構一「連續型依時性後推式最快路徑演算法」模式，於行前建議駕駛者行駛路徑和可行出發時間，始在預計的抵達時間下抵達訖點。“All roads lead to Rome.” Which route can someone go toward destination. When people engage in socio-economic activity, they hope arrive their destination fast or timely because the process of moving between origin and destination isn’t productive. The route cost of the shortest path problem was based on distance or static data that can’t reflect the level of traffic congestion, thus the benefit of route planning will loss. Time is the index that drivers, especially stuck in traffic, can be affected directly, therefore “pre-trip route planning” is more flexible than “en-route route changing”. The time-dependent shortest path problem included: “The time-dependent forward shortest path problem” and “The time-dependent backward shortest path problem” The past related research focused on the former and few papers discuss the latter. “The time-dependent backward shortest path problem” would consist with the arrival time of commuters, who is limited by schools, offices, or the timetable of public transportation. Due to the most traffic data is discrete data, “the discrete time-dependent backward fastest path algorithm” exists the time gap problem that lead to biased estimate. This study is based on “the shortest path algorithm” and linear spline model to construct a “continuous time-dependent backward fastest path algorithm.” During the pre-trip test, this model suggests a driver route planning and the feasible departure time to arrive the destination on expectation arrival time.摘要 .............................................i Abstract .............................................ii 目錄 .............................................iii 圖目錄 .............................................v 表目錄 .............................................vi 第一章 緒論......................................... 1 1.1 研究背景與動機............................... 1 1.2 研究目的..................................... 2 1.3 研究範圍..................................... 2 1.4 研究內容與流程............................... 3 第二章 文獻回顧..................................... 5 2.1 智慧型運輸系統(ITS).......................... 5 2.1.1 先進旅行者資訊系統(ATIS)..................... 5 2.1.2 行前資訊系統................................. 6 2.1.3 旅行者資訊系統的效益......................... 7 2.2 路徑規劃類型................................. 8 2.3 最短路徑問題(Shortest Path Problem).......... 10 2.3.1 路網資料結構................................. 10 2.3.2 路網基本定義................................. 11 2.3.3 最短路徑問題................................. 12 2.3.4 標記修正法(LCA).............................. 13 2.3.5 標記設定法(LSA).............................. 15 2.3.6 評析標記設定法(LCA)、標記修正法(LSA)......... 16 2.4 Dijkstra’s algorithm與A* algorithm.......... 17 2.4.1 Dijkstra’s algorithm........................ 17 2.4.2 Dijkstra’s algorithm範例.................... 19 2.4.3 Dijkstra’s algorithm評析.................... 21 2.4.4 A* algorithm................................. 22 2.5 依時性最短路徑問題........................... 23 2.5.1 依時性最短路徑問題........................... 23 2.5.2 依時性最短路徑演算法......................... 25 2.5.3 依時性前推式最短路徑演算法................... 27 2.5.4 路口延滯成本................................. 28 2.5.5 路口轉向成本................................. 29 2.6 小結......................................... 30 第三章 研究方法..................................... 31 3.1 前(後)推式路徑演算法原理及證明過程........... 31 3.2 依時性前推式最快路徑演算法................... 33 3.3 離散型依時性後推式最快路徑演算法............. 35 3.4 連續型依時性後推式最快路徑演算法............. 40 3.5 線性擬合模式(Linear Splines)................. 43 第四章 演算法流程圖及程式文件說明................... 45 4.1 演算法流程圖................................. 45 4.1.1 搜尋法則..................................... 49 4.1.2 左右轉向判斷................................. 52 4.2 程式說明文件................................. 54 4.2.2 重要子程式功能說明........................... 55 第五章 路徑規劃實作................................. 60 5.1 實驗研究範圍................................. 60 5.2 路口相關資料................................. 61 5.3 實驗研究範圍限制............................. 70 5.4 範例測試..................................... 71 第六章 結論與建議................................... 74 6.1 結論......................................... 74 6.2 建議......................................... 75 參考文獻 ..............................................7