카카오 T 에서 최단거리를 탐색하는 방법

 

 

 

---

 

 

🎯 글을 쓰게 된 이유

 

 

 

현대 사회를 살아가는 사람들이라면 누구나 택시를 타 본 경험은 있을 것이다.

옛날에는 택시를 타기 위해서는 택시 정류장에 가서 기다리거나,

대부분 길거리에서 '빈차' 가 표시되어 있는 택시를 향해 손을 흔들어서 택시를 타곤 했다.

 

하지만 요즘, 모두는 모르겠지만 내 주변을 기준으로 보자면 택시를 타는 방법의 100에 90은 카카오T 서비스를 이용한다.

물론 나 또한 택시 정류장이 있어도 카카오T를 먼저 호출해보는 편이다.

 

그만큼 우리들의 삶에 깊게 들어와있는 카카오 T 서비스, 나는 이 서비스를 이용하며 항상 불만이 있었다.

 

"저기로 가는게 더 빠른데, 왜 이 길로 가는거지??"

 

사실 택시 기사님들이야, 우리가 택시를 잡았을 때 주어지는 최단 경로를 따라 운전하실 뿐이지,

문제는 카카오 T 서비스의 최단 경로 탐색에 있다고 생각했다.

 

그래서 이번엔 카카오 T에서 어떤 방식으로 최단 경로를 찾아주는지 확인해보고자 한다.

 

 

---

 

 

 

💡 카카오 맵에서 사용하는 길찾기 알고리즘

 

 

일단 카카오 T의 경로 탐색 서비스는 카카오 맵을 사용할 것이라는 전제를 깔고 가야할 것 같다.

카카오 맵에서는 일반적으로 다음과 같은 과정을 거친다.

 

1. 도로 형상에서 그래프 형태의 도로 네트워크 구축
2. 출도착점에서 적절한 출도착 간선 선택
3. 경로 탐색 알고리즘으로 최단 경로 생성
4. 경로 후처리 및 가이드 생성

도로의 형상이나 정보와 같은 것들을 어떻게 가져오는지는 모르겠지만, 도로 정보을 토대로 Node화 시켜서

도로 네트워크를 구성한 후, 경로 탐색 알고리즘으로 최단 경로를 생성한다.

 

내가 알고 있는 경로 탐색 알고리즘에는

• BFS
• 다익스트라
• 플로이드 워셜
• 밸만-포드
• A* 알고리즘

이렇게 5가지가 있다.이 중 어떤 방식을 사용하는지 찾아보기전에 내가 먼저 고민을 해보자면

 

결국 경로 탐색 알고리즘이 작동하기 위해서는 간선에 '가중치' 라는 것이 포함되어야 한다.

도로 네트워크 내에서의 노드간 간선의 가중치는 아마 도로의 상태 (공사중이거나, 차가 많이 막힌다거나), 어린이 보호구역, 시속 제한 등등 많은 여러 요소들을 감안하여 결정될 것으로 예상하고 있다.

 

이러한 교통 정보들을 토대로 출발지 노드에서 도착지 노드까지의 

경로 탐색 알고리즘을 통해 최단 경로 Route를 줄 것이라고 생각된다.

 

AI가 포함되어 있지 않을까? 라는 생각도 해보았지만, 어차피 경로 탐색 알고리즘을 돌리는거라면, 굳이 AI가 있을 필요가 없다.

그냥 API 호출을 통해 서버에서 경로를 계산하면 끝이기 때문이다. (물론 내 생각... AI가 있을 수 있음...)

 

그럼 여러가지의 경로 탐색 알고리즘 중 어떤 알고리즘을 사용할까?

카카오맵의 최단 경로 탐색 요구사항은 아래와 같다.

 

• 출발지 한 지점에서 도착지 한 지점까지의 최단거리
• 가중치는 값이 다른 양수 (음수일 수 없을 것 같음)
• 현재 교통 정보에 따라 가중치를 계산할 것

 

물론 3번째 요구사항은 API가 호출 될 때 마다 교통 정보를 계산하는 것이 아닌, 주기적으로 도로 네트워크를 업데이트 시켜주는 Batch를 사용하지 않을까 싶다.

 

어차피 한 지점에서 다른 한 지점까지의 최단거리를 구하는 것이라면, 플로이드 워셜이나, 밸만-포드를 사용할 필요가 없고,

가중치가 모두 같지 않으니 BFS또한 사용하지 못한다.

 

따라서 아마 다익스트라나 A* 알고리즘을 이용하여 경로 탐색을 하지 않을까 예상해보며,

실제 카카오맵에서는 어떻게 하고 있는지 알아보자.

 

 

