[CONF] DEVIEW 2020: 그래서, 네이버내비가 주는 길은 뭐가 다른데

👀 네이버내비의 경로추천

네이버내비가 경로를 추천해주는 방법에 대해서 알아본다.

✔ 기존 경로 제공 방법

기본적으로 경로 제공 방법은 다음과 같은 순서를 따른다

1. 출발지, 목적지, 탐색옵션 설정
2. 길찾기 서버 + 도로네트워크 데이터 + 교통정보를 분석
3. 경로 제공

기존에는 이러한 과정에서 가중치를 두는 방식으로 경로를 제공했다. 이를테면 가장빠른(시간), 무료우선(요금), 큰길우선 또는 이륜차 우선(도로 종류)에 가중치를 주는 방식으로 말이다.

✔ 다양한 경로를 제공할수는 없을까?

기존 방식은 최적화된 도로에서 크게 벗어나지 않는 여러개의 경로를 제공하였다. 이를테면 내비게이션은 강남과 강북을 지나는 길로 성수대교를 꼭 지나치게 하고 나머지 세세한 경로만 바꾸는 식이다.

하지만 사용자들은 자신이 익숙한 길이나 동호대교, 또는 영동대교를 선택했을때의 가능성도 궁금해한다. 고속도로에서도 마찬가지이다. 이 고속도로를 추천해 주는데, 내가 익숙한 다른 고속도로는 어떨지와 같은 것들을 궁금해한다는 것이다.

✔ 양방향 알고리즘의 활용

로드 네트워크 데이터는 양방향의 양수가중치를 갖는 비정형 그래프 데이터이다. 이에 사용 가능한 다익스트라 알고리즘은 최적의 경로를 찾는데에는 적합하지만, 다양한 경로를 제공하는데에는 적합하지 못하다. 따라서 다익스트라 알고리즘을 기반으로 양방향 A* 알고리즘을 추가로 채택해 다양성을 높였다.

양방향 알고리즘의 과정은 1. 정방향 확장과 역방향 확장을 통해 후보링크를 생성, 2. 다수의 후보링크로 후보 경로를 생성하는 과정을 거친다.

그 과정 중 고려해야 할 것은, 후보링크가 최적화된 경로와 일정 이상의 비용차이가 발생하게 되면 대안경로로 부적합하다는 것이며, 이 과정에서 링크의 세부속성, 출발지/목적지까지의 거리, 확장시의 비용, 인접링크와의 연결성 등을 고려한다.

각각 후보링크들은 유사도(경로간 중복률, 중복링크의 특성, 도로네트워크 속성 등을 고려)를 기준으로 클러스터링 한 후, 각각의 클러스터들을 비용순으로 정렬하면 유의미한 다양한 경로 제공이 가능하다.

이를 통해 네이버내비는 경로의 다양성을 208% 상승시키고, 응답시간또한 77% 상승시킬 수 있었다.

✔ 발전 가능성

네이버내비가 앞으로 나아가야 할 길은 다음과 같다.

1. 정확한 소요시간 제공
   실시간 궤적정보 수집과 수집된 궤적정보를 도로에 매칭하는 것으로 실시간 교통정보를 정확히 생성해 내는것이 첫번째 과제이다. 또한 소요시간을 제공하는 데에는 실시간교통정보와 예측교통정보를 조합해서 사용하는데, 가중치를 얼마나 둘 것인지에 대한 의사결정 또한 발전시켜 나가야 할 것이다.
2. 정체 전파
   사고나 어떠한 원인으로 인해 정체가 있을 때 해당 정체가 어떤 흐름으로 전파되는지에 대한 분석을 해나간다.
3. 경로에 대한 개인화
   개인의 시간, 요금, 도로 등에 대한 선호도에 따라서 경로를 개인화해서 제공하는 것이 내비게이션의 미래일 것이다.

👍 참고 사이트

1. 그래서, 네이버내비가 주는 길은 뭐가 다른데