Konavi는 어떻게 최적 경로를 찾을까?

여행 경로 짜기, 왜 어려울까?

서울에서 여러 관광지를 돌아보는 순서를 짤 때, 대부분은 지도를 펼쳐놓고 가까운 곳끼리 묶어서 동선을 만듭니다. 직선 거리만 보면 이 방법이 꽤 합리적으로 보입니다.

하지만 실제로 대중교통을 타면 이야기가 달라집니다. 지도상으로는 바로 옆인데 지하철 노선이 연결되지 않아 두세 번 환승해야 하는 곳이 있고, 반대로 멀어 보여도 같은 노선 위에 있어서 한 번에 갈 수 있는 곳도 있습니다. 서울의 대중교통 네트워크는 복잡하기 때문에, 직선 거리와 실제 이동 시간의 차이가 예상보다 큽니다.

게다가 서울 대중교통은 비대칭이기도 합니다. A에서 B로 가는 시간과 B에서 A로 가는 시간이 다릅니다. 지하철 환승 구조나 버스 노선 방향에 따라 한쪽이 훨씬 오래 걸리는 경우가 많아서, 방문 순서를 뒤집기만 해도 총 이동 시간이 크게 달라질 수 있습니다.

결국 지도만 보고는 최적의 순서를 판단하기 어렵습니다. Konavi는 이 문제를 실제 대중교통 소요시간 데이터와 수학적 최적화 알고리즘으로 해결합니다.

1단계: 실제 대중교통 시간 수집

Konavi는 사진이 등록된 모든 관광지 사이의 모든 방향 조합에 대해 대중교통 소요시간을 미리 계산해 데이터베이스에 저장해 둡니다. 관광지는 계속 추가되며, 새로운 장소가 등록될 때마다 조합도 함께 갱신됩니다.

이 데이터는 한국 대중교통 전문 API인 ODsay에서 가져옵니다. 구글 지도는 한국 대중교통 경로를 정확하게 계산하지 못하기 때문에, Konavi는 한국 교통 데이터에 특화된 ODsay를 사용합니다.

사전에 캐시된 데이터 덕분에 경로를 찾을 때 API를 대량으로 호출할 필요가 없어 빠르게 결과를 제공할 수 있습니다. 실시간으로 계산이 필요한 것은 출발지에서 각 관광지까지의 시간뿐입니다. 이때도 출발지 → 관광지 방향만 계산합니다. Konavi의 경로는 출발지에서 시작해서 마지막 관광지에서 끝나는 열린 경로이므로, 관광지에서 출발지로 돌아오는 시간은 필요하지 않기 때문입니다.

2단계: 최적 순서 계산 (Held-Karp 알고리즘)

모든 장소 간 이동 시간이 준비되면, Konavi는 Held-Karp 알고리즘을 사용해 최적의 방문 순서를 찾습니다.

이 알고리즘은 컴퓨터 과학에서 유명한 "외판원 문제(Travelling Salesman Problem)"를 푸는 정확한 방법 중 하나입니다. 핵심 아이디어는 다음과 같습니다:

• 가능한 모든 방문 조합을 체계적으로 탐색합니다
• 이미 계산한 부분 경로의 결과를 **기억(메모이제이션)**해서 중복 계산을 피합니다
• 결과적으로, 모든 순서를 하나씩 대입하는 것보다 훨씬 빠르게 정확한 최적해를 구합니다

Konavi의 경로는 출발지에서 시작해서 마지막 관광지에서 끝나는 열린 경로입니다. 출발지로 돌아오는 시간은 포함하지 않으므로, 마지막 장소 근처에서 저녁을 먹거나 숙소로 이동하는 등 자유롭게 일정을 마무리할 수 있습니다.

3단계: 이상치 감지 (먼 곳 알림)

최적 경로를 계산한 후에도, 선택한 장소 중 하나가 나머지와 동떨어진 위치에 있어서 전체 이동 시간을 크게 늘리는 경우가 있습니다.

Konavi는 이런 장소를 자동으로 감지합니다:

• 각 장소를 하나씩 빼 보고, 그 장소 없이 경로를 다시 계산합니다
• 특정 장소를 뺐을 때 총 이동 시간이 30% 이상 줄어들고, 절약되는 시간이 40분 이상이면 해당 장소를 이상치로 판단합니다

이상치가 발견되면, Konavi는 해당 장소를 빼는 것을 제안합니다. 물론 그대로 포함해서 갈 수도 있고, 대신 근처의 다른 관광지로 교체하는 것도 가능합니다.

4단계: 근처 추천 관광지

이상치를 제거하거나 장소를 바꾸고 싶을 때, Konavi는 현재 경로에 가장 적은 추가 시간으로 삽입할 수 있는 관광지를 추천합니다.

단순히 직선 거리가 가까운 곳이 아니라, 실제 경로의 어느 구간 사이에 넣었을 때 우회가 가장 적은 곳을 찾습니다. 예를 들어 A → B 구간 사이에 C를 넣으면 A → C → B가 되는데, 이때 추가되는 시간(A→C + C→B - A→B)이 가장 작은 장소를 상위에 보여줍니다.

정리

• 대중교통 데이터 -- 사진 등록 관광지 간 모든 방향 조합의 실제 소요시간을 미리 캐시해 정확하고 빠르게 계산합니다.
• Held-Karp 최적화 -- 수학적으로 최단 방문 순서를 계산해 보장된 최적해를 제공합니다.
• 이상치 감지 -- 전체 이동 시간을 크게 늘리는 장소를 자동으로 식별해 알려줍니다.
• 근처 추천 -- 최소 우회로 삽입할 수 있는 대안 장소를 제안합니다.