[Navigation] #1 경로탐색은 어떻게 하는 것일까?

1. 네비게이션 엔진에 관심을 갖게 된 계기

서울역에서 부산역까지 길을 검색하면 결과는 거의 즉시 나온다.

이처럼 우리는 거리에 관계없이 쉽고 빠르게 길찾기 결과를 얻을 수 있다.
하지만 대한민국 전체 도로망은 방대한 수의 도로와 교차로로 이루어져있다.

도로를 edge, 교차로를 node라고 생각하면 도로망을 거대한 그래프라고 생각 할 수 있다.

그렇다면 질문이 생긴다.

이 거대한 그래프에서 최적의 경로를 몇 ms 만에 어떻게 찾는 것일까?

 

2. 경로 탐색은 어떻게 하는 것일까?

2-1. 도로망은 그래프다

네비게이션에서 도로는 아래와 같이 모델링된다.

• 교차로 → Node
• 도로 → Edge
• 이동 비용 → Weight

즉, 경로 탐색은 결국 그래프 최단 경로 문제다.

 

2-2. 경로 탐색 알고리즘은 어떤 것들이 있을까?

다익스트라(Dijkstra)

• 하나의 시작 정점(source)에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
• 가중치 그래프에서 사용하며, 모든 간선의 가중치는 0 이상(음수 불가)
• 그리디(Greedy) 알고리즘
• 최단 거리가 확정된 정점은 다시 갱신하지 않음
• 원리
  1. 시작 정점의 거리는 0, 나머지는 무한대(∞)
  2. 아직 방문하지 않은 정점 중 가장 거리가 짧은 정점 선택
  3. 해당 정점을 거쳐 다른 정점으로 가는 거리 갱신
  4. 모든 정점을 처리할 때까지 반복
• 시간복잡도: O(E log V)

그래프 전체를 퍼져나가며 최단거리를 계산한다. (모든 방향을 탐색)

이 방식은 항상 정확한 최단 경로를 보장하지만, 전국 단위 도로망에 그대로 적용하면 탐색 범위가 너무 넓어 실시간 응답이 어렵다

 

A*

• Dijkstra에 휴리스틱(heuristic)을 추가한 방식
• 휴리스틱(heuristic) : 목표까지 남은 비용을 추정하는 함수
• 목표 지점 방향으로 탐색 범위를 줄임
• e.g. 서울 → 부산 경로를 찾을 때 전국을 전부 탐색하지 않고 "부산과 가까워지는 방향"을 우선 탐색한다.
• f(n) = g(n) + h(n)
  • g(n): 지금까지 온 비용
  • h(n): 목표까지의 예상 거리
  • f(n) : 총 예상 비용
• 시간복잡도 : 최악은 Dijkstra와 동일, 하지만 휴리스틱을 통해 목적지 방향의 노드만 우선적으로 탐색하여 불필요한 탐색을 줄이기 때문에 실제는 훨씬 빠름

휴리스틱이 정확할수록 탐색 속도는 크게 개선된다.
이때 좋은 휴리스틱이란 무엇일까? 조건은 다음과 같다.

• 과대평가하지 않을 것 (Admissible)

휴리스틱으로 추정한 거리는 실제 최단 거리보다 절대 크면 안 된다.

h(n) ≤ h * (n)           ( h(n): 휴리스틱 추정값, h∗(n): 실제 최단 거리 )

이를 허용적(admissible)이라고 하며, 이 조건이 만족되면 A*는 항상 최적해를 보장한다.

e.g. 직선거리(Euclidean distance)는 실제 도로 거리보다 짧거나 같기 때문에 admissible하다.

• 일관성(Consistency, Monotonicity)을 가질 것

모든 간선에 대해 다음을 만족해야 한다.

h(n) ≤ cost(n, m) + h(m)

현재 노드의 휴리스틱 값은 "이웃 노드로 이동 비용 + 이웃 노드의 휴리스틱 값"보다 크면 안 된다.
이 조건을 만족하면:
- f(n) = g(n) + h(n)이 단조 증가
- 한 번 방문한 노드를 다시 방문할 필요가 없음, 이미 확정된 노드는 최적임이 보장됨
- 구현이 단순해지고 성능이 안정적

