Title

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

Translated Titles

Development of Time-dependent Backward Route Planning System

DOI

10.6342/NTU.2012.00668

Authors

闕嘉宏

Key Words

後推式路徑演算法 ; 旅行時間預測 ; 漏失資料插補 ; 卡曼濾波器 ; 傅立葉轉換 ; Backward route planning ; Travel time prediction ; Missing data interpolation ; Kalman Filter ; Fourier transforms

PublicationName

臺灣大學土木工程學研究所學位論文

Volume or Term/Year and Month of Publication

2012年

Academic Degree Category

博士

Advisor

張堂賢

Content Language

繁體中文

Chinese Abstract

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

English Abstract

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.

Topic Category 工學院 > 土木工程學研究所
工程學 > 土木與建築工程
Reference
  1. 6.葉羿稚 (2007),行前即時路徑規劃演算法之研究,國立台灣大學土木工程學系碩士論文。
    連結:
  2. 7.張堂賢、黃宏仁 (2008),「車輛偵測器資料漏失之在線插補技術」,運輸學刊,第二十卷第四期,頁300-320。
    連結:
  3. 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.
    連結:
  4. 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.
    連結:
  5. 11.Cartwright, M. (1990), Fourier Methods for Mathematicians, Scientists and Engineers, Ellis Horwood.
    連結:
  6. 13.Chen, H., Susan G. M., Mussone L., and Montgomery, F. (2001), “A Study of Hybrid Neural Network Approaches and the Effects of Missing Data on Traffic Forecasting,” Neural Computing & Applications, Vol. 10, No. 3, pp. 277-286.
    連結:
  7. 14.Chen, M. and Chien S. I. J. (2001), “Dynamic Freeway Travel Time Prediction Using Probe Vehicle Data: Link-based vs. Path-based,” 80th Annual Meeting of Transportation Research Board, Washington, D.C.
    連結:
  8. 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. 16.Daganzo, C. F. (2002), “Reversibility of the time-dependent shortest path problem”, Transportation Research Part B, Vol. 36, pp. 665-668.
    連結:
  10. 19.Dia Hussein (2001), “An object-oriented neural network approach to short-term traffic forecasting,” European Jurnal of Operation Research, Vol. 131, pp. 253-261.
    連結:
  11. 21.Gold, M. S., and Bentler, P. M. (2000), “Treatments of missing data: A Monte Carlo comparison of RBHDI, iterative stochastic regression imputation, and expectation-maximization,” Structural Equation Modeling, Vol. 7, pp. 319-355.
    連結:
  12. 22.Goldberg, D. E. (1989), Genetic Algorithms in Search, Optimization & Machine Learning, Boston: Addison Wesley Longman Inc.
    連結:
  13. 25.Li Q., Li L., Yi Z., and Hu, J. (2009), “PPCA-Based Missing Data Imputation for Traffic Flow Volume: A Systematical Approach”, IEEE Transactions on Intelligent Transportation Systems, Vol. 10, No. 3, pp. 512-522.
    連結:
  14. 26.Coifman, B. (1998), “Vehicle reidentification and travel time measure in real-time on freeway using the existing loop detector infrastructure,” Transportation Research Record, Vol. 1643, pp. 181-191.
    連結:
  15. 27.Hall, N., Hahn, P. M. and Grant, T. L. (1998), “A Branch-and-Bound Algorithm for the Quadratic Assignment Problem Based on the Hungarian Method,” European Journal of Operational Research, vol. 108, pp. 629-640
    連結:
  16. 28.HCM (2000), Highway Capacity Manual 4th Edition, Transportation Research Board, National Research Council, Washington, D. C.
    連結:
  17. 29.HCM (2010), Highway Capacity Manual 5th Edition, Transportation Research Board, National Research Council, Washington, D. C.
    連結:
  18. 30.Hollane, J. H. (1975), Adaptation in Natural and Artificial Systems, Ann Arbor, Michigan: University of Michigan Press.
    連結:
  19. 31.Huang, C. C., and Lee, H. M. (2004), “A Grey-Based Nearest Neighbor Approach for Missing Attribute Value Prediction,” Applied Intelligence, Vol. 20, No. 3, pp. 239-252.”
    連結:
  20. 32.Van Hinsbergen, C. P. IJ. and Van Lint, J. W. C. (2008), “Bayesian Combination of Travel Time Prediction Models,” Transportation Research Record: Journal of the Transportation Research Board, Vol. 2064, pp. 73-80.
    連結:
  21. 33.Ishak, S. and Alecsandru, C. (2004), “Optimizing traffic prediction performance of neural networks under various topological, input, and traffic condition settings,” Journal of Transportation Engineering, Vol. 130, No. 4, pp. 452-465.
    連結:
  22. 34.Kaan, E. and Altintas, A. (2001), “High speed CNC system design. Part I: jerk limited trajectory generation and quintic spline interpolation,” International Journal of Machine Tools & Manufacture, Vol. 41, pp. 1323-1345.
    連結:
  23. 35.Kershenbaum, A. (1981), “A note on finding shortest path trees,” Networks, Vol. 11, pp. 399-400.
    連結:
  24. 36.Klunder, G. A. and Post, H. N. (2006), “The Shortest Path Problem on Large-Scale Real-Road,” Networks, Vol. 48, pp.182-194.
    連結:
  25. 37.Kwon, J., Coifman, B., and Bickel, P., (2000), “Day-to-Day Travel Time Trends and Travel Time Prediction from Loop Detector Data,” Transportation Research Record, No. 1717, pp. 120-129.
    連結:
  26. 40.Makridakis, S. and Fildes, R. (1995), “The Impact of Empirical Accuracy Studies On Time Series Analysis and Forecasting,” International Statistical Review, Vol. 63, No. 3, pp. 289-308.
    連結:
  27. 41.Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs 3rd Edition, Springer.
    連結:
  28. 42.Nam D. H. and Drew D. R. (1998), “Analyzing Freeway Traffic under Congestion: Traffic Dynamics Approach,” Journal of Transportation Engineering, pp. 208-212.
    連結:
  29. 45.Pallottino S. and Scutella M. G. (1998), Shortest path algorithms in transportation models: classical and innovative aspects, Equilibrium and Advanced Transportation Modeling, pp. 245-281.
    連結:
  30. 46.Paterson, D. and Rose, G. (2008), “A recursive, Cell Processing Model for Predicting Freeway Travel Times,” Transportation Research C, Vol. 16, pp. 432-453.
    連結:
  31. 47.Peeta, S. and Anastassopoulos, L. (2002), “Automatic Real-time Detection and Correction of Erroneous Detector Data with Fourier Transforms for Online Traffic Control Architectures,” Transportation Research Record, Vol. 1811, pp. 1-11.
    連結:
  32. 48.Rice, J. and van Zwet, E. (2004), “A Simple and Effective Method for Predicting Travel Times on Freeways,” IEEE Transactions on Intelligent Transportation Systems, Vol. 5, No. 3, pp. 200-207.
    連結:
  33. 50.Rubin, D. B. (1976), “Inference and Missing Data,” Biometrika, Vol. 63, No. 3, pp. 581-592.
    連結:
  34. 51.Sharma, S., Zhong, M., and Lingras, P. (2003), “Estimation of missing traffic counts using factor, genetic, neural, and regression techniques,” Transportation Research Part C, Vol. 12, No.2, pp. 139-166.
    連結:
  35. 52.Singh, V. P. and Harmancioglu, N. B. (1996), Estimation of missing values with use of entropy, NATO Advanced Research Workshop, Izmir, Turkey, pp. 267-274.
    連結:
  36. 54.Smith, G. C., Wood, A. M., Pell, J. P., White, I. R., Crossley, J. A., and Dobbie, R. (2004), “Second-Trimester Maternal Serum Levels of Alpha-Fetoprotein and the Subsequent Risk of Sudden Infant Death Syndrome,” New England Journal of Medicine, Vol. 351, pp. 978–986.
    連結:
  37. 56.Sun, S. L. and Zhang, C. S. (2007), “The selective random subspace predictor for traffic flow forecasting,” IEEE Transactions on Intelligent Transportation Systems, Vol. 8, No. 2, pp. 367-373.
    連結:
  38. 57.Van Lint, J. W. C., Hoogendoorn, S. P. and van Zuylen, H. J. (2002), “Freeway travel time prediction with state-space neural networks-Modeling state-space dynamics with recurrent neural networks,” Transportation Research Record, Vol. 1811, pp. 30-39.
    連結:
  39. 58.Wei, C. H. and Lee, Y., (2007), “Development of freeway travel time forecasting models by integrating different sources of traffic data,” IEEE Transactions on Vehicular Technology, Vol. 56, No. 6, pp. 3682-3694.
    連結:
  40. 61.Zunxiong Liu, Zhang, D., Liu, Z., and Liao, H. (2009), “Multi-scale Combination Prediction Model with Least Square Support Vector Machine for Network Traffic,” Computer Science, Vol. 3498, pp. 385-390.
    連結:
  41. 62.Zhong, M., Lingras, P., and Sharma, S. (2004), “Estimation of Missing Traffic Counts Using Factor, Genetic, Neural, and Regression Techniques,” Transportation Research Part C, Vol. 12, No. 2, pp. 139-166.
    連結:
  42. 63.Ziliaskopoulos, A. K. and Mahmassani, H. S. (1996), “A note on last time path computation considering delays and prohibitions for interection movements,” Transportation Research Part B, Vol. 30, No. 5, pp. 359-367.
    連結:
  43. 1.李俊賢 (1996),在靜態模型中運用傅立葉轉換分析隨機性動態旅行時間之研究,國立台灣大學土木工程學系碩士論文。
  44. 2.陳慧琪 (1999),時間相依最短路徑問題演算方法之研究,國立交通大學運輸工程與管理系碩士論文。
  45. 3.郭中天 (2002),公車到站時間暨複合路線旅行時間預估模式之研究,國立台灣大學土木工程學系碩士論文。
  46. 4.江文聲 (2001),動態隨機時間相依路網可靠路徑選擇,國立台灣大學土木工程學系碩士論文。
  47. 5.邱妍菁 (2006),高速公路短期交通資訊之灰預測模型,私立逢甲大學交通工程與管理所碩士論文。
  48. 8.Arem Van, B., Vlist Van der, Muste M. J. M., Ruiter M., De, J. C. C., Smulders, S.A. and DOUGHERTY, M. S. (1994), “Models for monitoring the current and expected traffic state on inter-urban motorways,” 1st World Congress on Applications of Transport Telematics and Intelligent Vehicle-Highway Systems, Vol. 3, pp. 1186-1201.
  49. 12.Chandra Mouly, and Chien, Steven I.J., (2002), “Development of a Hybrid Model for Dynamic Travel Time Prediction,” 81th Annual Meeting of Transportation Research Board, Washington D.C.
  50. 17.Delurgio, S. A. (1998), Forecasting Principles and Applications, McGraw-Hill.
  51. 18.DeVellis, R. F. (1991), Scale development theory and applications, Newbury, CA: Sage.
  52. 20.ESRI (2010), ArcGIS Desktop 9.3 Help: Network Analyst, Retrieved March 8, 2011, website: http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm.
  53. 23.Gupta, A., and Lam, M. S. (1996), “Estimating Missing Values Using Neural Networks,” Journal of the Operation Research Society, Vol. 47, No. 2, pp. 229-238.
  54. 24.Lewis, C. D. (1982), Industrial and Business Forecasting Method, Southampton: The Camelot Press Ltd.
  55. 38.Little, R. A. and Rubin, D. B. (1987), Statistical Analysis with Missing Data, New York: Wiley.
  56. 39.Matsumura, S., Yamashita, H., Iwaki, S. and Sugimura, H. (1998), “Experimental Verification of Travel-time Prediction Method,” 5th ITS World Congress.
  57. 43.Oh, J. S., Jayakrishnan, R., and Recker, W. (2002), “Section Travel Time Estimation from Point Detection Data,” Proceedings of the 82th Annual Meeting of Transportation Research Board, Washington, D. C., U.S.A.
  58. 44.Park, D., Rilett, L. R., and Han, G. (1998), “Forecasting multiple-period freeway link travel times using neural networks with expanded input nodes,” Proc., 5th Int. Conf. of Advanced Technol, Application in Transp. Engrg., pp. 325–332.
  59. 49.Ross, P. (1982), “Exponential filtering of traffic data,” Transportation Research Record, Vol. 869, pp. 43-49.
  60. 53.Singh, A. K. and Ghassan, A. L. (2007), State Space Neural Networks for Travel Time Predictions in Signalized Networks, Proceeding of the Transportation Research Board Annual Meeting, National Academies Press, Washington, DC, USA.
  61. 55.Sturtevant, N. and Buro, M. (2005), Partial pathfinding using map abstraction and refinement, Proceedings of the Artificial Intelligence, pp. 47-52.
  62. 59.Wen, Y. H., Lee, T. T., and Cho, H. J. (2005), “Missing data treatment and data fusion toward travel time estimation for ATIS,” Transportation Research Part E, Vol. 39, No. 6, pp.417-444.
  63. 60.Wright, P. M. (1993), “Filling in the Blanks: Multiple Imputation for Replacing Missing Values in Survey Data,” Proceedings of the SAS 18th Annual Conference, New York.
  64. 64.Ziliaskopoulos, A. K. and S. Lee. (1997), “A Cell Transmission Based Assignment-Simulation Model for Integrated Freeway/Surface Street Systems,” Transportation Research Record, No. 1701, pp. 2-23.
Times Cited
  1. 賴勁丞(2016)。基於站點相依性之公共自行車調度策略研究。臺灣大學土木工程學研究所學位論文。2016。1-95。 
  2. 楊傑理(2013)。國道旅行時間資訊之時空無縫演算模型。臺灣大學土木工程學研究所學位論文。2013。1-93。 
  3. 劉姿君(2013)。基於號誌因子之公車動態旅行時間預估模式研究。臺灣大學土木工程學研究所學位論文。2013。1-104。