---

 

 

 

해당 정보는 카카오 테크 블로그에 올라와 있는 카카오 맵의 경로 탐색 알고리즘에 대한 글을 보고 알아냈다.

글을 읽어보니, 기존의 서비스는 예상대로 A* 알고리즘을 사용하여 경로를 탐색하고 있었다.

 

하지만 늘어나는 트래픽과 먼 목적지까지의 경로를 A* 알고리즘이 감당하기에는 성능상에 이슈가 있었고,

그 대체제로 CH 알고리즘을 생각했지만, 이 또한 실시간으로 바뀌는 교통정보를 처리하는데 문제가 있어,

현재는 CCH 알고리즘을 사용하고 있다고 한다.

 

그럼 각각의 알고리즘이 어떤 것인지 간단하게 알아보자

 

 

---

1. A* 알고리즘

1. 개념

A* 알고리즘(A-Star Algorithm)은 주어진 출발점에서 목표점까지의 최단 경로를 찾는 그래프 탐색 알고리즘입니다.

1968년 피터 하트, 닐스 닐슨, 버트램 라팰에 의해 개발되었으며,

현재까지도 네비게이션과 게임 AI에서 가장 널리 사용되는 경로 탐색 알고리즘입니다.

 

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘으로,

휴리스틱 함수를 사용해 목적지 방향을 우선적으로 탐색합니다.

 

2. 다익스트라와의 차이점

다익스트라: 출발점에서 모든 방향으로 균등하게 퍼져나가며 탐색

A*: 목적지 방향을 우선적으로 탐색 (휴리스틱 사용)

 

A* 알고리즘은 다익스트라 알고리즘을 확장시킨 알고리즘으로, 큰 차이는 휴리스틱 사용에 있다.

 

3. 휴리스틱이란?

휴리스틱 = "경험칙" 또는 "추정법"

완벽하진 않지만 "대충 이 정도일 것 같아"라고 빠르게 추정하는 방법이다.

즉, 좀 더 좋아보이는 경로를 대충 예측하는 것을 휴리스틱이라고 이해하면 된다.

 

A* 알고리즘에서의 메인 포인트는 이 휴리스틱으로, 휴리스틱 값을 계산하는 방법도 여러가지이다.

휴리스틱 계산 방법에 대해서는 이번 글에서는 굳이 다루진 않겠다. 수학 공식이 난무한다.

난 찾아보고도 이해 못했다.

 

4. 성능

시간 복잡도

• 최악의 경우: O(b^d)
  • b: 분기 계수 (각 노드의 인접 노드 수)
  • d: 해의 깊이
• 평균적으로: 휴리스틱의 품질에 따라 크게 개선

공간 복잡도

• O(b^d): 모든 노드를 메모리에 저장해야 함

 

5. 장단점

장점

• 최적성 보장 : 적절한 휴리스틱 함수를 사용하면 항상 최단 경로를 보장합니다.
• 효율성 : 다익스트라보다 목적지 방향으로 똑똑하게 탐색하여 탐색 범위를 크게 줄입니다
• 유연성
  • 다양한 휴리스틱 함수 적용 가능
  • 실시간 환경 변화에 대응 가능
  • 가중치 조정으로 성능 튜닝 가능

 

단점

• 메모리 사용량 : 모든 탐색 노드를 메모리에 저장해야 하므로 메모리 사용량이 많습니다.
• 휴리스틱 함수 의존성
  • 부정확한 휴리스틱은 성능 저하 야기
  • 휴리스틱 설계가 어려운 경우가 있음
• 동적 환경의 한계 : 환경이 자주 변하면 매번 새로 계산해야 합니다.
• 대규모 그래프에서의 한계
  • 노드 수가 많아질수록 성능 저하
  • 실시간 처리에 부담

---

2. CH (Contraction Hierarchies) 알고리즘

1. 개념

효율적인 지름길을 만들어놓고 지름길을 통해 필요한 곳만 탐색하는 알고리즘이다.

정점에 랭크를 매기고, 랭크가 낮은 순서대로 정점 추출며 지름길을 만드는 Contraction이라는 작업을 한다.

그렇기 때문에 Contraction(단축 경로를 생성해서) Hierarchy(계층을 두고 탐색)이라는 이름을 가지게 된 것이다.

 

2. 노드의 랭크는 어떻게 산정??

CH에서 노드의 랭크(중요도)는 주로 Edge Difference(ED)라는 지표로 결정된다.

Edge Difference = 제거되는 간선 수 - 생성되는 지름길 수

즉, ED는 노드의 연결된 간선 수에서 해당 노드를 제거할 때 생성해야 하는 지름길 수를 뺀 값이다.

 

