배경
생각나는 순서로 일정을 짜다보면 이동경로가 비효율적으로 될 경우가 생길 수 있다.
출발지만 선택하고 경로를 최적으로 추천받는 기능이 있으면 좋겠다.
지점 간의 경도와 위도로 단순한 직선 거리를 비교하는 것이 아니라 지점 간의 실제 이동거리로 경로를 추천하고 싶다. 따라서 카카오 모빌리티 Api를 통해 이동거리를 받아서 비교 기준으로 두고 싶다.
구현한 기능
FE
길찾기의 기준, 출발지 선택
경로 추천의 기준이 되어줄 수 있도록 가장 처음 등록한 장소를 출발지로 등록하고, 사용자가 원하는대로 지정할 수 있도록 출발지 선택 기능을 추가하였습니다.
등록된 여행 일정을 백엔드로 보내면 백엔드에서 카카오 모빌리티를 통해 실제 거리 데이터를 가지고 양방향으로 최적의 경로를 찾아주고, 최적 동선으로 정렬된 데이터를 가지고 프론트에서 맵 위에 마커와 Polyline을 다시 생성합니다.
BE
카카오 모빌리티 다중 목적지 API
다중 목적지 API를 사용한 이유는 적은 API호출로 모든 지점간의 양방향 거리를 구할 수 있기 때문으로, 최대 30개의 목적지를 검색할 수 있기 때문에 최대 10개의 지점의 양방향 거리를 10번의 api호출 만으로 알아낼 수 있습니다.
완전탐색을 사용해서 최적 경로를 정렬하여 반환
당일치기라는 컨셉으로 인해 최대 일정 수가 10개로 제한 되어 있고, 출발지가 정해져 있기 때문에 모든 지점의 거리를 완전탐색으로 구현하더라도 9!의 시간복잡도로 해결 가능하다고 생각이 들어 완전 탐색을 통한 최적의 경로 추천을 구현하였습니다.
추가적으로 구현하고 싶은 기능
•
지점간 거리를 다중 경유지 api로 변경하기
현재는 다중 목적지 api로 구현하여서 지점간 최대 반경이 10km로 제한 되어 있기 때문에 출발점과 목적지 사이의 거리가 최대 반경을 넘어서게 되면 거리를 추천해 주지 못하는 경우가 생기고 있습니다.
따라서 다중 경유지 길찾기로 지점간의 거리를 구하게 되면 제한 반경 거리가 없기 때문에 모든 거리를 추천해 줄 수 있을 것이라 생각합니다.
다만 api를 최소한으로 부르기 위한 로직이 다소 복잡할 것으로 예상됩니다.