• 실제 비용에 최대한 가까울 것 (정확성)

휴리스틱이 너무 작으면?

→ 거의 다익스트라처럼 동작한다.
→ 탐색 범위가 넓어지고 느려진다.

휴리스틱이 실제 최단 거리와 가까울수록 A*는 목표 방향으로 빠르게 수렴한다.

즉, 휴리스틱은 과대평가하지 않으면서도 가능한 한 실제 비용에 가까워야 한다.

• 계산 비용이 낮을 것

휴리스틱 계산 자체가 느리면 오히려 전체 알고리즘이 느려진다.

휴리스틱은 빠르게 계산 가능하고, 탐색 공간은 크게 줄여야한다.

 

좋은 휴리스틱은 "과대평가하지 않으면서, 실제 거리와 최대한 가깝고, 계산이 빠른 추정 함수"이다.

Dijkstra A*

https://qiao.github.io/PathFinding.js/visual/ 에서 길찾기 알고리즘 동작을 시각적으로 확인 할 수 있다.

다익스트라는 시작점에서 사방으로 퍼지는 모습을 보이며 탐색 범위가 넒고 A*는 장애물을 피해 목표 방향으로 집중된 탐색을 하여 탐색 범위가 줄어듦을 볼 수 있다. 

	Dijkstra vs  A*
	Dijkstra	A*
기본 개념	시작점 기준 최단 경로 탐색	목표 지향 최단 경로 탐색
평가 함수	f(n) = g(n)	f(n) = g(n) + h(n)
휴리스틱 사용	없음	있음
탐색 방향	사방으로 균등 확장	목표 방향으로 집중
탐색 노드 수	많음	적음 (좋은 h일수록 더 적음)
시간 복잡도	O(E log V)	최악 O(E log V) (보통 더 빠름)
구현 난이도	비교적 단순	휴리스틱 설계 필요
대표 사용	네트워크 라우팅, 전체 거리 계산	게임, 네비게이션, 로봇 경로

 

도로망은 노드와 간선 수가 매우 많은 대규모 그래프이기 때문에, 매 요청마다 탐색을 수행하는 A*의 방식은 계산 부담이 커질 수밖에 없다.

또한 실제 도로는 고속도로, 간선도로, 골목길처럼 계층적인 구조를 가지고 있지만, A*는 이러한 계층 정보를 사전에 활용하지 않는다. 따라서 경로를 탐색할 때 고속도로와 같은 상위 도로망으로 빠르게 진입하는 구조를 매번 찾아야 한다.

여기에 실시간 교통 상황까지 반영해야 하는 환경에서는 간선 가중치가 계속 변경되므로, A*는 변경된 비용을 기준으로 다시 탐색을 수행해야한다.

이러한 한계를 보완하기 위해 그래프를 사전에 계층화하거나 분할하는 전처리 기반 알고리즘(CH, CCH, MLD 등)이 사용되고 있다.

 

CH (Contraction Hierarchies)

• 도로망을 사전 전처리하여 중요도가 낮은 노드를 제거(Contraction)하면서 shortcut을 추가하는 방식

before after

위 이미지 예시에서  v → u → w 경로의 총 비용이 3이다. 이때 노드 u를 제거(contraction)하면서 v와 w 사이에 비용 3의 shortcut 간선을 추가한다.

• 원리:
  1. 도로망의 모든 노드에 중요도(rank) 부여
  2. 중요하지 않은 노드를 제거하면서 shortcut 간선 생성
  3. 계층 구조를 활용해 탐색 범위를 제한

여기서 말하는 "계층 구조를 활용해 탐색 범위를 제한한다"의 의미는 다음과 같다.

CH에서는 중요도 부여와 노드 제거 과정을 거친 뒤,  모든 노드가 중요도 순서에 따라 계층(level)을 갖게 된다.
즉, 도로들은 중요도에 따른 위계 구조를 가지게 된다.

예를 들어 중요도를 단순화하면 다음과 같이 생각할 수 있다.

• 동네 골목 = 낮은 중요도
• 간선도로 = 중간 중요도
• 고속도로 = 높은 중요도

이 구조가 완성된 뒤 실제 경로 탐색을 수행할 때, 중요도가 증가하는 방향으로만 이동하도록 탐색을 제한한다.

