行前即時路徑規劃演算法之研究

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

葉羿稚(I-Chih Yeh)

指導教授 ： 張堂賢

國立臺灣大學/工學院/土木工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.03161

摘要

「出發，總有個方向」，但「條條道路通羅馬」，該往哪條路？
在人們從事社會經濟活動時，移動過程不具經濟意義，會希冀越快或越準時抵達目的地投入社經活動。以往最短路徑問題研究以距離等定值資料作為路徑成本，其靜態交通資訊未能真實地反映交通擁擠程度，路徑效益將大打折扣。時間是駕駛者最能直接感受的指標，尤其是塞在車陣中，最容易感到時間流逝，因而「行前路徑規劃」較「途中變換路徑」在決策上更有彈性。
依時性最短路徑問題分為「依時性前推式最短路徑問題」和「依時性後推式最短路徑問題」。以往相關研究皆著重於「依時性前推式最短路徑問題」，甚少文獻探討「依時性後推式最短路徑問題」，然而通勤者往往受限於學校、公司或大眾運輸工具制定的抵達時間，以「依時性後推式最短路徑問題」作路徑規劃建議較符合實際需求。
由於交通蒐集資料屬於離散型資料，然而「離散型依時性後推式最快路徑演算法」會存在時間間隙問題，偏估了預測的可行出發時間或導致路徑搜尋無法收斂情形，因此必須利用擬合模式連續化離散型交通資料，避免時間間隙問題產生。
綜合以上所述，本研究模擬離散型依時性路段旅行時間資料，利用線性擬合模式連續化離散型交通資料，以最短路徑演算法為路徑規劃基礎，建構一「連續型依時性後推式最快路徑演算法」模式，於行前建議駕駛者行駛路徑和可行出發時間，始在預計的抵達時間下抵達訖點。

關鍵字

連續型依時性路徑規劃演算法 ； 後推式最快路徑演算法 ； 依時性最短路徑問題 ； 路徑導引系統

並列摘要

“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.

並列關鍵字

continuous time-dependent route planning algorithm ； the backward fastest path algorithm ； the time-dependent shortest path problem ； route guidance system

參考文獻

2.Watling, D. and T. Van Vuren, The modelling of dynamic route guidance systems. Transportation Research Part C, 1993. 1(2): p. 159-182.

3.Barfield, D., Integrating commuter information needs in the design of a motorist information system. Transportation Research Part A, 1991. 25(2): p. 71-78.

4.Dijkstra, E.W., A note on two problems in connexion with graphs. Numerische Mathematik, 1959. 1: p. 269-271.

5.Sheffi, Y., Urban transportation networks: Equilibrium analysis with mathematical programming methods 1985, Englewood Cliffs, N.J.: Prentice Hall.

6.Smith, J.C. and K. Russam. Some possible effects of AUTOGUIDE on traffic in London. in IEEE International Conference on Vehicle Navigation and Information Systems. 1989. Toronto, Canada.