네비 개발자여, 번개처럼 빠른 경로탐색엔진을 만들라
티맵 개발자 SSUL 3편 - CCH Algorithm
Chap1. 티맵 경로탐색 엔진
1-1. AStar 알고리즘
1-2. AStar 알고리즘의 한계
Chap2. 경로탐색 알고리즘 검토
2-1. 알고리즘 조사
2-2. 알고리즘 선택
Chap3. CCH(Customizable Contraction Hierarchies) 알고리즘을 이용한 Thor 엔진 개발
3-1. CH(Contraction Hierarchies) 알고리즘
3-2. CCH 기본 아이디어
3-3. Node Ordering
3-4. Graph Partitioning 알고리즘
3-5. Metric-Independent Preprocessing
3-6. Metric-Dependent Customization
3-7. Query
3-8. 성능
마치며
Chap1. 티맵 경로탐색 엔진
많은 사용자 분들이 현재 티맵 내비게이션과 함께 운전을 하고 계시죠?:) 프로티맵러이시라면 티맵이 어떻게 경로를 탐색해 안내하는지 궁금하셨을텐데요. 오늘은 그 비밀이라고 할 수 있는 ‘티맵 경로탐색 엔진’에 대해서 알려드리겠습니다.
티맵 경로탐색 엔진은 아래 화면과 같이 출발지부터 목적지까지 사용자에게 최적의 경로를 안내해주기 위한 엔진입니다.
도로네트워크를 기반으로 다양한 정보(실시간/예측 교통정보, 유고정보 등)를 수집하고, 해당 정보들을 비용(Cost)으로 환산하여 경로탐색에 이용하고 있습니다.
이를 알고리즘 문제로 정의한다면 Road Network 으로 생성된 Graph 구조에서 Source(출발지), Target(목적지)가 주어졌을 때, Source → Target 까지 최소의 비용으로 이동이 가능한 Shortest Path를 찾는 문제로 정의할 수 있습니다.
1-1. AStar 알고리즘
현재 티맵 경로탐색 엔진은 AStar 알고리즘으로 개발되어 있습니다. AStar 알고리즘은 전통적 경로탐색 알고리즘인 Dijkstra 알고리즘에 heuristic function이 추가되어 성능을 개선한 알고리즘 입니다.
AStar 알고리즘은 ‘heuristic function을 어떻게 설정하느냐’에 따라 탐색성능이 달라집니다. 또한 heuristic function을 설정할 때에는 아래와 같이 admisible 조건을 만족해야 Shortest Path 탐색이 가능합니다.
참고: https://en.wikipedia.org/wiki/Admissible_heuristic▼왼쪽부터 Dijkstra - AStar(admissible) - AStar(non-admissible)
heuristic function을 목적지까지의 직선거리로 설정한 케이스인데요, 탐색범위를 보시면 AStar 알고리즘의 탐색범위가 더 적다는 것을 알 수 있습니다.
추가적으로 heuristic function을 non-admissible로 설정하게 되면 탐색 성능은 훨씬 빨라지게 되지만 shortest-path를 보장하지는 않습니다.
1-2. AStar 알고리즘의 한계
성능 이슈
heuristic function으로 성능을 높이긴 했지만, 모든 node를 방문하면서 탐색하는 방식이기 때문에 Graph 의 크기가 커지면 커질수록 탐색성능은 느려지는 경향이 있습니다.
오랜 기간동안 티맵 서비스를 제공하면서 많은 도로들이 개통되고 상세화 되면서 Network의 크기는 지속적으로 커지고 있었습니다. 여기에 스마트폰의 보급 등으로 티맵 유저수도 폭발적으로 늘어나면서 점점 서버에 부하가 걸리기 시작하였습니다.
그로 인해 서울 → 부산 등으로 경로탐색을 하게 되면 요청당 2~3s 정도 혹은 그 이상 소요되는 경우도 간헐적으로 발생하게 되었습니다.
확장성 이슈
그동안 다양한 요구사항으로 인해, 경로탐색결과는 단순히 내비게이션에서만 사용되는 것이 아니라 다양한 분야에서 사용되고 있습니다.
예)
택시 배차시 승객 주변 n대의 택시가 승객의 위치까지 이동하는데 걸리는 경로 계산
택배 등의 물류배송시 최적의 경로를 안내하기 위해 경유지간 n * m 경로 계산
하지만 AStar 알고리즘은 기본적으로 목적지 방향으로 탐색하는 알고리즘이기 때문에 위와 같이 n * m 경로를 탐색할 수는 없습니다.
Chap2. 경로탐색 알고리즘 검토
2-1. 알고리즘 조사
참고: 2015 Route Planning in Transportation Networks2005년 구글맵이 오픈 된 이후로, 경로탐색 알고리즘 분야에서도 다양한 논문들이 발표되기 시작했습니다. 여러 알고리즘들을 테크닉별로 위와 같이 정리할 수 있습니다.
Goal-Directed
출발지로부터 목적지를 향해서 탐색하는 알고리즘입니다. 위에서 말씀드린대로 AStar가 대표적이고요. Landmark를 이용하여 heuristic function을 계산 하면서 탐색반경을 획기적으로 줄어들게 성능을 개선한 ALT 알고리즘으로 발전되었습니다.
하지만 앞서 말씀드린대로 Goal-Directed는 목적지 방향으로 탐색하는 알고리즘이기 때문에 n * m 탐색이 불가능합니다.
Hierachical
기본적으로 vertex(node)를 중요도 순서대로 정렬을 한 후, vertex u에 연결된 이웃 vertex간에 이동이 가능하도록 shortcut을 만들어서 성능을 향상시키는 알고리즘입니다.
처음 CH알고리즘이 발표된 이후, 실시간 교통정보 변경 등에 대응하기 위해 CRP알고리즘에 처음 도입된 개념인 Customization 기능을 추가하면서 CCH 알고리즘으로 개선되었습니다.
Separator Based
Graph를 각 지역(Region) 단위로 파티셔닝하고, 각 Region의 경계지점(boundary vertex) 마다 내부에 shortcut을 생성하고, Region to Region 마다 shortcut을 생성한 후 탐색하여 성능을 향상시키는 알고리즘입니다.
해당 알고리즘에 처음 실시간 교통정보 변경 등에 대응하기 위한 Customization 기능이 추가되어 주기적으로 Region 내부의 shortcut을 업데이트 합니다.
2-2. 알고리즘 선택
참고: 2015 Route Planning in Transportation Networks위에서 언급한대로 Goal-Directed 테크닉에서도 ALT 등으로 개선되면서 성능이 빠른 알고리즘이 발표되었지만 n * m 경로탐색을 지원하지 않아 기능 확장성에 문제가 있어 배제했습니다.
CCH(Customizable Contraction Hierarchies), CRP(Customizable Route Planning) 모두 n * m 경로탐색 지원이 가능하고, 성능도 대폭 개선되었다는 점을 확인했습니다.
따라서 두 알고리즘 중 어떤 알고리즘을 선택할지 고민하다 차 후 Time-Dependent graph 의 지원여부 및 구현에 대한 용이성 등을 고려하여 최종적으로 CCH 알고리즘을 선택하게 되었습니다.
Chap3. CCH(Customizable Contraction Hierarchies) 알고리즘을 이용한 Thor 엔진 개발
위에서 언급한대로 저희는 CCH알고리즘을 사용하기로 결정했고, 신규알고리즘을 토대로 새로운 엔진을 개발하기 위한 프로젝트를 "번개처럼 빠른 경로탐색 엔진" 이라는 의미를 담아 Thor 엔진이라 정하고 진행하게 되었습니다.
CCH 알고리즘은 실시간 교통정보 등에 효율적으로 대응하기 위해 Customization 단계가 추가된 알고리즘 입니다. 알고리즘은 아래 3단계로 구성됩니다.
Metric-Independent Preprocessing
-cost metric에 독립적으로 topology가 변경될 때마다, 즉 맵데이터가 변경될 때마다 shortcut을 만드는 작업을 수행합니다.
-보통 2주에 한번씩 수행 됩니다.
Metric-Dependent Customization
-실시간 교통정보 등이 업데이트 될 때마다 수행되어, shortcut의 가중치를 업데이트 합니다.
-보통 5분에 한번씩 수행 됩니다.
Query
-위 두 단계를 거쳐 생성된 Graph에서 경로를 탐색하는 단계입니다.
3-1. CH(Contraction Hierarchies) 알고리즘
CCH 알고리즘은 CH알고리즘을 기반으로 확장된 알고리즘입니다. 따라서 CH알고리즘에 대해 기본적인 개념들을 먼저 알아보도록 하겠습니다.
기본 아이디어
노드를 중요도(rank) 순서로 정렬한 후, 왼쪽 그림과 같이 중요도가 v > u, u < w 인 조건을 만족하는 경우 v → w 에 대한 shortcut을 생성합니다.
만약 우측 그림과 같이 shortcut에 해당하는 cost보다 더 나은 경로가 이미 존재한다면 shortcut은 생성하지 않습니다. 이 때 v → x → y → w 경로를 v → w에 대한 witness path 라고 합니다.
이와 같이 v → u, u → w 에 대한 shortcut v → w를 만드는 작업을 contraction 작업이라 합니다.
Node Ordering
위에서 언급한 contraction 작업을 수행할 때, 노드의 정렬 순서는 매우 중요합니다. 정렬 순서에 따라 Query 성능에서 꽤 차이가 발생합니다.
위 자료에서의 숫자는 노드의 중요도(rank)를 나타냅니다. 좌측에서 부터 우측에 있는 파란색 노드로 탐색할 때
Balanced Ordering 에서는 1 → 4 ⤏ 5 → 3 으로 shortcut을 이용한 효율적 탐색이 가능하지만
Unbalanced Ordering 에서는 2 → 3 → 4 → 5 → 6 으로 shortcut 없는 탐색이 되어 shortcut이 생성된게 쓸모없게 됩니다.
CH알고리즘에서도 효율적인 정렬 알고리즘이 있지만, 이 부분은 뒤에 CCH알고리즘에서 개선된 정렬 알고리즘이 소개 되므로 뒤에서 자세히 말씀드리도록 하겠습니다.
Query
Shortcut이 포함된 Graph를 2개의 Graph로 나눕니다.
Upward Graph (u → v | u < v): 노드의 중요도(rank)가 u < v 인 edge만을 대상으로하는 Graph
Downward Graph: u → v | u > v: 노드의 중요도(rank)가 u > v 인 edge만을 대상으로하는 Graph
그리고 Query알고리즘은 Bidirectional Dijkstra를 이용합니다.
Upward Graph 에서 정방향으로 탐색하고,
Downward Graph에서 역방향으로 탐색합니다.
참고: 2008 Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
참고: 2008 Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks탐색한 결과는 Shortcut 을 포함하기 때문에, 위 그림과 같이 Shortcut에 대해 unpacking 단계를 수행하여 원본 node, edge를 얻어온 후 결과를 응답합니다.
3-2. CCH 기본 아이디어
자, 그럼 CH알고리즘에서 확장된 CCH 알고리즘의 기본 아이디어에 대해 알아보겠습니다.
CH와 거의 유사합니다만 아래와 같은 내용이 다릅니다.
shortcut에 cost를 부여하지 않습니다. 나중에 cost가 업데이트 될 수 있기 때문에 무한대 값으로 설정합니다.
cost가 무한대이기 때문에, witness-path에 대해 체크하지 않습니다.
3-3. Node Ordering
CH알고리즘 파트에서 노드정렬에 대한 중요성에 대해 말씀드렸는데요, CCH에서는 Nested Dissection 즉 Graph 를 Balanced 하게 Partitioning 하여 노드를 정렬하는 방식이 성능향상에 도움이 된다고 합니다.
참고 - 2012 Search Space Size in Contraction Hierarchies위 자료와 같이 Graph를 파티셔닝하여 정렬하게 되면 shortcut이 생성되는 개수가 최소화되고, 노드간의 연결(Edge)은 자신의 부모 파티션과만 연결되어있기 때문에 동일 level Partition 간에는 Edge로 연결되지 않는다는 것이 보장됩니다. 그로 인해 뒤에서 설명드릴 Customization 단계에서의 처리작업을 병렬로 수행할 수 있습니다.
3-4. Graph Partitioning 알고리즘
Graph Partitioning 알고리즘도 어떤 알고리즘을 사용하느냐에 따라 성능의 차이가 발생하는데요, 구현이 쉬우면서도 성능도 꽤 잘 나오는 Inertial Flow를 많은 곳에서 사용합니다.
Graph에 임의의 직선을 만들고, Node를 Projection하여 정렬합니다.
임의의 직선을 여러개 만들어 그 중 가장 좋은 (밸런싱이 잘 된) 결과를 사용합니다.
정렬된 Node를 기준으로 b · ｜N｜개수의 Node를 Sources, Sinks 로 설정합니다. (b 값은 보통 0.2 ~ 0.4 정도로 설정합니다)
다음은 Source, Sink를 이용한 min-cut 알고리즘을 수행합니다.
저희 같은 경우는 Dinic's 알고리즘을 사용하였습니다.
전국을 Inertial Flow를 이용하여 Graph Partitioning을 수행하면 아래 그림과 같이 Balanced하게 잘 나뉘어 진 것을 볼 수 있습니다. (level < 5)
3-5. Metric-Independent Preprocessing
preprocessing 단계는 cost metric에 독립적으로 topology가 변경될 때마다, 즉 맵데이터가 변경될 때마다 shortcut을 만드는 작업을 수행합니다. 티맵 같은 경우는 특별한 이슈가 없는한 보통 2주에 한번씩 수행됩니다. 서비스에 영향이 없기 때문에 오랜 시간이 걸리더라도, 최대한 모든 연산을 preprocessing 단계에서 미리 수행해 놓는 것이 효율적입니다.
위에서 말씀드렸던 대로, 그래프 파티셔닝을 이용하여 정렬된 노드의 중요도 순서대로 위와 같은 조건을 만족하는 shortcut을 생성합니다.
노드 내에 작성된 숫자는 노드의 중요도(rank) 입니다. rank-1 노드부터 인접한 shortcut을 생성하는 애니메이션입니다. 마지막 이미지는 노드를 rank 순서대로 정렬한 이미지 입니다.
이렇게 생성된 Graph는 Chordal Graph 라고 부르고, 해당 데이터를 이용하여 이 후 단계를 진행합니다.
3-6. Metric-Dependent Customization
Graph의 Cost metric은 교통정보, 유고정보 등 다양한 정보들이 변화함으로 인해 주기적으로 업데이트가 됩니다. 그리고 업데이트가 일어날 때마다 그에 맞게 경로는 변화되어야 합니다.
Customization 단계는 두 단계로 나뉘어서 수행 됩니다.
Basic Customization: low rank = 1 부터 high rank 까지 노드를 순회하며 업데이트된 cost metric을 이용하여, 무한대 값을 가지고 있는 shortcut의 cost를 업데이트합니다.
Perfect Customization: high rank 부터 low rank 까지 노드를 순회하며 추가적인 변경이 필요한 cost에 대해 업데이트를 하고, 필요 없는 arc(shortcut 포함) 데이터를 삭제합니다.
preprocessing 단계에서 생성된 Graph의 연결성과 노드의 rank를 이용하여 위와 같이 3가지 종류로 구분합니다.
Basic Customization
분류된 Triangles 중 Lower Triangles 데이터를 이용하여 shortcut 업데이트를 수행합니다.
아래 이미지와 같이 shortcut이 구성된 경우에는 shortcut의 cost는 6으로 업데이트되고, v → w에 대한 witness-path는 v → u' → w으로 저장됩니다.
preprocessing 단계에서 생성된 Graph에서 Lower Triangles 데이터를 이용하여, Low rank node 부터 high rank node까지 순차적으로 순회하면서 아래 애니메이션처럼 cost 데이터를 업데이트 합니다.
Perfect Customization
분류된 Triangles 중 Middle, Upper Triangles 데이터를 이용하여 shortcut 업데이트를 수행합니다. Basic Customization과는 반대로 High rank node에서부터 Low rank node까지 순차적으로 순회하면서 아래 애니메이션처럼 shortcut 뿐만 아니라 일반 arc에도 cost 데이터를 업데이트 합니다.
업데이트되는 cost를 가지는 arc(shortcut 포함)는 경로탐색 대상에서 제외돼도 무방한 arc입니다. 이미 triangles 내에서 해당 arc의 cost 값보다 낮은 cost를 가진 arc로 탐색이 가능하기 때문입니다. 따라서 perfect customization 단계에서 업데이트되는 arc들을 Graph에서 삭제합니다.(Query단계에서 성능이 향상됩니다)
3-7. Query
기본적으로 출발지 → 목적지로 이동하는 one-to-one 경로탐색 알고리즘은 CH 알고리즘에서 소개해드린 내용과 동일하게 동작하므로, 생략합니다. 여기에서는 추가적으로 n개의 출발지 → n개의 목적지로 이동하는 many-to-many 경로탐색 알고리즘에 대해 설명 드리도록 하겠습니다.
위 이미지에서처럼 3개의 출발지에서 3개의 목적지까지 이동하는 경로를 탐색하려면 총 n * m, 즉 9번의 경로탐색이 필요합니다. 하지만 Dijkstra 알고리즘의 특성을 이용하면 n + m, 즉 6번의 Dijkstra 연산을 통해 9개의 경로를 얻어낼 수 있습니다. 이는 n, m 의 개수가 증가하면 할수록 더욱 더 성능의 차이를 발생시킵니다.
기본적으로 Dijkstra 알고리즘은 출발지로부터 연결된 모든 지점으로 탐색해 나가는 알고리즘 입니다(BFS 알고리즘과 유사). 위와 같은 Graph에서 A → F에 대해 Dijkstra 알고리즘을 수행하고 나면 위와 같은 정보를 얻을 수 있고, 이를 출발지 A를 Root Node로 하는 Shortest Path Tree라고 합니다.
이와 같은 Dijkstra의 특성을 이용하여 Bidirectional Dijkstra 알고리즘을 이용합니다. 우선, 위 이미지에서 처럼 모든 목적지(target)에 대해서 역방향 Dijkstra를 수행하여 각각의 Shortest Path Tree를 구합니다.
그리고 모든 출발지(source)에 대해서 정방향 Dijkstra를 수행하여 각각의 Shortest Path Tree를 구합니다. 각 출도착지 Tree마다 intersect되는 지점이 존재한다면 경로를 탐색하였다는 것이고, Tree 순회를 통해 Shortest Path를 얻어올 수 있습니다.
3-8. 성능
기존 AStar 대비 성능이 얼만큼 개선되었는지 측정하기위해 동일장비에서 테스트를 수행하였습니다.
테스트셋은 일주일동안의 유저의 요청정보를 랜덤샘플링하여 이용하였습니다.
위 이미지에서 보시다시피 Latency, Throughput 모드 큰 폭으로 개선되었습니다. 특히, 400km 이상 장거리 구간에서는 거의 100배이상 성능이 대폭 개선되었습니다.
마치며
개인적으로 알고리즘 개선을 위해 다양한 논문들을 조사한 후 프로토타이핑을 통해 빠르게 결과를 확인해보고, 서비스에 적용하기 까지 여러 문제점 들이 있었지만 문제들을 하나씩 해결해 나갔고, 그 과정 속에서 팀 멤버들이 다같이 성장하게 되는 소중한 경험이었습니다. 이 과정을 함께하고 싶은 분들은 언제든 지원 부탁드립니다. - 티맵모빌리티 채용
현재 티맵 내비게이션은 굉장히 많은 사용자가 이용중인 내비게이션이기 때문에 Thor 엔진을 티맵 내비게이션에 바로 적용하기 보다는, 빠른 성능에 대한 요구사항을 가지고있는 고객을 대상으로 티맵 Open API부터 우선적으로 적용되었습니다. 그리고 바로 이어서 보행자 경로탐색 기능에 대한 개발을 완료하였으며 Thor 엔진에 추가되어 연말에 서비스에 적용 예정입니다.
또한 현재 티맵모빌리티는 다양한 모빌리티 서비스로의 확장을 시도중입니다. 대리운전, 퀵서비스, 물류 서비스등이 런칭될 때, 신규 엔진을 활용하여 사용자에게 최적화된 서비스를 제공하려 합니다. 긴 글 읽어 주셔서 감사합니다.
참고자료
2015 Route Planning in Transportation Networks
2008 Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
2012 Search Space Size in Contraction Hierarchies
2015 Customizable Contraction Hierarchies
2015 On Balanced Separators in Road Networks
Lecture - algorithm for routeplanning (KIT)
경로탐색엔진 2편도 나왔어요