• 낮은 중요도 → 높은 중요도 방향 이동은 허용
• 높은 중요도 → 낮은 중요도 방향 이동은 제한

이러한 제한을 두는 이유는 불필요한 하위 도로 탐색을 줄이기 위함이다.
장거리 이동의 경우 대부분 상위 계층(간선도로, 고속도로)을 중심으로 경로가 형성되기 때문에, 하위 계층을 반복적으로 탐색할 필요가 없다.

또한 CH는 출발지에서 도착지로 한 방향으로만 탐색하지 않는다.
노드의 중요도가 증가하는 방향으로 탐색하되, 출발지와 도착지 양쪽에서 동시에 탐색을 수행하는 양방향 탐색(bidirectional search)을 적용하여 속도를 극대화한다.

• 출발지에서 → 중요도가 증가하는 방향으로 탐색
• 도착지에서 → 중요도가 증가하는 방향으로 역방향 탐색

즉, 양쪽에서 동시에 위로 올라가며 탐색을 진행한다. 이때 왜 도착점에서도 위로 올라갈까?

CH 전처리 이후 그래프는 "중요도 순으로 방향성이 부여된 그래프"가 된다.

따라서 한쪽에서만 탐색하는 것이 아니라, 출발지와 도착지 모두에서 같은 규칙을 적용해 상위 계층으로 탐색을 확장한다.

정리하면 다음과 같다.

• 시작점 → 상위 계층으로만 이동
• 도착점 → 상위 계층으로만 이동 (역방향 그래프 기준)

이렇게 하면 두 탐색은 결국 어느 상위 계층 노드에서 만나게 된다. 이 만나는 지점이 바로 최적 경로의 중간 지점이 된다.
최종 경로는 "시작점 → 만나는 지점 → 도착점"으로 구성된다.

그렇다면 실제로 탐색 범위는 얼마나 줄어들까? 서울 → 부산 경로를 찾는다고 가정해보자.

• 시작점은 서울의 하위 도로에서 시작
• 빠르게 간선도로, 고속도로 계층으로 상승
• 도착점도 부산에서 동일하게 상승

결과적으로 두 탐색은 전국의 모든 도로를 살펴보는 대신, 고속도로와 같은 상위 계층 도로 중심에서 만나게 된다.

즉, 서울과 부산 사이의 수많은 골목길과 동네 도로는 탐색 대상에서 자연스럽게 제외된다.
이로 인해 탐색해야 할 노드 수가 급격히 줄어들고,  빠르게 결과를 계산할 수 있게 된다.

•  시간복잡도:
  • 전처리 : 매우 오래 걸림  (대규모 망은 수 시간 가능)
  • 질의 (query) : ms 단위 (매우 빠름)

CH는 경로 탐색을 매우 빠르게 수행할 수 있는 알고리즘이다.
하지만 전처리 단계에서 가중치(예: 거리, 시간)를 기준으로 shortcut을 생성하기 때문에, 가중치가 변경되면 기존 shortcut의 비용이 더 이상 최적성을 보장하지 못한다.

즉, 교통 상황이나 시간대에 따라 간선 가중치가 달라지면 전처리(Contraction) 과정을 처음부터 다시 수행해야 하는 구조적 한계가 있다. 이 때문에 CH는 정적(static) 가중치 환경에서는 매우 강력하지만, 실시간 교통 정보처럼 가중치가 자주 변하는 환경에는 유연하게 대응하기 어렵다.

CCH는 이러한 한계를 해결하기 위해 등장했다.

 

CCH (Customizable Contraction Hierarchies)

