Many people use GPS navigation systems to find directions when driving a car. Beyond the needs to find the fastest possible routes, there are growing needs to find the shortest path via waypoint such as gas stations. While there have been a number of studies to find the answer to the similar problem, most were concentrated on searching items near a route. In this paper, we propose an algorithm to compute top-k shortest paths among possible routes via waypoint which is located on the route under the maximum distance limit from a starting point. To guarantee that proposed algorithm achieves satisfactory performance, an experiment has been conducted on real dataset.
많은 사람들이 출발지에서 도착지까지 가는 최단 경로를 찾기 위해 내비게이션 시스템을 이용한다. 단순히 출발지에서 도착지까지의 최단 경로를 찾아주는 것에 대한 요구를 벗어나서, 도착지까지 가는 도중에 주유소 등의 경유지를 방문하는 최단 경로를 찾고자 하는 요구가 늘어나고 있다. 기존에 최단 경로를 구하는 여러 연구들이 진행된 반면, 이러한 경유 최단 경로 관련 연구는 도착지까지의 최단 경로 주변의 아이템들에 대한 검색만 대부분 이루어져 있다. 본 논문에서는 출발지에서 일정 이동 거리 범위 내에 있으면서 특정 속성을 만족하는 경유지를 지나는 여러 경로 결과들 중 최상의 k개 결과를 얻어내는 알고리즘을 제안한다. 그리고 제안한 알고리즘을 실세계 데이터에 대해 기초적인 알고리즘과 비교 실험하여 좋은 성능을 보임을 확인한다.
