Single Group Collective Trip Planning Query Processing Using G-tree Index Structures on Road Networks

Junkyu Lee, Seog Park

http://doi.org/10.5626/JOK.2020.47.5.513

In this paper, we discuss Single Group Collective Trip Planning (SGCTP) queries that minimize the overall travel cost in location-based ride sharing services. The SGCTP queries identify a meeting point that minimizes the overall cost of such a trip when a group of users are gathered at a particular point and travel to the destination using one vehicle. Although many researches on collective trip planning queries have been conducted, there is a problem that the query performance is effective only in a specific situation. So, we introduce a baseline method of the SGCTP queries and then, propose an effective pruning technique with a G-tree index structure. Additionally, we analyze that the limitations of the previous studies, and experimental results show that the proposed pruning technique can obtain the optimal query result without being affected by the limitations of the previous studies.