• CH를 확장하여 구조(Topology)와 가중치(Weight)를 분리한 알고리즘
• 원리:
  1. 도로 구조만으로 계층 생성 (가중치 무관)
     CCH는 CH와 달리 계층 구조를 만들 때 가중치를 사용하지 않는다.
     오직 도로의 연결 관계(Topology)만을 기준으로 노드를 제거하고 shortcut 구조를 생성한다. 이 단계는 계산량이 크기 때문에 시간이 오래 걸리지만, 도로망 구조가 바뀌지 않는 한 한 번만 수행하면 된다.
     즉, "이 도로가 얼마나 빠른가"가 아니라 "이 도로가 어떻게 연결되어 있는가"만을 기반으로 계층이 형성된다. 
  2. 동적 가중치 반영 (Customization 단계)
     CCH의 핵심은 도로의 구조(Topology)와 비용(Weight)을 분리하는 설계에 있다.
     이때 변경된 비용을 반영하는 과정을 Customization 단계라고 한다.
     Customization 단계에서는 실시간 교통 정보뿐만 아니라, 시간대별 평균 속도, 차량 유형, 통행료 정책, 도로 제한 조건 등 다양한 비용 요소를 가중치에 반영할 수 있다.
     계층 구조와 shortcut의 연결 관계가 이미 전처리 단계에서 완성되어 있어서, 교통 상황이나 시간대 변화로 간선 가중치가 변경되더라도 그래프 구조를 다시 생성할 필요는 없다. 대신, 변경된 간선 가중치를 기반으로 각 shortcut이 대표하는 경로의 최소 비용 값만 재계산하면 된다.
     즉, 구조는 고정되어 있고, 비용만 동적으로 갱신되는 방식이다.
  3. CH와 동일한 방식으로 빠른 질의 수행
     Customization이 끝나면 경로 질의는 CH와 동일한 방식으로 수행된다.
     • 중요도가 증가하는 방향으로만 탐색
     • 양방향 탐색(bidirectional search) 수행
     • 상위 계층에서 탐색이 만나는 지점에서 최단 경로 확정

• 시간복잡도:
  • 구조 전처리: 오래 걸림 (초기 1회 수행)
  • Customization(가중치 반영): 수 초~수십 초
  • 질의(query) : ms 단위 (매우 빠름)

CH의 응답 성능을 유지하면서 교통 가중치를 유연하게 반영할 수 있도록 개선한 모델이다.

고정 도로망 + 다양한 비용 모델을 빠르게 적용해야 하는 환경에 적합하다.

 

MLD (Multi-Level Dijkstra)

• 그래프를 다중 레벨로 분할(partition) 하여 지역 → 광역 → 전국 단위로 계층을 구성하는 방식
• 대규모 도로망을 한 번에 탐색하지 않고, 필요한 영역만 단계적으로 확장하도록 설계된 알고리즘
• 원리:
  1. 지도를 여러 구역(cell)으로 분할
     전체 도로망을 하나의 거대한 그래프로 다루지 않고, 공간적으로 여러 개의 셀(cell)로 분할한다.
     예: 시/군 단위 또는 격자 기반 분할
  2. 각 구역의 경계 노드(boundary node) 를 추출
     각 셀에서 다른 셀로 연결되는 노드들만 추출한다. 이 노드들을 boundary node라고 한다.
     
     • 셀 내부에서만 연결되는 노드 → 로컬 처리
     • 셀 밖으로 나가는 노드 → 상위 레벨 처리 대상
     이 boundary node들은 "구역을 벗어나는 출입구 역할"을 한다.
  3. 상위 레벨 그래프(Overlay Graph) 구성
     각 셀 내부에서 boundary node들 간의 최단 거리를 미리 계산한다.
     예를 들어, 셀 A 내부에 boundary node가 3개 있다면 이 3개 노드 사이의 모든 쌍(pair)에 대해 최단 거리를 계산해 둔다. 
     이때 계산되는 것은 단순 연결이 아니라 " 셀 내부를 통과할 때 발생하는 최소 비용 " 이다.
     그 결과, 실제 도로망 위에 boundary node들만으로 구성된 요약 그래프(overlay graph) 가 생성된다.
     이 overlay graph는 다음과 같은 특징을 가진다:
     • 셀 내부의 복잡한 도로 구조는 상위 레벨에서 보이지 않는다.
     • boundary node들만 남아 상호 연결된다.
     • 각 연결 간선은 “셀 내부 최단 거리”를 비용으로 가진다.
     • 상위 레벨 탐색에서는 이 간소화된 그래프만 탐색한다.
       
       이 덕분에 상위 레벨 탐색에서는 노드 수와 간선 수가 크게 줄어들어 질의 속도가 빨라진다.
       실제 도로망 전체를 탐색하는 대신 "셀 내부는 압축하고, 셀 간 이동은 boundary 중심으로 처리하는 구조" 가 만들어진다.
  4. 질의 시 동작 방식
     경로 요청이 들어오면 탐색은 3단계로 진행된다.
     
     • 출발지 셀 내부 탐색 : 출발지에서 해당 셀의 boundary node까지 로컬 탐색
     • 상위 레벨 overlay 그래프 탐색 : boundary node들만 있는 작은 그래프에서 빠르게 이동
     • 목적지 셀 내부 탐색 : 목적지 셀로 내려와 로컬 탐색으로 마무리
       
       이 과정에서 기본 탐색은  Dijkstra 또는 A* 기반으로 수행된다.
