교통흐름 예측 결과틀 적용한 동적 최단 경로 탐색 = A dynamic Shortest Path Finding with Forecasting Result of Traffic Flow

국문 초록 (Abstract)

텔레매틱스 서비스 중 가장 보편적으로 사용되는 것이 출발지에서 목적지까지의 최단 경로 안내 서비스이다. 본 논문에서는 미래 시간에 대한 교통흐름 예측 결과를 바탕으로 한 동적 최단 경로 탐색 시스템을 개발하고 실시간교통정보를 이용한 다양한 실험을 수행하여 성능을 분석하였다. 교통흐름 예측은 베이지안 네트워크 (Bayesian network)를 이용한 예측 시스템을 사용하였다. 동일한 출발지와 목적지에 대해 동적 최단 경로와 정적 및 누적 최단 경로를 탐색하고 각 경로에 대한 통행 시간을 계산하여 실제 최단 경로의 통행시간과 비교하였다. 실험 결과 75% 이상의 비율로 동적 최단 경로의 통행시간이 정적이나 누적 최단 경로의 통행시간보다 실제 최단경로의 통행시간에 가깝게 나타났다. 따라서 중간 경유지에 도착 예정인 시간대의 교통 흐름을 예측하여 동적 최단 경로를 구하는 것이 출발시간의 교통흐름을 모든 구간에 적용하여 최단 경로를 구하는 정적 최단 경로에 비해 더 정확한 교통정보를 제공하여 텔레매틱스 서비스의 품질을 향상시킬 수 있음을 보여 주었다.

다국어 초록 (Multilingual Abstract)

One of the most popular services of Telematics is a shortest path finding from a starting point to a destination. In this paper, a dynamic shortest path finding system with forecasting result of traffic flow in the future was developed and various experiments to verify the performance of our system using real-time traffic information has been conducted. Traffic forecasting has been done by a prediction system using Bayesian network. It searched a dynamic shortest path, a static shortest path and an accumulated shortest path for the same starting point and destination and calculated their travel time to compare with one of its real shortest path. From the experiment, over 75%, the travel time of dynamic shortest paths is the closest to one of their real shortest paths than one of static shortest paths and accumulated shortest paths. Therefore, it is proved that finding a dynamic shortest path by applying traffic flows in the future for intermediated intersections can give more accurate traffic information and improve the quality of services of Telematics than finding a static shortest path applying by traffic flows of the starting time for intermediated intersections.

참고문헌 (Reference)

1 강연수, "예측통행시간 기반 동적경로탐색시스템 개발" 154-162, 2004

2 강연수, "승용차 길 안내를 위한 멀티미디어 서비스 체계 개발" 교통개발연구원 2004

3 유영중, "베이지안 네트워크를 이용한 단기 교통정보 예측 모델" 한국해양정보통신학회 13 (13): 765-773, 2009

4 김동호, "고속도로 통행시간 예측을 위한 과거 통행시간 이력 자료 구축에 관한 연구" 197-202, 2005

5 Chun-Hsin Wu, "Travel-Time Prediction With Support Vector Regression" 5 (5): 2004

6 남궁성, "TCS 자료를 이용한 고속도로 통행 시간 예측" 한국도로공사 2000

7 G. Q. Yu, "Short-term traffic flow forecasting based on Markov chain model" 2003

8 Ingrid Flinsenberg, "Route Planning Algorithms for Car Navigation" Technique University Eindhoven 2004

9 Thomas H. Cormen, "Introduction to Algorithm" MIT Press 1994

10 H. D. Chon, "FATES: Finding A Time dEpendent Shortest Path" 2003

11 Road E. Turochy, "Enhancing Short-Term Traffic Forecasting with Traffic Condition Information" 2005

12 Hironobu Kitaoka, "Development of a Travel Time Prediction Method for the TOYOTA G-BOOK Telematics Service" 41 (41): 2007

13 Finn V. Jensen, "An introduction to Bayesian networks" UCL Press 1996

14 Young Jung Yu, "A Short-Term Prediction Model for Forecasting Traffic Information Using Bayesian Network" 247-253, 2008

15 Shiliang Sun, "A Bayesian Network Approach to Traffic Flow" 7 (7): 2006