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

Abstract

本研究結合路徑演算、旅行時間預測以及漏失資料插補等三大模組，開發出一套依時性後推式路徑演算系統。有別於先前路徑演算研究，本系統採用後推式路徑規劃作為資訊提供，讓使用者於行程選擇上變成主動決策者。演算過程中，以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.