노드기반과 링크기반 최단경로 탐색알고리듬의 비교연구

펼치기

기존 최단경로 탐색에서 연구된 주요 문제는 회전 금지나 회전 벌점(Turn penalty)을 고려할 수 있는 최단경로탐색 알고리듬을 개발하는 분야였다. Dijkstra 알고리듬(1959)으로 대표되는 수형망 알고리듬(Tree building algorithm)의 경우, 교차로내 좌회전금지, P-turn, U-turn 허용 등 회전제약문제를 최단경로 탐색과정에 효과적으로 고려할 수 없는데, 이는 최단경로를 탐색할 때 사용하는 기본 원리인 Bellman의 최적조건(optimal condition)을 위배되기 때문이다. 이런 회전제약문제를 풀기 위하여 덩굴망(Vine building algorithm) 알고리듬이 개발되었다. 덩굴망 알고리듬은 동일한 노드를 한번 이상 포함할 수 있기 때문이다. 따라서, 좌회전 금지와 같이 회전벌점이 있는 경우에도 최적경로를 찾을 수 있게 된다. 그런데, 연속적으로 회전이 금지된 교통망의 경우 기존 덩굴망 최단경로 알고리듬으로도 정확한 최단경로를 찾지 못한다는 사실이 밝혀졌는데(김익기, 1998), 이는 최적조건을 만족하는 덩굴망 알고리듬이 가능 탐색영역(feasible searching area)을 제한하기 때문이다. 따라서 이를 근본적으로 해결하기 위해서는 네트워크를 확장해야 하는데, 이는 네트워크 수정에 따른 추가시간과 번거로움이 따르게 된다.