3. 성능

시간 복잡도

• 전처리: 매우 오래 걸림 (한 번만 수행)
• 쿼리: 다익스트라 알고리즘보다 몇 배 빠른 쿼리 성능
• 특징: 거리와 거의 상관없는 균일한 쿼리 성능

공간 복잡도

• O(b^d): 모든 노드를 메모리에 저장해야 함

 

4. 장단점

장점

• 극도로 빠른 쿼리 : 놀랍게도 우선순위 큐를 사용하지 않고 탐색을 한다
• 일관된 성능 : 거리에 상관없이 균일한 성능 (서울-부산이나 강남-홍대나 비슷한 속도)
• 확장성 : 대규모 도로 네트워크에서도 안정적인 성능

 

단점

• 동적 변화 대응 어려움 : 도로가 침수되어 이용을 하지 못한다거나, 인파가 많아져서 이동시간이 길어지는 등의 비용 변화가 생기면 CH는 처음부터 다시 지름길을 만들어주는 작업을 해줘야 하기 때문에 실시간성 이슈에 대응을 하기 힘들다

---

 

CH 설명 마지막에 있는 단점인 실시간 교통 정보가 바뀔 때 마다 가중치가 변경되어서 지름길을 다시 계산해야된다는 점 때문에,

CH를 사용하지 않고, CH를 보완한 CCH를 카카오맵에서 사용하게 된다.

 

3. CCH (Customizable Contraction Hierarchy) 알고리즘

1. 개념

비용에 상관없이 그래프의 연결 관계가 같다면 항상 같은 지름길이 생기고,

여기서 일부 비용이 바뀐다고 해도 그 부분과 연관된 일부 지름길의 비용만 수정하기 때문에

굉장히 빠르게 실시간 비용 변경을 적용할 수 있는 CH를 보완한 알고리즘

 

2. CH와의 차이점

• CH: 비용이 바뀌면 전체 지름길을 처음부터 다시 계산
• CCH: 지름길 구조는 유지하고 비용만 업데이트

 

3. 장단점

장점

• 실시간 비용 적용 : 도로가 침수되어 이용을 하지 못한다거나, 인파가 많아져서 이동시간이 길어지는 등의 비용 변화에 굉장히 빠르게 실시간 비용 변경을 적용할 수 있다
• CH의 모든 장점 유지 : 극도로 빠른 쿼리 성능과 일관된 성능 특성 그대로 보존

 

단점

• 높은 초기 전처리 비용 : CH보다도 더 복잡한 전처리 과정 필요
• 복잡한 구현 : 3단계 처리 과정으로 인한 시스템 복잡도 증가
• 토폴로지 변경 한계 : 도로 구조 자체가 바뀌면 여전히 전처리부터 다시 수행해야 함

 

---

 

🖌️ 결론

 

카카오 맵의 최단 경로 탐색이 내 맘에 안들었던 이유는 알고리즘에 있는 것이 아니었다.

알고리즘은 그저 가중치에 맞게 최단 경로를 탐색해줬을 뿐, 문제는 가중치 산정에 있었다.

 

물론 이것도 가중치를 어떻게 산정 하는지 정확히 알지 못하기 때문에, 확실한 정보는 아니지만

어린이 보호구역, 제한속도, 왕복 차선, 신호 개수 등등 여러가지 요소를 따져 보았을 때, 제일 적절한 경로를 찾아준 것 같다.

 

별도로 글을 쓰는 와중에 들었던 생각이,

우리집이 신축 아파트라 아직 교통 정보가 제대로 파악되지 않았기 때문일 수도 있을 것이라는 생각이 들었지만, 네이버맵에서는 도로 네트워크 데이터 팀이 따로 있다고 한다. 그래서 해당 팀에서 교통 정보 관련 데이터를 받는다고 하며, 카카오맵도 데이터 정보 플랫폼 팀이 있어 여기에서 공사 정보와 같은 교통 정보를 꾸준히 업데이트할 것으로 판단되어,

해당 이유는 아닌 것 같다는 결론이 나왔다

 

 

 

어떤 방식으로 가중치를 선정하기에, 누가 봐도 저기로 가는게 더 빠른데 이렇게 갈까는 명확하게 알 수 없었지만,

그래도 이번 공부로 카카오 팀에서 굉장히 노력하고 있다는 걸 알 수 있었기에,

이제는 내가 원하는 경로가 아니더라도 그러려니 할 수 있을 것 같다.

 

 

 

결론 : 경로 탐색 알고리즘 자체에는 문제가 없고, 문제는 도로 네트워크 노드간의 가중치 계산에 있을 것이라 판단됨