• 시간복잡도:
  • 전처리 : CH와 달리 복잡한 노드 Contraction 과정이 없음 (상대적으로 단순한 구조)
  • 질의 (query) : ms 단위 (매우 빠름)

MLD는 단순히 지도를 나누는 방식이 아니라, 각 셀 내부의 boundary node 간 최단 거리를 미리 계산하여 상위 레벨의 overlay graph를 구성하는 구조이다. 즉, 실제 도로망과 요약된 상위 그래프를 함께 사용하는 다단계 탐색 구조라고 볼 수 있다.

MLD의 중요한 특징은 분할 구조가 가중치와 독립적이라는 점이다. 가중치가 변경되더라도 partition 자체는 유지되며, boundary 간 거리 계산만 갱신하면 된다. 이러한 특성 덕분에 실시간 교통 정보를 비교적 유연하게 반영할 수 있다.

다만 partition 품질에 따라 성능이 크게 달라질 수 있으며, 분할이 적절하지 않으면 탐색 범위가 예상보다 넓어질 수 있다.

 

2-3. 상용 네비게이션은 어떤 알고리즘을 사용할까? 

네이버 지도, 카카오 지도, 구글 지도, 티맵과 같은 상용 네비게이션이 실제로 어떤 알고리즘을 사용하는지 조사했다. 아래 공식 기술 블로그와 공개된 자료를 읽어보며 내용을 정리했다.

[티맵 참고 자료]

https://www.tmapmobility.com/support/data/path/about?utm_source=chatgpt.com

TMAP MOBILITY

https://brunch.co.kr/@tmapmobility/3

네비 개발자여, 번개처럼 빠른 경로탐색엔진을 만들라

 

[카카오맵 참고자료]

https://tech.kakao.com/posts/436

카카오맵이 빠르게 길을 찾아주는 방법: CCH를 이용한 개편기 - tech.kakao.com

 

티맵 (T map Mobility)

티맵 경로탐색 엔진에 대한 공식 기술 블로그에 따르면, 경로탐색 엔진은 처음에는 A* 알고리즘 기반으로 만들어졌으나, 시간 및 확장성 문제 때문에 발전해왔다. 그 과정에서 CCH (Customizable Contraction Hierarchies) 기반의 Thor 엔진을 도입했다.

• 초기 엔진은 A* 알고리즘 기반이었다.
• 이후 CCH 기반 알고리즘으로 발전하여 빠르고 확장성 있는 길찾기 처리를 하고 있다.
• 티맵 서비스 페이지에서도 “실시간 교통정보 + CCH 알고리즘 기반으로 경로 안내”라고 소개하고 있다.

CCH는 CH 알고리즘 기반으로, 그래프 전처리 단계에서 중요한 구조(shortcut)를 생성한 뒤 실시간 교통정보 등 변화에 쉽게 대응할 수 있도록 커스터마이즈 단계가 분리된 알고리즘이다. CH 대비 실시간/변경 대응이 유리하고 큰 그래프에서도 빠른 탐색이 가능하다는 점이 티맵 측에서도 기술적으로 선택 이유로 설명된다.

 

카카오맵 (Kakao Map)

카카오 기술 블로그에서도 CCH 알고리즘 관련 언급이 있다. 길찾기 성능을 개선하기 위해 CCH를 활용한다는 설명이다.

• 카카오맵 기술블로그에서 CCH 알고리즘을 이용한 개편 사례를 다루고 있다.
• 여기에 따르면 도로 네트워크 기반 그래프 → 최단 경로 생성 → 경로 후처리 과정이 길찾기 성능의 핵심이며 CCH가 성능 개선에 기여한다고 소개된다.

