한정된 자원을 고려한 집단 여행 계획 질의 처리 기법
Resource Capacitated Collective Travel Planning Query
- 주제(키워드) 네트워크 유량 , 질의 처리 , 공간 데이터베이스 , 공간 그룹 질의 , 여행 계획 질의 , network flow , query processing , spatial databases , spatial group query , travel planning query
- 발행기관 서강대학교 일반대학원
- 지도교수 박석
- 발행년도 2020
- 학위수여년월 2020. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- UCI I804:11029-000000065313
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
도시 간 운송 문제인 집단 여행 계획 질의는 질의 사용자들을 모아서 목적지까지 이동하는 전체 비용을 최소화하는 만남 장소들의 집합을 제공한다. 서비스 제공자는 사용자들에게 집단 여행 계획 질의를 이용하여 최적의 승차 위치를 제공할 수 있다. 그러나 서비스 제공자의 자원이 한정되어 있다면 집단 여행 계획 질의를 가지고 최적의 승차 위치를 제공할 수 없다. 본 논문은 서비스 제공자가 가지고 있는 차량의 용량, 차량의 수, 사용자와 차량 사이의 최대 허용 거리라는 세 가지 유형으로 구성된 자원 한계를 고려하여 최적의 여행 경로를 제공하는 한정된 자원을 고려한 집단 여행 계획 질의를 제안한다. 한정된 자원을 고려한 집단 여행 계획 질의는 질의 결과의 정확성을 보장하는 세 단계의 가지치기 기법을 제안한다. 또한 지역 탐색 휴리스틱 방법을 적용하고 지역 변경 연산의 성능 개선을 위한 가지치기 기법도 제안한다. 추가적으로, 지역 탐색 방법보다 효과적인 질의 수행 시간을 갖는 반복 탐욕 기법이라는 새로운 방법을 제안한다. 마지막으로 실험을 통해 본 연구에서 제안하는 세 가지 가지치기 방법이 기본적인 기법보다 성능을 개선할 수 있음을 보이고, 제안하는 근사 알고리즘이 지역 탐색 기법과 비슷한 정확도를 보이지만 개선된 질의 수행 시간을 갖는다는 것을 보인다.
more초록/요약
Collective Travel Planning (CTP), as an intercity transportation problem provides a subset of meeting points which minimize the total cost of distances to travel to a destination by gathering query users. Service agents can provide an optimal set of vehicle locations using the CTP query for customers. However, it is not possible to provide an optimal result in the CTP if there are resource capacities of service agents. In this thesis, we present a novel query called Resource Capacitated Collective Travel Planning (RCCTP) that provides the optimal travel route considering resource capacities of service agents which consist of three types such as vehicle capacity, maximum number of vehicles, and maximum distance bound between users and meeting points in the RCCTP query. We propose three level pruning rules that guarantee the query correctness. We also apply the local search heuristic and develop pruning rules for local change operations. Furthermore, we propose Repeated Greedy Method (RGM) which has better query running time than the local search. Finally, in experiments, we show that the performance improvement of the proposed three level pruning rules compared with the baseline method, and the proposed approximation algorithm has similar accuracy to the local search, but has improved query running time.
more