최소신장트리를 적용한 주행시간 기반 내비게이션의 실시간 최단경로 탐색 (A Real-time Shortest Path Search for Navigation Based on Traveling Time Using the Minimum Spanning Tree)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 12권 / 8호 / 1 ~ 8페이지
· 저자명 : 이상운

초록

사고나 정체 등 상황에 따라 시시각각 변화하는 도로의 차량 주행 속도 정보를 실시간으로 활용하여 최단경로를 재탐색하기 위해서는 빠른 실시간 도로정보 탐색 알고리즘이 요구된다. 본 논문은 주행시간 개념을 도입하여 내비게이션에서 실시간으로 최단 경로를 재탐색하는 알고리즘을 제안하였다. 도로 상황에 따른 실시간 정보를 제공할 수 있는 내비게이션을 구현하기 위해서는 거리 기반의 Dijkstra 알고리즘을 적용할 수 없다. 제안 알고리즘은 모든 노드의 경로 길이를 계산하지 않고, 단지 최소신장트리를 얻는 Borůvka 알고리즘의 변형 형태와 Kruskal 알고리즘을 조합하여 목적지까지의 최단 경로만을 선택하는 기법을 적용하였다. 제안된 알고리즘은 일반적인 도로 상황에서의 최단 경로와 특정 도로에서 사고가 발생하였다고 가정한 경우에 대해 적용성을 검증하였다. 실험 결과 돌발 상황이 발생하여 도로가 정체되었을 때 우회하여 목적지 까지 최단시간 내에 도달 할 수 있는 경로를 쉽고 빠르게 찾음을 증명하였다.

영어초록

Under the pressure of potential contingencies such as sudden accidents or congested traffic, a demand for a fast search algorithm seems natural as it has become integral to navigation systems which require real-time road information. This paper therefore deals with a newly devised algorithm based on a transit time concept that researches the shortest path real-time in Navigation system. A distance information-based Dijkstra’s algorithm making it unlikely for it to offer a speedy information in real-time road situation. It is also rendered obsolete in the face of changing vehicle speeds subject to road conditions. The proposed algorithm thus disregards calculations of all nodes but rather incorporates both the Borůvka algorithm of the minimum spanning tree and a modified Kruskal algorithm in order to selectively determine the shortest path to a desired destination. To verify its applicability, I test the proposed algorithm on a case in which an accident occurs on both the shortest path and a specific road. The test results prove that the algorithm has been successful in expeditiously obtaining a detour that results in the shortest transit time.

참고자료

· 없음