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

간단 소개

티맵의 미래 예측 경로 탐색 엔진인 CATCHUp 알고리즘의 개발 과정과 최적화 기법, 그리고 성능 향상 결과를 설명합니다.

AI Summary

Time-Dependent 경로탐색과 CATCHUp 알고리즘
- Time-Dependent 경로탐색은 도로 탐색 시 각 도로의 진입 시각을 계산하여 예상 시점의 교통정보를 활용하는 방식이다.
- 기존 티맵은 AStar 기반의 Time-Dependent 경로탐색을 제공했으나, 성능 문제로 CCH 기반의 CATCHUp 알고리즘을 도입했다.
- CATCHUp 알고리즘은 CCH를 기반으로 Time-Dependent 경로탐색이 가능하도록 확장되었으며, 3단계(Preprocessing, Time-Dependent Customization, Query)로 구성된다.
CATCHUp 알고리즘의 핵심 아이디어 및 최적화
- CATCHUp 알고리즘은 Shortcut을 구성하는 Witness-Path 변화가 크지 않다는 점을 활용, 모든 Arc의 비용을 저장하는 대신 Witness-Path가 변경되는 시점의 Path만 저장하여 메모리 공간을 확보한다.
- Query 단계에서 Shortcut Unpacking Data로부터 특정 시점의 Witness-Path를 구하고, Unpacking 하여 비용과 경로를 재계산한다.
- Elimination Tree Interval Query, Lazy Shortcut Unpacking, Corridor AStar 등의 최적화 기법을 적용하여 성능을 향상시켰다.
결론 및 향후 계획
- Thor 엔진으로 미래시간 길 찾기를 전환하여 자동차 경로탐색 요청을 효율적으로 처리하고 있으며, 장거리 요청의 응답 성능이 향상되었다.
- Thor 경로탐색 엔진은 사내 외 서비스로 확장되고 있으며, 2023년에는 티맵 내비게이션 실시간 경로안내까지 확장할 예정이다.