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

Development of Time-dependent Backward Route Planning System

闕嘉宏(Chia-Hung Chueh)

指導教授 ： 張堂賢

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

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

摘要

本研究結合路徑演算、旅行時間預測以及漏失資料插補等三大模組，開發出一套依時性後推式路徑演算系統。有別於先前路徑演算研究，本系統採用後推式路徑規劃作為資訊提供，讓使用者於行程選擇上變成主動決策者。演算過程中，以A*演算法為邏輯基礎，導入旅行成本、延滯成本與轉向成本等交通特性；旅行成本採用時間特性取代空間特性，透過卡曼濾波器與傅立葉轉換技術，對系統進行長短期預測與門檻值設計；線上資料插補技術能克服漏失資料狀態，將歷史資料與即時資料走勢進行結合並獲得良好的插補績效。上述成果皆以JAVA程式語言進行開發，搭配基因演算法對各模型所需參數進行最佳化訓練，其成果將可輔助相關系統突破前推式演算思維，讓使用者依照預期抵達時間需求，獲得有效且穩定的建議出發時間與路徑。

關鍵字

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

並列摘要

This paper integrates route planning, travel-time prediction and missing-data interruption modules, to develop a time-dependent backward route planning system. Comparing with previous researches, this system leads a backward searching concept in A* algorithm, replaces spacing cost with travel-time and delay cost. By Kalman filter and Fourier transform, system is able to operate prediction and threshold design for short and long terms. The data interruption module resists situations of missing-data, avoids the afterward prediction failed. The large scale of historical data figures out to satisfy the requirement of unbiased estimation in statistics. All of above programs are created by JAVA, adjusted parameters of model needed with Genetic algorithms. This system can help travelers to obtain a flexible suggestion in travel path and departure-time via expected arrival-time.

並列關鍵字

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

參考文獻

6.葉羿稚 (2007)，行前即時路徑規劃演算法之研究，國立台灣大學土木工程學系碩士論文。

7.張堂賢、黃宏仁 (2008)，「車輛偵測器資料漏失之在線插補技術」，運輸學刊，第二十卷第四期，頁300-320。

15.Clark, S.D., Watson, S., Redfern, E. and Tight, M.R. (1993), “Application of Outlier Detection and Missing Value Estimation Techniques to Various Forms of Traffic Count Data,” Working Paper. Institute of Transport Studies, University of Leeds, Leeds, UK.

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

10.Bole, V., Cepar, D., and Radalj, Z. (1990), “Estimating Missing Values in Time Series,” Methods of Operations Research, Vol. 226, No. 62, pp. 151-163.