카카오맵은 전통적인 최단 경로 탐색만으로는 빠른 응답을 보장하기 어렵기 때문에 전처리된 그래프 구조 + CCH 기반 탐색 방식을 활용하여 응답 성능을 높이고 있다.

 

다른 네비게이션 서비스도 대규모 도로망에서 빠른 응답과 실시간 교통 반영을 처리하기 위해 CCH나 MLD와 같은 전처리 기반 + 가중치 갱신이 가능한 알고리즘 구조를 활용하고 있을 것으로 예상된다.

실제 오픈소스 경로 탐색 엔진(OSRM, GraphHopper 등)들도 동일한 문제를 해결하기 위해 계층적 전처리 기반 구조를 채택하고 있다는 점에서 상용 서비스 또한 유사한 접근을 사용했을 가능성이 높다고 보았다.

 

상용 네비게이션과 오픈소스 라우팅 엔진의 알고리즘 알아보니, 다음과 같은 궁금증이 생겼다.

1. 티맵이나 카카오맵은 왜 MLD가 아니라 CCH를 선택했을까? 

CCH는 CH 계열 알고리즘으로 전처리 이후 질의 속도가 매우 빠르다.
또한 그래프 구조와 가중치를 분리하기 때문에 가중치 변경 시 shortcut 비용만 재계산하면 된다. 이 구조는 실시간 교통이 반영되는 환경에서 빠르고 일관된 응답 시간을 유지할 수 있다.

MLD 역시 매우 빠른 알고리즘이지만, partition 품질에 따라 성능 편차가 발생할 수 있다. 반면 CCH는 계층 기반 구조를 활용하기 때문에 질의 성능이 비교적 안정적으로 유지된다.

또한 CH 계열은 도로 중요도 기반 계층 구조를 형성하기 때문에 고속도로 중심 탐색, 복잡한 골목길 회피 같은 정책을 설계하기에도 적합하다. 따라서 상용 네비게이션 환경에서 CCH가 요구사항에 더 적합했을 가능성이 있다.

 

2. 오픈소스 경로 탐색 엔진인 Open Source Routing Machine(OSRM)은 왜 기본 알고리즘으로 MLD를 선택했을까?

OSRM은 자동차, 자전거, 도보 등 여러 프로파일을 지원한다.
MLD는 partition 구조와 가중치가 분리되어 있어 여러 프로파일을 유연하게 적용하기 쉽다.

또한 전 세계 규모의 그래프를 대상으로 할 경우, CH 계열은 강한 전처리를 수행해야 하며 메모리 사용량과 빌드 시간이 크게 증가할 수 있다. 특히 CCH는 구현 복잡도가 높고 메모리 요구량도 상대적으로 큰 편이다.

반면 MLD는 CH보다 전처리 과정이 비교적 단순하며, 대규모 그래프에 대해 현실적인 빌드 시간과 자원 요구 수준을 유지할 수 있다.

이러한 조건을 고려해 OSRM은 MLD를 기본 알고리즘으로 채택한 것으로 볼 수 있다.

 

즉, 상용 서비스는 응답 시간의 일관성과 정책 반영, 오픈소스 엔진은 유연성과 범용성을 더 중요하게 고려했을 가능성이 있다.

3. 최적의 경로란 무엇인가?

우리는 "최적 경로"라는 말을 자연스럽게 사용한다. 그런데 최적이란 무엇일까?
거리가 짧은 경로일까? 시간이 가장 적게 걸리는 경로일까?

초보 운전자에게는 유턴이나 복잡한 좌회전이 적고, 골목길 대신 직선 위주의 큰 도로가 더 편한 경로일 수 있다.
반대로 숙련된 운전자라면 약간 복잡하더라도 더 빠른 지름길을 선호할 수도 있다.

결국 최적은 절대적인 개념이 아니라, 어떤 기준(cost)을 최소화하느냐에 따라 달라지는 상대적인 개념이다.

 

알고리즘 관점에서의 "최적"

경로 탐색 알고리즘에서 최적 경로란 보통 "정의된 비용 함수(cost function)를 최소화하는 경로"로 같이 정의된다.

