최대 거리 제약이 있는 시맨틱 장소를 경유하는 최단 경로 탐색 방법

Abstract

많은 사람들이 출발지에서 도착지까지 가는 최단 경로를 찾기 위해 내비게이션 시스템을 이용한다. 단순히 출발지에서 도착지까지의 최단 경로를 찾아주는 것에 대한 요구를 벗어나서, 도착지까지 가는 도중에 주유소 등의 경유지를 방문하는 최단 경로를 찾고자 하는 요구가 늘어나고 있다. 기존에 최단 경로를 구하는 여러 연구들이 진행된 반면, 이러한 경유 최단 경로 관련 연구는 도착지까지의 최단 경로 주변의 아이템들에 대한 검색만 대부분 이루어져 있다. 본 논문에서는 출발지에서 일정 이동 거리 범위 내에 있으면서 특정 속성을 만족하는 경유지를 지나는 여러 경로 결과들 중 최상의 k개 결과를 얻어내는 알고리즘을 제안한다. 그리고 제안한 알고리즘을 실세계 데이터에 대해 기초적인 알고리즘과 비교 실험하여 좋은 성능을 보임을 확인한다.