A*의 한계와 CCH 기반 Thor 경로탐색 엔진 (2021-12)

기존 A* 엔진의 성능과 확장성

티맵 경로탐색 엔진은 도로 네트워크 그래프 위에서 실시간과 예측 교통정보, 유고정보를 비용으로 바꿔 최소 비용 경로를 찾습니다. 기존 엔진은 Dijkstra에 휴리스틱 함수를 더한 A*였습니다. 휴리스틱은 허용 조건을 만족해야 최단 경로가 보장되고, 조건을 어기면 더 빠르지만 최단 경로를 보장하지 못합니다.

한계는 둘이었습니다. 그래프가 커질수록 느려지는데, 도로가 늘고 사용자가 폭발적으로 늘면서 서울에서 부산까지 탐색하면 요청당 2~3초 이상 걸리는 경우가 간헐적으로 생겼습니다. 또 A*는 목적지 방향으로만 탐색하므로, 택시 배차의 승객 주변 n대 계산이나 물류 경유지 사이 n×m 경로 계산에는 쓸 수 없었습니다.

알고리즘 조사와 CCH 선택

원문은 논문들을 세 갈래로 나눕니다. 목적지 지향 계열은 A*와 ALT가 대표인데 n×m 탐색이 안 돼 제외했습니다. 계층 계열은 노드를 중요도순으로 정렬해 지름길을 만드는 CH, 여기에 실시간 교통 반영용 커스터마이징을 더한 CCH입니다. 분할 계열은 CRP가 대표입니다. CCH와 CRP는 둘 다 n×m 탐색과 큰 성능 향상이 가능했고, 이후 시간 의존 그래프 지원 여부와 구현 용이성을 따져 CCH를 골랐습니다. 이 엔진 프로젝트의 이름이 Thor입니다.

세 단계의 CCH 구조

• 전처리: 맵 데이터가 바뀔 때 비용과 무관하게 지름길을 만듭니다. 보통 2주에 한 번입니다.
• 커스터마이징: 교통정보가 갱신될 때 지름길의 가중치를 고칩니다. 보통 5분에 한 번입니다.
• 쿼리: 위 두 단계로 만든 그래프에서 경로를 찾습니다.

CH와 달리 CCH는 지름길에 비용을 주지 않고 무한대로 두며, 그래서 우회 경로 검사도 하지 않습니다. 노드 정렬은 그래프를 균형 있게 나누는 방식을 써서 지름길 수를 줄이고, 같은 레벨 파티션끼리는 간선이 없으므로 커스터마이징을 병렬로 돌릴 수 있습니다. 분할에는 Inertial Flow를 쓰고 min-cut에는 Dinic 알고리즘을 썼습니다. 전국을 레벨 5 미만으로 나누면 균형 있게 갈라졌다고 합니다.

커스터마이징은 낮은 순위에서 높은 순위로 지름길 비용을 채우는 기본 단계와, 높은 순위에서 낮은 순위로 거치며 불필요한 간선을 지우는 완전 단계로 나뉩니다. 지운 간선 덕에 쿼리가 빨라집니다.

다대다 쿼리와 성능

일대일 탐색은 상향 그래프 정방향, 하향 그래프 역방향의 양방향 Dijkstra입니다. 다대다는 출발지 3곳과 도착지 3곳이면 9번 대신 6번의 Dijkstra로 9개 경로를 얻습니다. 목적지마다 역방향, 출발지마다 정방향으로 최단 경로 트리를 만들고 서로 만나는 지점에서 경로를 이어 붙입니다.

성능은 동일 장비에서 일주일치 사용자 요청을 무작위 추출해 비교했습니다. 지연과 처리량이 모두 크게 좋아졌고, 400km 이상 장거리에서는 거의 100배 이상 빨라졌다고 합니다.

적용 범위

원문은 이용자가 많은 내비게이션에는 바로 적용하지 않고, 빠른 성능이 필요한 고객을 대상으로 티맵 Open API부터 적용했다고 밝혔습니다. 보행자 경로탐색도 Thor에 추가해 연말 서비스를 예정했고, 대리운전과 퀵서비스와 물류에도 쓸 계획입니다. 시간 의존 경로탐색은 후속 글 3시간 뒤 출발 경로탐색에서 이어집니다.