여기서 비용은 단순 거리일 수도 있고, 예상 소요 시간(ETA)일 수도 있으며, 아래와 같이 다양한 요소가 조합된 값일 수도 있다.

Cost = 거리 × α 
      + 예상 소요 시간 × β 
      + 교차로 수 × γ 
      + 톨게이트 비용 × δ 
      + 위험도/복잡도 × ε

 

α, β, γ와 같은 가중치(weight)에 따라 완전히 다른 최적 경로가 나온다.

즉, 최적의 경로는 하나가 아니라 설정된 목적 함수에 따라 달라지는 결과다.

 

사용자 관점에서의 "최적"

네비게이션 앱에는 보통 이런 옵션들이 존재한다.

• 최단 거리
• 최소 시간
• 무료 도로 우선
• 고속도로 우선/회피
• 추천 경로

이는 결국 사용자가 어떤 비용을 중요하게 생각하는지를 선택하는 과정이다.

예를 들어:

• 택시 기사 → 회전율을 높이기 위해 시간 최소화
• 초보 운전자 → 복잡도 최소화
• 전기차 사용자 → 충전소 접근성 포함

이처럼 "최적"은 사용자 맥락(Context)에 따라 달라진다.

 

시스템 관점에서의 "최적"

상용 네비게이션은 단순히 한 사용자만을 위한 최적화가 아니라, 전체 교통 흐름까지 고려하는 경우도 있다.

예를 들어 모든 차량을 동일한 지름길로 보내면 그 길은 곧 정체가 발생해 최적이 아니게 된다.

따라서 일부 서비스는:

• 교통 분산(Routing Diversification)
• 수요 예측 기반 가중치 조정
• 혼잡 완화 모델

등을 통해 "전체 시스템 관점에서의 준최적"을 선택할 가능성도 있다.

 

이와같이 최적 경로는 하나의 정답이 있는 개념이 아니다.

최적 경로란, 특정 목적 함수와 사용자 맥락을 기준으로 비용을 최소화한 결과이다.

즉, 네비게이션에서 말하는 최적이란 단순히 가장 짧은 길이 아니라, 정의된 조건 아래에서 가장 합리적인 선택이라고 볼 수 있다.

 

그렇다면 아래와 같은 질문이 생긴다.

1. 시스템 관점의 최적이 사용자 관점의 최적이 아니라면, 사용자는 경로를 믿어도 되는가?

네비게이션이 계산하는 최적은 보통 예상 소요 시간(ETA) 최소 또는 정의된 비용 함수 최소다.
이는 대규모 데이터 기반으로 계산된 통계적 예측 결과다.

하지만 사용자가 체감하는 최적은 다를 수 있다.

좌회전이 많으면 불편할 수 있고, 좁은 골목길은 부담스러울 수 있으며 약간 막히더라도 큰 도로가 더 편할 수도 있다

네비게이션은 개인 감정 기반 최적이 아니라 데이터 기반 확률적 최적을 제공한다.

상용 서비스는 다수 차량의 GPS 속도 데이터, 과거 시간대별 평균 속도, 사고나 공사 등 이벤트 정보와 같은 신뢰할 수 있는 데이터를 활용한다.

이러한 데이터는 개인의 직관보다 통계적으로 더 정확한 경우가 많다.
다만 완전한 개인 맞춤 최적은 아니기 때문에 최단 거리, 고속도로 우선, 유료도로 회피 등의 옵션을 통해 사용자가 비용 모델을 일부 선택하도록 설계되어 있다.

결론적으로, 네비게이션은 평균적으로 신뢰할 수 있는 최적을 제공한다.
다만 자신의 운전 성향에 맞게 옵션을 조정하는 것이 가장 합리적이다.

 

2. 모든 사람이 같은 앱을 쓰지 않는데 교통 분산은 어떻게 이루어질까?

교통 데이터는 한 앱의 정보만으로 구성되지 않는다.

상용 네비게이션은 자사 앱 GPS 데이터, 공공 교통 데이터 등 수집할 수 있는 여러 데이터를 함께 활용한다. 따라서 특정 앱 하나가 전체 교통을 완전히 통제하는 구조는 아니다.

이때 만약 여러 앱이 동일한 지름길을 추천하는 상황이 발생될 수 있을까?

