티맵, 3시간 뒤 출발하면 얼마나 걸려?
17편-미래예측을 위한 경로탐색엔진 (CATCHUp Algorithm)
티맵 언제 갈까 소개
티맵의 신규 경로탐색 엔진 Thor 1편 '번개처럼 빠른 경로탐색엔진'에 이어 신규 개선한 2편 ‘언제 갈까’ 기능을 소개합니다.
티맵은 출발 시간에 따른 소요시간과 경로를 예측할 수 있는 기능을 제공하고 있습니다. 목적지를 선택한 후 출발 시간을 변경해가며 확인할 수 있는데요. 출퇴근, 주말 가족나들이, 명절 장거리 운행 등 미래 계획이 있을 때 많은 분들이 유용하게 활용하고 계시죠.
소요시간과 경로를 구하기 위해 티맵의 강점인 ‘많은 실사용자들의 GPS 데이터에 기반한 예측 교통정보’와 ‘풍부하고 정교한 맵데이터’를 활용해 경로탐색 엔진을 수행합니다.
Time-Dependent 경로탐색이란
1편에서 언급했던 경로탐색에 대한 정의를 참고합니다.
도로네트워크를 기반으로 다양한 정보(교통정보, 유고정보 등)를 수집하고, 해당 정보들을 비용(Cost)으로 환산하여 경로탐색에 이용하고 있습니다.
이를 알고리즘 문제로 정의한다면 Road Network로 생성된 Graph 구조에서 Source(출발지), Target(목적지)가 주어졌을 때, Source → Target까지 최소의 비용으로 이동 가능한 Shortest Path를 찾는 문제로 정의할 수 있습니다.
출발지→도착지의 경로탐색 시 여러 가지 정보를 비용으로 환산하여 최적의 경로를 찾게 되는데, 실 세계에 가까운 결과에 다가가기 위해 비용 계산에 시간 의존적(Time-Dependent)인 조건이 추가됩니다.
Time-Dependent 경로탐색이란 출발지로부터 도로를 탐색(확장)하면서 각 도로의 진입 시각을 계산하여 예상 시점의 교통정보, 유고정보 등을 활용하는 경로탐색을 말합니다. 예를 들면, 서울→부산 경로를 오전 9시 30분 출발하는 것으로 요청한 경우, 중간 대구 근처 도로 탐색 시 예상 시점인 오후 1시 정도의 정보를 활용하게 되는 것입니다.
CATCHUp 알고리즘을 이용한 Time-Dependent 경로탐색엔진 개발
전통적인 단방향 Dijkstra, AStar 알고리즘으로 Time-Dependent 경로탐색을 구현하는 것은 비교적 어렵지 않습니다. Graph 탐색 시 만나는 각 도로별 예상 소요시간을 더해가면서 시간 계산을 하고, 그 시간에 맞는 정보를 활용하면 되기 때문입니다. 기존 티맵의 경로탐색 엔진은 AStar 기반의 Time-Dependent 경로탐색을 제공하고 있었습니다.
다만 1편에서도 말씀드렸듯이 CCH기반의 Thor 엔진을 도입하게 된 가장 큰 목적은 성능입니다. 지속적으로 증가하는 사용자와 그에 따른 경로탐색 요청 건수 증가, 장거리 요청 응답 속도 성능, 외부 제공 API의 성능 요구사항 등 AStar로 해결하기 어려운 문제에 부딪히면서 더 나은 성능과 정확도를 보장하는 알고리즘으로 문제 해결을 고민하게 되었습니다.
CCH와 CATCHUp 알고리즘
CATCHUp 알고리즘은 CCH를 기반으로 Time-Dependent 경로탐색이 가능하도록 확장합니다. (이 글의 내용은 많은 부분 1편 '번개처럼 빠른 경로탐색엔진'에서 소개한 CCH 알고리즘을 참조합니다.) Thor 경로탐색 엔진 개발을 위해 알고리즘 선정 시 미리 Time-Dependent를 염두에 두었고, 자연스럽게 CATCHUp으로 적용하게 되었습니다. CCH와 가장 큰 차이점은 경로탐색에 특정 시점의 Snapshot 정보를 이용하거나 시간에 따라 변화하는 정보를 이용하는 가의 차이입니다.
CCH 기반의 Thor 경로탐색 엔진은 크게 3개의 모듈(preprocessor, customizer, route-planning)로 구성됩니다.
CATCHUp 은 각 모듈의 역할에 따라 3단계로 구성됩니다.
Preprocessing(preprocessor)
- Cost Metric에 독립적으로 Graph Topology 가 변경될 때마다 Shortcut을 만드는 작업을 수행합니다. (CCH와 동일합니다.)
- 보통 2주에 한 번씩 수행됩니다.
Time-Dependent Customization(customizer)
- Shortcut의 시간대별 가중치 정보를 계산하여 Shortcut을 구성하는 경로(Witness-Path)의 변화를 저장합니다.
- 보통 패턴 교통정보 업데이트 주기에 맞춰 하루에 한 번 수행합니다.
Query(route-planning)
- 위 두 단계를 거쳐 생성된 데이터를 기반으로 Graph에서 경로를 탐색하는 단계입니다.
CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking)
CCH 알고리즘이 AStar 대비 월등히 빠른 경로탐색 처리 시간을 보일 수 있는 이유는 Shortcut 기반의 탐색 이기 때문입니다. 하지만 Trade-Off 가 있는데요.
1.CCH Graph 생성(Shortcut 생성포함)하는 Preprocessing Time 이 필요합니다(실 서비스에 영향은 없습니다).
2. 원본 Graph에 Shortcut(약 7천만 개 이상) 이 추가되면서 많은 추가 메모리 공간이 필요하게 됩니다.
Preprocessing 단계를 거쳐 생성된 CCH Graph의 Shortcut을 포함한 Arc는 약 9천만(원본 2천만 + Shortcut 7천만)에 이릅니다. CCH 알고리즘은 Snapshot 교통 정보, 유고정보 등을 활용하여 9천만 개에 달하는 Arc의 Cost Metric을 생성합니다. 이는 단일 객체로는 상당히 큰 데이터 이긴 하지만 데이터 구조 최적화를 통해 처리가 가능한 수준입니다(5분 단위 Snapshot Cost Metric 메모리 사이즈: 4 bytes로 encoding 시 9천만 * 4 bytes → 360MB).
하지만 Time-Dependent로 넘어오게 되면 이야기가 달라집니다.
티맵의 예측 교통정보는 평상시 일주일(월~일) + 연휴(최대 9일 치)의 데이터를 활용하고 최대 16일 치 데이터를 처리할 필요가 있습니다. 그리고 9천만 Arc의 16일 치 Cost Metric을 생성한다는 것은 5분 단위의 데이터로 표현한다면 (5분 단위 * 12)[시간당] * 24 [하루치] * 16 [날짜수] = 23,040 배의 메모리 공간이 필요하게 됩니다.
5분 단위의 데이터 360MB * 23,040 → 약 8.3TB로 단순히 서버 메모리 사이즈 증설로 해결 가능한 문제가 아닙니다. 그리고 메모리에 올리지 못한다면 Query 성능이 현저하게 줄어들 것입니다.
CATCHUp 알고리즘의 아이디어
경로탐색 비용을 계산하는 기반 데이터(교통정보, 유고정보 등)의 시간에 따른 변화는 많지만 실제로 Shortcut을 구성하는 Witness-Path 변화는 많지 않습니다.
Customization 단계에서는 모든 Arc의 비용을 계산하여 저장하지 않고, Witness-Path가 변경되는 시점의 Path를 저장합니다. (Shortcut Unpacking Data)
Query 단계에서는 Shortcut Unpacking Data로부터 특정 시점의 Witness-Path를 구할 수 있고, Shortcut 탐색 시 이를 활용하여 Unpacking 하며 Cost(비용), Path(경로) 계산을 합니다.
요약하면, 변화가 크지 않은 Shortcut Unpacking Data를 활용하여 메모리 공간을 확보하고, Query 단계에서 비용, 경로 계산이 필요할 때 Unpacking 하여 재계산하는 것입니다.
Time-Dependent Customization
Shortcut Unpacking Data를 생성하는 과정입니다. 앞서 언급한 대로 Shortcut의 Witness-Path 가 변경되는 시점의 Path를 저장합니다.
CCH 알고리즘의 Customization과 동일하게 Low Rank Node부터 High Rank Node까지 순회하면서 Lower Triangle에 대해서 relaxation을 수행합니다.
Shortcut Unpacking Data
Shortcut u → v에 대해서 Lower Triangle u → w1 → v, u → w2 → v 가 존재하는 경우 relaxation을 거치면 오른쪽 표와 같은 변경 시점 + Witness-Path 정보가 만들어집니다.
참고: 2021 Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks추가적으로 Query 최적화를 위해 Customization 수행 시 계산된 Shortcut Cost의 lower bound, upper bound를 별도로 저장해 둡니다. 이는 Query 최적화 기법(Elimination Tree Interval Query)에서 어떻게 사용되는지 살펴보겠습니다.
Shortcut Unpacking
Time-Dependent Customization의 결과로 Shortcut Unpacking 정보를 만들었습니다. 이를 활용하여 Query단계에서 Shortcut의 특정시점 비용과 소요시간, 원본 Path를 계산할 수 있습니다.
Shortcut Unpacking을 Original Arc를 만날 때까지 재귀적으로 수행합니다(실제 구현은 Stack을 이용했습니다.).
Evaluation
Query 시 사용될 Shortcut의 비용(Cost), 소요시간(Duration)을 계산합니다(아래 Pseudo code에서는 소요시간 만 계산).
참고: 2021 Space-Efficient, Fast and Exact Routing in Time-Dependent Road NetworksUnpack
Query의 결과로 생성된 Shortcut의 원본 Path를 계산합니다.
참고: 2021 Space-Efficient, Fast and Exact Routing in Time-Dependent Road NetworksQuery
CCH 기반의 알고리즘 이기 때문에 CATCHUp 도 마찬가지로 CCH Graph 상에서 Query를 수행하게 됩니다. CCH Graph 상의 Query는 기본적으로 Bidirectional Upward Search를 수행하게 되는데요.
Time-Dependent Query를 위해서는 2가지 이슈를 해결해야 합니다.
1.Time-Dependent에서는 역방향 탐색 시 도로의 진입 시간(entry time)을 알 수 없습니다. → Query를 2단계로 나누어 해결합니다.
a.Subgraph 생성하여 Graph 탐색 범위를 축소합니다.
b.Subgraph에서 Forward-Only Time-Dependent Dijkstra 수행하여 결과를 얻습니다.
2.Shortcut의 Unpacking 은 무거운 작업입니다. → Optimization을 통해 Subgraph의 크기를 줄여 탐색 범위를 최소화합니다.
기본 - Earliest Arrival Queries
1단계 Elimination Tree를 이용한 Subgraph 생성
Elimination Tree는 Node Ordering 된 Chordal Graph에서 최하단 Node부터 Root까지 최소 조상 Node로 올라가는 Edge를 남긴 Graph Tree입니다.
아래 예제는 Upward, Downward로 표현된 CCH Graph와 생성된 Elimination Tree입니다. Source(seqId:12), Target(seqId:30)으로부터 Elimination Tree 구조를 따라 Root까지 최소 조상 Node를 방문하며 연결된 Arc를 Subgraph에 추가합니다.
결과로 아래와 같은 Subgraph 가 만들어집니다. Subgraph 에는 Source와 Target 사이의 ShortestPath가 포함되기 때문에 정확도를 보장할 수 있습니다.
2단계 Forward-Only Time-Dependent Dijkstra
생성된 Subgraph에서 Source로부터 정방향 Time-Dependent Dijkstra를 수행합니다. 탐색 시 필요한 Arc의 Cost는 Evaluation을 통해 얻을 수 있습니다.
여기까지 적용되면 CATCHUp 알고리즘으로 CCH Graph 기반의 Time-Dependent 경로탐색이 가능합니다.
최적화 기법과 성능
기본 구현 만으로는 만족할 만한 성능 이점을 얻을 수 없습니다. 논문에서는 3가지(Corridor, Lazy Unpacking, Corridor AStar) 최적화 기법을 소개합니다.
Elimination Tree Interval Query (Corridor)
Elimination Tree Interval Query는 2단계 Forward-Only Time-Dependent Query를 위한 보다 더 작은 Subgraph를 생성합니다. 이를 Corridor라고 합니다.
앞서 Time-Dependent Customization 수행 시 Arc cost의 lower bound, upper bound를 저장해 두었습니다.
이를 활용하여 Source와 Target으로부터 Elimination Tree의 Root까지 최소 조상을 따라 올라가며 연결된 arc에 대해 relaxation을 수행합니다(최초 node의 cost bound는 무한대로 초기화합니다.).
relaxation을 수행하며 만나는 node에 대해서
- cost bound 가 기존 값과 overlap 되지 않고 더 작으면 node의 lower, upper bound와 연결된 arc, parent pointer를 업데이트합니다.
- cost bound 가 기존 값과 overlap 되는 경우 lower, upper bound를 재계산하고, 연결된 arc, parent pointer를 추가합니다.
forward, backward meeting node 인 경우 node min cost > shortest-path candidate max total cost 조건을 만족하면 skip 할 수 있습니다.
Query가 완료되면 forward(from source), backward(from target) search space가 생성됩니다.
이 두 Search space를 이용하여 Corridor를 구성하게 됩니다.
Lazy Shortcut Unpacking
Forward-Only Time-Dependent Dijkstra에서는 Shortcut의 Cost를 구하기 위해 Runtime에 Unpacking을 수행합니다. 겹겹이 구성된 Shortcut을 Unpacking 하다 보면 연산이 중복되는 경우가 많은데요. 앞서 말씀드렸듯 Unpacking 은 매우 무거운 작업입니다.
Lazy Unpacking 은 Shortcut을 Unpacking 하면서 진출 Arc는 Unpacking 하지 않고 Corridor에 추가합니다(필요시 Lazy Unpack, 논문에서는 1.3~3배의 성능향상 효과).
참고: 2021 Space-Efficient, Fast and Exact Routing in Time-Dependent Road NetworksCATCHUp 기본 + Corridor, Lazy Unpacking 최적화 성능
최초 개발 시에는 CATCHUp 기본 구현과 Corridor, Lazy Unpacking 최적화까지 적용해도 충분한 성능을 보여줄 것으로 예상하고 개발 진행하였고, 성능 테스트를 진행했습니다(CCH 와의 비교를 위해 간단히 CCH_EliminationTree 성능 테스트 결과도 추가합니다.).
Instance Type: r6g.4xlarge (vCPU 16, 128GB) 사용
나쁘지 않은 성능을 보여주지만 예상보다는 부족하였습니다. 경로탐색 시 어떠한 경우에도 Latency는 500ms 이내의 응답 성능을 보여주는 것이 목표였습니다.
따라서 추가적으로 남은 최적화 가법인 Corridor AStar를 적용하기로 결정하고, 개발을 진행합니다.
Corridor AStar
AStar 알고리즘 기본 지식
AStar 알고리즘은 기본적으로 탐색방식은 Dijkstra와 동일하지만 Queue에 입력할 때 사용하는 cost에 heuristic function이 추가되는 구조입니다.
· Dijkstra: cost(s → u)
· AStar: cost(s → u) + heuristic(u → t)
AStar에서 정확성을 보장하기 위해선 아래 조건을 만족하면 됩니다.
· heuristic(u → t) ≤ cost(u → t)
Time-Dependent Customization 시 모든 Arc cost에 대해 lower bound, upper bound를 저장하기 때문에 lower bound를 heuristic function으로 활용할 수 있습니다(lower bound이기 때문에 heuristic(u → t) ≤ cost(u → t) 조건도 만족합니다.).
Elimination Tree Interval Query를 수행하면 forward, backward search space를 얻을 수 있고, 이를 이용하여 Corridor를 생성할 수 있습니다.
backward search space를 통해 계산된 lower bound 값을 이용하면 해당 공간의 모든 node마다 heuristic function을 계산할 수 있습니다.
forward search space에 존재하는 graph의 heuristic function 계산은 아래와 같이 수행합니다.
- query 수행 후 meeting node로부터 forward search space 공간으로 backward search를 추가적으로 수행합니다.
- backward search를 수행하면서 forward search space에 위치한 node에 heuristic function을 계산합니다: heuristic(u → t) = cost(u → v) + heuristic(v → t)
forward only Time-Dependent AStar를 수행합니다.
- Time-Dependent Dijkstra와 동일한 프로세스로 수행합니다.
- Queue에 입력할 때 key(cost)를 cost(s → u) + heuristic(u → t)로 입력합니다.
(참고) Lazy Shortcut Unpacking시에 heuristic function은 다음과 같이 계산한다. (위 Lazy Shortcut Unpacking 이미지 참고)
- u → v를 lazy unpacking 하는 경우
u → w, w → v가 생성됨 → heuristic(v) + lower bound(w → v)를 통해 heuristic(w)를 계산합니다.
- ou → w를 추가 unpacking
u → x, x → w가 생성됨 → heuristic(w) + lower bound(x → w)를 통해 heuristic(x)를 계산합니다.
CATCHUp 기본 + Corridor, Lazy Unpacking, Corridor AStar 최적화 성능
Corridor AStar 구현후 성능테스트 결과 만족할 만한 성능 향상을 보여줍니다. CPU 90% 이상이 유지되는 환경에서도 평균 응답속도 50ms, 400km 이상 장거리 경로에도 평균 300ms 이하의 Latency를 보여줍니다.
Instance Type: r6g.4xlarge (vCPU 16, 128GB) 사용
마치며
논문 검토 및 조사 단계부터 시작해서 티맵 적용 가능성을 판단하고, 실제 기본기능 개발까지 4~5개월 정도 소요되었고, 최적화 및 알고리즘 검증까지 추가 2~3개월 쉽지 않은 개발 여정이었습니다. 목표를 달성하기 위해 공부하고 이슈를 만날 때면 서로 아이디어를 제시하고 토론하면서 결국에는 도달할 수 있었고 그 과정에서 팀은 한 단계 성장했다고 생각합니다.
미래시간 길 찾기를 Thor 엔진으로 전환하면서 많은 자동차 경로탐색 요청을 서버(m6g.12xlarge)2대로 매우 여유 있게 처리하고 있습니다. 또한 장거리 요청의 경우 전에 비해 눈에 띄게 빨라진 응답 성능을 체감할 수 있습니다.
Thor 경로탐색 엔진은 사내 외 서비스에 서서히 영역을 확장해 가고 있습니다. 지도 기반의 서비스에는 경로탐색이 필요한 곳이 많고, 플랫폼 기능으로써 현재 사내 외 여러 서비스에서 활발하게 사용 중입니다. 2023년에는 가장 많은 트래픽이 발생하는 티맵 내비게이션 실시간 경로안내까지 확장을 준비하고 있습니다. 티맵에는 이와 같은 흥미로운 주제가 많이 있습니다. 함께 하실 분들의 많은 참여를 기다립니다. - 티맵모빌리티 채용
참고자료
•2021 Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks
•2015 Customizable Contraction Hierarchies
