티맵, 3시간 뒤 출발하면 얼마나 걸려? - 17편-미래예측을 위한 경로탐색엔진 (CATCHUp Algorithm)

티맵은 출발 시간에 따른 소요 시간과 경로를 예측하는 '언제 갈까' 기능을 제공합니다. 이 기능은 티맵의 강점인 실사용자 GPS 데이터 기반 예측 교통정보와 정교한 맵데이터를 활용하여 경로탐색 엔진을 수행합니다.

경로탐색은 도로 네트워크를 그래프로 보고 출발지에서 목적지까지 최소 비용의 최단 경로를 찾는 문제로 정의됩니다. 특히, 시간 의존적인 조건(Time-Dependent)을 추가하여 실제 도로 상황에 가까운 예측을 제공합니다.

이는 출발 시점에 따라 각 도로의 진입 시각을 계산하고, 해당 시점의 교통정보를 활용하는 방식입니다. 기존에는 A* 알고리즘 기반의 Time-Dependent 경로탐색을 제공했지만, 성능 개선을 위해 CCH 기반의 Thor 엔진을 도입하여 CATCHUp 알고리즘을 활용한 새로운 경로탐색 엔진을 개발했습니다.