依時性後推式路徑演算系統開發

Development of Time-dependent Backward Route Planning System

張堂賢(Tang-Hsien Chang) ； 闕嘉宏(Chia-Hung Chueh)

《運輸學刊》 25卷2期 (2013/06) Pp. 169-198

https://doi.org/10.6383/JCIT.201306_25(2).0002

摘要

本研究結合路徑演算、旅行時間預測以及漏失資料插補等三大模組，開發出一套依時性後推式路徑演算系統。有別於先前的路徑演算研究，本系統將後推式演算概念導入A*路徑演算中，將傳統的空間成本項目以旅行成本、延滯成本與轉向成本等時間成本項目進行取代；同時，資料插補技術可抵抗時間序列資料漏損缺失，利用歷史資料與即時資料走勢進行補償；後續的卡曼濾波器與傅立葉轉換技術在完整的時間序列資料下，持續對目標路段之旅行時間進行精確的長短期預測。上述成果皆以JAVA程式語言進行開發，搭配基因演算法對各模型所需參數進行最佳化訓練，其成果將可輔助相關系統突破前推式演算思維，讓使用者依照預期抵達時間需求，獲得有效且穩定的建議出發時間與路徑。

關鍵字

後推式路徑演算法 ； 旅行時間預測 ； 漏失資料插補 ； 卡曼濾波器 ； 傅立葉轉換

並列摘要

This paper develops a time-dependent backward route-planning system by integrating route-planning, travel-time prediction and data interpolation modules. Compared with previous studies, this system introduces a backward search into the A* algorithm, replacing the more conventional spatial cost with temporal costs, namely, travel time, turning time and delay time. Furthermore, the interpolation module could mitigate the effect of incomplete time-series data by reconstructing missing data with historical and real-time data. With a reconstructed time-series, the prediction module can then continuously make accurate short- and long-term predictions on travel time using Kalman filter and Fourier transform. All of the above are implemented in JAVA language, with all parameters optimized using the Genetic algorithm. This system can help provide travelers with robust suggestions for departure time and travel route.

並列關鍵字

Backward route planning ； Travel time prediction ； Missing data interpolation ； Kalman Filter ； Fourier transforms

參考文獻

張堂賢、黃宏仁(2008)。車輛偵測器資料漏失之在線插補技術。運輸學刊。20(4)，300-320。

Beveridge, S.(1992).Least Squares Estimation of Missing Values in Time Series.Communications in Statistics: Theory and Methods.21(12),3479-3496.

Bellman, R.(1958).On a Routing Problem.Quarterly Applied Mathematics.16(1),87-90.

Bole, V.,Cepar, D.,Radalj, Z.(1990).Estimating Missing Values in Time Series.Methods of Operations Research.226(62),151-163.

Cartwright, M.(1990).Fourier Methods for Mathematicians, Scientists and Engineers.New York:Ellis Horwood.