네비게이션의 최단 경로 탐색 알고리즘은 일반적으로 Dijkstra 알고리즘에 기반을 두고 있으며, 가중치로 단지 길이 (거리) 만을 고려하고 있다. 거리 기반의 Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 또한, 거리에만 기반하기 때문에 전방에 차량사고로 인해 병목현상이 발생하였을 때 우회도로를 탐색하는 기능이 없어 항상 동일한 경로만을 탐색한다. 이러한 문제점을 해결하고자, 본 논문은 도로 등급 (고속도로, 국도, 지방도 등)을 고려하지 않고, 속도 기준 (원활, 지체 서행, 정체, 사고 통제 등)도 적용하지 않으며, 단지 도로별 주행시간 (주행속도 ${\times}$ 거리)을 고려한다. 이는 사고, 지체, 공사 등으로 인해 동일한 거리의 도로도 다른 시간이 소요되는 현실성을 반영하여 우회도로를 탐색할 수 있는 장점이 있다. 제안된 알고리즘은 특정 도로에서 사고가 발생하였다고 가정한 경우에도 도로의 통행속도를 실시간으로 반영함으로서 돌발지점을 우회하여 목적지 까지 최단시간 내에 도달 할 수 있음을 증명하였다.
네비게이션의 최단 경로 탐색 알고리즘은 일반적으로 Dijkstra 알고리즘에 기반을 두고 있으며, 가중치로 단지 길이 (거리) 만을 고려하고 있다. 거리 기반의 Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 또한, 거리에만 기반하기 때문에 전방에 차량사고로 인해 병목현상이 발생하였을 때 우회도로를 탐색하는 기능이 없어 항상 동일한 경로만을 탐색한다. 이러한 문제점을 해결하고자, 본 논문은 도로 등급 (고속도로, 국도, 지방도 등)을 고려하지 않고, 속도 기준 (원활, 지체 서행, 정체, 사고 통제 등)도 적용하지 않으며, 단지 도로별 주행시간 (주행속도 ${\times}$ 거리)을 고려한다. 이는 사고, 지체, 공사 등으로 인해 동일한 거리의 도로도 다른 시간이 소요되는 현실성을 반영하여 우회도로를 탐색할 수 있는 장점이 있다. 제안된 알고리즘은 특정 도로에서 사고가 발생하였다고 가정한 경우에도 도로의 통행속도를 실시간으로 반영함으로서 돌발지점을 우회하여 목적지 까지 최단시간 내에 도달 할 수 있음을 증명하였다.
The shortest path search algorithm of navigation is generally based on Dijkstra algorithm and considers only the distance using the weight. Dijkstra algorithm based on the distance mainly ought to perform the 'number of nodes 1' and requires a lot of memory, for it is to start from the starting node...
The shortest path search algorithm of navigation is generally based on Dijkstra algorithm and considers only the distance using the weight. Dijkstra algorithm based on the distance mainly ought to perform the 'number of nodes 1' and requires a lot of memory, for it is to start from the starting node and to decide the shortest path for all the nodes. Also, it searches only the same identical path in case of any bottleneck due to an accident nearby, since it is based only on the distance, and hence does not have a system that searches the detour road. In order to solve this problem, this paper considers only the travelling time per road (travelling speed * distance), without applying speed criteria (smoothness, slow speed, stagnation and accident control) or road class (express road, national road and provincial road). This provides an advantage of searching the detour, considering the reality that there are differences in time take for the car to travel on different roads with same distance, due to any accident, stagnation, or repair construction. The suggested algorithm proves that it can help us to reach the destination within the shortest time, making a detour from any congested road (outbreak) on providing an information on traveling time continuously(real-time) even though there is an accident in a particular road.
The shortest path search algorithm of navigation is generally based on Dijkstra algorithm and considers only the distance using the weight. Dijkstra algorithm based on the distance mainly ought to perform the 'number of nodes 1' and requires a lot of memory, for it is to start from the starting node and to decide the shortest path for all the nodes. Also, it searches only the same identical path in case of any bottleneck due to an accident nearby, since it is based only on the distance, and hence does not have a system that searches the detour road. In order to solve this problem, this paper considers only the travelling time per road (travelling speed * distance), without applying speed criteria (smoothness, slow speed, stagnation and accident control) or road class (express road, national road and provincial road). This provides an advantage of searching the detour, considering the reality that there are differences in time take for the car to travel on different roads with same distance, due to any accident, stagnation, or repair construction. The suggested algorithm proves that it can help us to reach the destination within the shortest time, making a detour from any congested road (outbreak) on providing an information on traveling time continuously(real-time) even though there is an accident in a particular road.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
3장에서는 주행시간에 기반한 빠른 최단경로 탐색 알고리즘을 제안한다. 또한, 사고나 정체 등으로 인해 돌발 상황이 발생할 경우 정체구간을 우회하여 목적지 까지 최단 경로를 탐색할 수 있는지 검증한다.
결국, (14, 18 ) 도로를 통과하지 못하여 목적지에 도달하지 못하는 상황이 발생한다. 반면에, 주행시간 기반의 TSP 알고리즘을 적용할 경우 (14, 18 ) 도로를 우회할 수 있는지 고찰해보자.
본 논문에서는 네비게이션에 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 고찰해보고 새로운 최단 경로 탐색 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 모든 노드들을 한번에 하나씩 방문하는 방법으로 알고리즘 수행속도가 느린 단점이 있다.
본 논문은 TPEG의 기능을 최대한 발휘하도록 빠른 시간 내에 최단경로를 탐색하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프의 출발 노드부터 목적지 노드까지의 레벨을 설정하고, 불필요한 노드와 호들을 3단계로 제거하여 최소한의 노드와 호들만을 대상으로 최단경로를 선택함으로서 실시간으로 탐색 정보를 제공할 수 있는 장점을 갖고 있다.
본 논문은 도로 등급과 속도 구분 기준을 적용하지 않으며 도로별 차량의 주행시간 (Traveling Time) 개념에 기반하여 실시간으로 최단 우회 경로를 탐색할 수 있는 알고리즘을 제안한다. 이 알고리즘의 특징은 기존의 길이 개념 대신 주행시간을 적용한다.
가설 설정
1 노드에서 출발하여 30 노드에 도착한다고 가정하여 보자. 출발 노드에서 목적지 노드까지의 최단거리를 갖는 경로를 Dijkstra 알고리즘으로 찾는 과정은 표 1에, 최단경로는 그림 3에 제시되어 있다.
그림 2의 G1 그래프에서 현재 (1, 3 ) 도로를 운행 중에 (14, 18 ) 도로에서 사고가 발생하여 (14, 18 ) 도로가 폐쇄 (삭제)되고, 이로 인해 (18, 14 )과 14와 18 노드로 유입되는 (8, 14 ), (9, 14 ), (13, 14 ), (15, 14 ), (17, 18 )과 (22, 18 ) 도로에 정체 현상이 발생하여 주행속도는 5 Km/h라 가정하여 보자. 이 경우 각 도로별 주행 시간은 그림 8과 같다.
초기 조건으로 n × n 가중치 호 정방행렬을 작성하였다고 가정한다.
제안 방법
방향그래프의 점대점 최단거리를 빠르게 탐색하기 위해 먼저, 그래프의 노드들을 S, P와 D의 3 그룹으로 분류한다. 여기서 S는 출발 노드, D는 목적지 노드이며, P는 출발과 목적지 노드를 제외한 그래프의 모든 경로노드들이라 하자.
본 논문은 TPEG의 기능을 최대한 발휘하도록 빠른 시간 내에 최단경로를 탐색하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프의 출발 노드부터 목적지 노드까지의 레벨을 설정하고, 불필요한 노드와 호들을 3단계로 제거하여 최소한의 노드와 호들만을 대상으로 최단경로를 선택함으로서 실시간으로 탐색 정보를 제공할 수 있는 장점을 갖고 있다.
이론/모형
그림 2의 G1 그래프에 대해 Dijkstra 알고리즘[5]을 적용하여 보자. G1 그래프는 Lee[8]에서 인용되었으며, 이 도시는 30개의 노드 (교차로)와 41개의 양방향 도로, 11개의 일방통행로로 구성되어 통행 가능한 도로 (호)는 93개이다.
성능/효과
(1) 출발 노드에서 목적지 노드까지 주행함에 있어 역 방향 도로 (목적지에서 출발지로)는 주행하지 않으므로 역-레벨로 향하는 호를 삭제한다. (2) 그 결과, 유출 차수 do와 유입 차수 di가 0인 경로 노드가 존재하면 행과 열을 모두 삭제한다. di = 0인 노드는 결코 도달할 수 없는 노드이며, do = 0인 노드는 더 이상 다른 도로로 갈 수 없어 해당 노드의 모든 유입 호들을 삭제가 가능하다.
그러나 출발과 목적지 노드 연결 호들은 가중치가 최소가 되지 않더라도 경로 노드들에 의해 최단 경로로 선택 될 수 있으므로 최소 가중치 호를 2개 선택한다. (3) 유출 차수 do와 유입 차수 di가 0인 경로노드의 행과 열을 모두 삭제한다. 이 단계에서 그래프가 2차적으로 단순화된다.
Dijkstra 알고리즘의 문제점은 첫 번째로, 알고리즘 수행에 많은 메모리를 요구하며 일반적으로 n - 1개의 정점을 모두 방문해야 하기 때문에 그래프 크기가 클 경우 실시간으로 정보를 제공하기가 어렵다. 두 번째로, 네비게이션의 최단경로는 단일 출발점과 단일 목적지를 대상으로 하는 점대점 (Point-to-Point, P2P) 최단경로를 찾는 문제로 Dijkstra 알고리즘을 적용할 경우 최단 경로 상에 있지 않는 불필요한 노드들의 경로 길이를 계산하는 단점이 있다. 세 번째로, 기존의 모든 알고리즘은 호의 가중치로 거리를 적용하기 때문에 최단 경로 상에서 정체 또는 사고가 발생하여도 항상 동일한 경로를 제공하기 때문에 우회도로를 재탐색하지 못하여 이용자의 만족도를 높일 수 없다.
또한, 목적지까지 경로 탐색에 있어 불필요한 노드와 호들을 가급적 많이 제거하여 알고리즘 수행 시간을 단축시킬 수 있다. 따라서 제안된 알고리즘은 실시간 교통상황을 입력 받아 도로별 주행시간을 계산하여 최단 시간 내에 목적지까지 우회할 수 있는 경로를 제공할 수 있다.
두 번째로, 네비게이션의 최단경로는 단일 출발점과 단일 목적지를 대상으로 하는 점대점 (Point-to-Point, P2P) 최단경로를 찾는 문제로 Dijkstra 알고리즘을 적용할 경우 최단 경로 상에 있지 않는 불필요한 노드들의 경로 길이를 계산하는 단점이 있다. 세 번째로, 기존의 모든 알고리즘은 호의 가중치로 거리를 적용하기 때문에 최단 경로 상에서 정체 또는 사고가 발생하여도 항상 동일한 경로를 제공하기 때문에 우회도로를 재탐색하지 못하여 이용자의 만족도를 높일 수 없다.
이는 정상 상태의 교통 흐름과 돌발 상황 발생을 가정한 2개 경우에 대해 검증하였다. 제안된 알고리즘 검증 결과 최단 시간 내에 목적지 까지 도달 가능한 경로를 탐색하는데 성공하였다. 제안된 알고리즘을 추후 실제 TPEG 네비게이션에 도입하여 고객의 만족도를 얼마나 높일 수 있는지 검증할 계획이다.
제안된 알고리즘은 기존의 거리 정보 대신 주행 시간 개념을 도입함으로서 실시간 교통정보를 활용할 수 있는 효과를 얻었다. 이는 정상 상태의 교통 흐름과 돌발 상황 발생을 가정한 2개 경우에 대해 검증하였다.
후속연구
제안된 알고리즘 검증 결과 최단 시간 내에 목적지 까지 도달 가능한 경로를 탐색하는데 성공하였다. 제안된 알고리즘을 추후 실제 TPEG 네비게이션에 도입하여 고객의 만족도를 얼마나 높일 수 있는지 검증할 계획이다.
질의응답
핵심어
질문
논문에서 추출한 답변
Dijkstra 알고리즘이란 무엇인가?
이와 같은 이유로 내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되고 있다.[1,6,7] Dijkstra 알고리즘은 양의 가중치를 갖는 호들로 구성된 방향 그래프에 대해 단일 출발 노드부터 다른 모든 노드까지의 최단 경로 (Single-Source Shortest Path)를 찾는 알고리즘이다[3-5].
방향 그래프는 어디에 활용되는가?
방향 그래프는 최단 경로 (Shortest Path, SP)와 임계 경로 (Critical Path, CP) 등을 구하는데 활용된다. 본 논문은 최단 경로에 초점을 맞춘다.
내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되는 이유는 무엇인가?
[1,2] 이들 알고리즘은 일반적으로 호의 가중치로 거리 (Length) 정보를 활용한다. Bellman Ford 알고리즘은 그래프 크기가 커짐에 따라 Dijkstra 알고리즘보다 많은 시간이 소요되지만 좋은 결과를 얻을 수 있다. 위상순서 알고리즘은 선형 시간대에 최단 경로를 찾을 수 있지만 최적의 경로를 찾지 못할 수 도 있다. A* 알고리즘은 Dijkstra 알고리즘과 같이 좋은 결과를 얻으며 메모리를 적게 요구하지만 알고리즘 구현이 보다 어렵다. 이와 같은 이유로 내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되고 있다.
참고문헌 (8)
M. Abboud, L. Mariya, A. Jaoude, and Z. Kerbage, "Real Time GPS Navigation System," 3rd FEA Student Conference, Department of Electrical and Computer Engineering, American University of Beirut, 2004.
T. H. Cormen, C. E. Leserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 2nd Edition, MIT Press and McGraw-Hill, 2001.
E. W. Dijkstra, "A Note on Two Problems in Connection with Graphs," Numerische Mathematik, Vol. 1, pp. 269-271, 1959.
Wikipedia, "Dijkstra's Algorithm," http://en.wikipedia.org/wiki/Dijkstra_algorithm, Wikimedia Foundation Inc., 2012.
J. Misra, "A Walk Over the Shortest Path: Dijkstra's Algorithm Viewed as Fixed-Point Computation," Department of Computer Science, University of Texas at Austin, USA, 2000.
Y. T. Lim and H. M. Kim, "A Shortest Path Algorithm for Real Road Network Based on Path Overlap," Department of Civil Engineering, Institute of Transportation Studies, University of California, Irvine, USA, http://www.its.uci.edu/-hyunmyuk/library/(2005)20EAST(k-path). pdf, 2005.
F. B. Zhan, "Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures," Journal of Geographic Information and Decision Analysis, Vol. 1, No. 1, pp. 69-82, 1997.
K. S. Lee, "Shortest Path Algorithm," http://www.geocities.com/leekinseng1/
※ AI-Helper는 부적절한 답변을 할 수 있습니다.