티맵 길찾기 더 빨라진다..."토르 알고리즘 적용"

이용자가 접할 수 있는 길안내 선택지가 늘고, 목적지 검색 후 대기시간이 줄어든다. 장거리 경로의 경우, 응답시간이 100배 이상 빨라진다. 터널 진입 시 끊김 현상도 최소화한다. 개개인 이용 패턴을 반영해, 이전보다 최적화한 경로를 제공한다.

티맵 서비스가 이렇게 개편된다. 티맵모빌리티는 기존 서비스 알고리즘이 지닌 한계를 넘어 이용 편의성을 높일 수 있도록 새로운 알고리즘을 적용하기로 했다.

티맵 새 알고리즘 프로젝트명은 일명 ‘토르’. 북유럽 신화에 나오는 번개의 신에서 착안해 번개처럼 빠른 반응속도의 서비스를 제공하겠다는 의미를 담았다.

"토르 알고리즘, UX 개선 최우선 목표…최적경로 빠르게 제공"

김재순 티맵 모빌리티플랫폼 담당(그룹장)은 “티맵 사용자경험(UX) 개선을 최우선 목표로 토르 알고리즘을 도입했다”며 “예상도착시간(ETA)과 실제도착시간(ATA) 간 오차나 이용자 불편을 최소화해, 서비스 신뢰도를 더욱 높였다”고 운을 뗐다.

김재순 티맵 모빌리티플랫폼 담당이 지난달 31일 지디넷코리아와 인터뷰하고 있다.

그간 최단거리를 안내하는 다익스트라(알고리즘) 체계에서 진화한 에이스타(Astar) 알고리즘은 목적지까지 경우의 수를 활용해 성능값을 크게 높였다. 에이스타는 출발지에서 목적지 방향으로 모든 데이터값을 탐색하는 형태라 그래프 크기가 커질수록 성능이 느려진다는 단점이 있다.

많은 도로가 개통되고 교통 상황이 수시로 변하면서 네트워크 크기가 나날이 커지는 동시에, 티맵 이용자수도 늘어나 점점 서버 과부하가 발생한다는 뜻이다.

이같은 문제를 해결하기 위해 티맵은 CCH(Customizable Contraction Hierarchies) 기반 알고리즘으로 서비스 엔진을 다듬었다.

김재순 그룹장은 “출발지를 서울역으로 부산역까지 티맵에 검색한다고 가정하면, 에이스타 알고리즘은 계산량에 따라 짧게는 3초, 최악의 경우 6초가 지난 뒤에야 경로를 제공하며 편차가 컸다”고 설명했다.

이어, “토르 알고리즘을 통해선 최소시간 내 결과를 도출할 수 있어 쾌적하게 이용할 수 있다”고 강조했다.

"트래픽 몰려도 끄떡없다"…시간의존적 조건 따라 최단경로 탐색

이 알고리즘은 전처리화(preprocessing), 커스터마이제이션(customization), 경로쿼리(path query) 세 단계를 거친다.

우선 전처리화 단계에선 도로 데이터를 중요도 순서로 정렬한 다음, 그래프를 최적화해 최단경로를 생성한다. 도로 데이터가 변경될 때마다 전처리화가 반복된다.

티맵은 보통 1~2주에 한 번씩 모든 데이터 연산을 이처럼 전처리화한다.

이후 커스터마이제이션을 통해 실시간 교통정보, 유고정보 등을 경로에 반영해 1분마다 최단경로를 최신화하는데, 이때 중요도 기준으로 도로 데이터가 정렬된다.

마지막 경로쿼리에서 최단경로를 포함한 그래프를 두 개로 쪼개, 최적의 경로 결과값을 이용자에게 전달한다.

명절과 같이 티맵 이용량이 급등해 트래픽이 몰리게 되면, 토르 알고리즘이 유용하게 쓰인다.

김 그룹장은 “단거리든, 장거리든 큰 차이 없이 계산량이 비슷하기 때문에 최적 목적지를 바로 제시해준다”며 “커스터마이제이션에서 예상 통과 시점의 교통정보, 즉 시간 의존적(특정 시간대 교통상황 등) 조건에 따라 최단경로 탐색이 가능하다”고 강조했다.

이용 편의성 높이고, 인프라 비용 줄고

김 그룹장은 토르 알고리즘 특장점으로 매트릭스(Matrix) API를 꼽았다.

매트릭스 API는 출발지 1곳에서 도착지로 경로를 탐색하는 대신, n개 출발지와 m개 도착지로 예상되는 경로값을 확장하는 방식이다. 이를테면 기존 알고리즘이 2개 출발지와 3개 도착지로 5개(n+m) 경로를 제공했다면, 토르 알고리즘은 6개(n*m)를 제공한다는 의미다.