Telematics is expected to be one of the fastest growing businesses in information technology area. It may create a new emerging market in industry related to automotive, telecommunications, and information services. Especially vehicle navigation service is considered as a killer application among telematics service applications. The current vehicle navigation service typically recommends a single path that is based on the traveling time or distance from the origin to the destination. The system provides two options for users to choose either via highway or via any road. Since the traffics and road conditions of big cities are very complicated and dynamic, the demand of multi-path guidance system is increasing in telematics market. The multi-path guidance system should allow drivers to choose a path based on their individual preferences such as traveling time, distance, or route familiarity. Using the Lawler’s algorithm, it is possible to find multiple paths; however, due to the lengthy computational time, it is not suitable for the real-time services. This study suggests a computationally feasible and efficient heuristic KSP (K-Shortest Paths) algorithm that is reliable for the real-time vehicle navigation services.
본 논문은 텔레메틱스 서비스 중 경로 안내 서비스에 필요한 다중 경로 발생 알고리즘을 기존의 알고리즘의 계산시간보다 빠른 휴리스틱 알고리즘을 개발함으로써, 실시간 복수 경로 안내 서비스 활용을 위한 보다 실용적인 알고리즘으로 활용할 수 있는 기반을 제공한다. 다중 경로 안내 서비스 구현을 위해서 사용될 수 있는 다중 최단 경로 (K Shortest Paths: 이하 KSP) 알고리즘들은 이미 많이 제시되어 활발히 연구되고 있다. 그러나 실시간 서비스인 차량 경로 안내 서비스에 적용하기에는 알고리즘 계산 시간이 길다는 치명적인 약점을 가지고 있다. 수백개 단위의 노드로 구성된 네트워크에서는 기존의 KSP 알고리즘의 적용이 가능하나, 대도시의 예로 보면 현재 실제 네트워크는 적게는 수천개, 많게는 수만개의 노드로 구성되어 있기 때문에, 기존의 KSP 알고리즘을 적용하기에는 한계를 지니고 있다. 이에 본 논문에서는 실시간 다중 경로 안내 서비스 구현에 기여하기 위해, 기존 KSP 알고리즘 보다 계산 속도가 빠른 휴리스틱 다중 경로 탐색 알고리즘 개발에 대해 역점 두었다.