이론적으로는 가능하다. 이 현상은 연구 분야에서 Self-fulfilling congestion(자기실현적 혼잡)으로 불린다.

이를 완화하기 위해 일부 서비스는 유사 시간의 복수 경로를 생성, 일부 사용자에게 대안 경로 제시, 교통량 증가 시 도로 가중치 조정 등의 전략을 사용하는 것으로 알려져 있다.

즉, 현대 네비게이션은 단순 경로 탐색기가 아니라 실시간 수요와 공급을 반영하는 동적 시스템에 가깝다.

4. 추천 경로는 무엇을 바탕으로 할까?

추천 경로는 단순 최단 경로가 아니다. "예상 소요 시간(ETA, Estimated Time of Arrival)을 최소화하는 경로"에 가까울 것이다.

예를 들어, A 경로가 10km, B 경로가 12km라고 하더라도
A 경로가 정체로 평균 속도 20km/h라면 약 30분이 소요되고,
B 경로가 평균 속도 60km/h라면 약 12분이 소요된다.

이 경우 시스템은 B 경로를 추천할 것이다.
즉, 거리보다 시간(cost) 이 더 중요한 최적화 기준이 된다.

 

추천 경로에는 실시간 교통 상황, 과거 주행 데이터, 도로 이벤트 정보, 사용자 특성 등 다양한 요소들이 종합적으로 반영된다.

1. 실시간 교통 정보

• 현재 구간별 평균 주행 속도
• 차량 밀집도 (probe data 기반)
• 정체 구간 길이
• 사고, 통제, 차로 축소 정보

이는 수많은 사용자 단말기로부터 수집되는 GPS 데이터(Probe Data)를 기반으로 계산된다.
특정 도로 구간의 평균 속도가 급격히 낮아지면 해당 엣지(edge)의 가중치가 증가한다.

 

2. 과거 평균 속도 (Historical Traffic Pattern)

실시간 데이터만으로는 부족하다.
예를 들어 새벽 3시에는 차량이 거의 없기 때문에 과거 패턴이 더 중요할 수 있다.

• 요일별 평균 속도
• 시간대별 평균 소요 시간
• 출퇴근 패턴
• 명절/휴일 특성

따라서 많은 네비게이션은 "실시간 데이터 + 과거 패턴"을 혼합하여 가중치를 계산한다.

 

3. 사고 / 공사 / 이벤트 정보

• 교통 통제
• 도로 폐쇄
• 공사 구간
• 대형 행사

이 정보는 보통 별도의 교통 센터, 지자체 API, 사용자 신고 데이터를 통해 수집된다.
해당 구간은 가중치를 매우 크게 주거나, 경우에 따라 그래프에서 제거되기도 한다.

 

4. 사용자 주행 패턴

일부 네비게이션 서비스는 사용자 이력을 기반으로 한 제한적인 개인화 기능을 제공한다.

예를 들어:

• 자주 방문하는 장소(집, 회사 등) 자동 인식 및 빠른 경로 제안
• 출퇴근 시간대 이동 패턴 기반 예상 소요 시간 안내
• 최근 검색 또는 최근 이동 경로의 우선 노출
• 사용자가 설정한 옵션(고속도로 회피, 유료도로 회피 등)에 따른 경로 필터링

5. 신호 대기와 교차로 요소

단순 도로 길이뿐 아니라 교차로 통과 시간과 같은 요소들도 전체 소요 시간에 영향을 준다

• 교차로 위치 및 연결 구조
• 신호등 존재 여부
• 좌·우회전 가능 여부 및 제한 정보
• 회전 금지(turn restriction) 정보

 

 

 

이번 글을 정리하며..
“경로란 무엇인가?”,
“최적이란 무엇인가?”,
“추천 경로는 어떤 과정을 거쳐 만들어지는가?”

와 같은 질문에 대해 하나씩 개념을 정리해보는 시간을 가졌다.

우리가 일상적으로 사용하는 네비게이션은 단순한 최단 거리 계산이 아니라,
다양한 알고리즘과 가중치 모델, 계층 구조 위에서 동작한다는 점을 확인할 수 있었다.

이어서 오픈소스 라우팅 엔진인 OSRM 실습을 해 볼 예정이다.