적응적 우선순위 기반의 부분적 방문순서를 따르는 경로 검색 기법
An Adaptive Priority-based Partial Sequenced Route Query Processing Method
- 주제(키워드) 도움말 방문순서를 따르는 경로 검색 , 위치기반서비스 질의 , 도로 네트워크 , 근사 최단경로 , LBS query , sequenced route query , road network , approximate shortest route
- 발행기관 서강대학교 일반대학원
- 지도교수 정성원
- 발행년도 2014
- 학위수여년월 2014. 8
- 학위명 석사
- 학과 및 전공 도움말 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000054056
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약 도움말
최근 대중화 된 스마트폰을 위시한 스마트 모바일 기기들은 휴대가 가능하고 무선 통신을 제공함으로써 GPS 및 네비게이션 등과 같이 위치기반 서비스에 대한 수요를 이끌고 있다. 전통적인 위치기반 서비스는 출발지와 목적지 간의 최단 경로를 찾는 경로 문제가 대표적이다. 이 문제는 출발지와 목적지 사이에 반드시 방문해야 하는 POI(Point of Interest)도 처리 가능하도록 발전되었고, 이후 POI들 중 일부에만 방문순서가 주어진 경우를 의미하는 부분적인 방문순서를 따르는 경로 문제로 발전되었다. 즉, 부분적인 방문순서를 따르는 경로 문제란 출발지에서부터 주어진 유형별 POI들 중 각 유형별로 하나씩 주어진 여러 방문순서들에 따라 방문한 후 목적지에 도달하는 경로를 찾는 문제이며, 이 경로들 중 근사 최단 경로(Approximate Shortest Path)를 찾는 것이 본 논문의 목표이다. 예를 들어, 사용자는 회사에서 퇴근 후 은행을 방문하여 현금을 인출, 레스토랑에서 저녁을 먹고 집으로 오길 원한다. 이때 출발지는 회사가 되고, 목적지는 집이 되며, POI는 은행과 레스토랑이 된다. 레스토랑 전에 은행을 들리지 않으면 저녁을 사먹을 돈을 인출하지 못하기 때문에 방문순서는 반드시 지켜져야 한다. 기존의 2가지 부분적으로 주어진 방문순서를 따르는 경로 검색 기법들은 출발지를 포함한 이전 방문 POI와 이후 방문해야 할 유형의 POI들과의 근접성만을 고려하거나, 후보군 선정시 출발지와 후보지 간 유클리디언 거리와 후보지와 목적지간의 유클리디언 거리의 합만을 고려하기에 방문순서 및 네트워크 거리가 고려되지 않고, 또한 각 POI들에 대한 유클리디언 거리계산이 필요한 단점을 가지고 있다. 이를 해결하기 위해 본 논문에서는 네트워크 기반 탐색을 이용하여 최단 경로에 더 근접한 POI 탐색이 가능하고, 방문한 유형별 POI가 많은 경로에 적응적 우선순위를 주어 더 짧은 시간 안에 향상된 근사 최단 경로를 구하는 기법을 제안한다.
more초록/요약 도움말
Smart mobile devices including the smartphone, which recently become popular, are leading the demand in the use of Location-Based Services(LBS), such as global-positioning systems(GPS) or navigation as they are portable and offer wireless communication. Route query finding the shortest path between a source point and a destination point is one of the many path-finding problems in traditional LBS systems. This problem is developed visiting one point for every type of Point of interest(POI) between the source and destination. This problem developed into partially sequenced route query according to partial order of visits, which means some of specified POIs should be visited in order. In other words, partially sequenced route query means finding a route from starting location to a specified destination passing through one POI for each POI type according to the order of visit and then finding the approximate shortest path among these paths is the goal of this paper. For example, when a user goes off from work, he will go to his bank to withdraw some money, then go to a restaurant to eat dinner. In this situation, the starting point is his workplace and the final destination is his house. POI types include the bank and the restaurant. The order of visiting should be kept. In our case, the user will not be able to pay for his meal if he goes to the restaurant without withdrawing money first from his bank. The two existing partial sequenced route query algorithms have weaknesses. One of them only considered the proximity between previously visited POI including starting location and POI to visit in the future. The other algorithm doesn't consider the order of visit and network distance with choosing candidates. The latter only considered sum of Eucldean distance between starting location and a POI and Euclidean distance between the POI and destination. The algorithm needs to compute the distance for each POIs. To solve this problem, this paper provides an algorithm which is possible to find POI nearer to shortest path and improved approximate shortest route by assigning adaptive priority to route which visited more POIs.
more