본 논문에서는 도로 네트워크 환경에서 부분적으로 주어진 방문순서에 따라 출발지로부터 각 타입의 포인트 데이터 한 개씩을 방문하여 도착지에 도달하는 근접최단경로를 찾기 위하여, 방문할 후보 포인트 데이터를 선정하는 효과적인 비용함수와 후보 포인트 데이터를 방문하는 근접최단경로를 찾는 경로 검색 기법 PRGA(Partial sequenced Route computation Greedy Algorithm)와 GCPRA(Globally Considered Partial sequenced Route computation Algorithm)를 제안하였다. PRGA은 Greedy 알고리즘을 사용하여 근접최단경로를 구하는 방법이며, GCPRA은 후보 포인트로 구성된 가능한 모든 경로를 고려하여 근접최단경로 구하는 기법이다. 제안한 두 개의 근접최단경로 검색기법의 성능분석 결과 기존의 기법보다 더 최단경로에 근접한 경로를 생성하는 것으로 나타났다.
This paper addresses the problem of finding the approximate shortest route that visits one candidate point for each POI (Point Of Interest) type from the start to the destination by using a partially given visiting sequence of POI types. We first propose an effective cost function that selects candidate points for each POI types. We then propose two approximate shortest route computation algorithms, PRGA (Partial sequenced Route computation Greedy Algorithm) and GCPRA (Globally Considered Partial sequenced Route computation Algorithm), which pass through the selected candidate points in road networks according to a partially given visiting sequence of POI types. PRGA computes an approximate shortest route based on a greedy algorithm, whereas GCPRA computes an approximate shortest route by considering all possible routes of candidate points. The performance analysis of the two proposed algorithms shows that they generate the better approximate shortest routes than the existing methods.
