Resource Capacitated Collective Travel Planning in Spatial Databases

Abstract

The widespread use of GPS smart devices has allowed users to collect location information in real-time, leading to the emergence of ride-sharing services based on users' locations. Ride-sharing services have become effective services that reduce the cost of individual use of vehicles and also reduce the amount of gas that vehicles emit. Many studies have been conducted on ride-sharing services, which have focused on calculating the optimal cost of assigning users to vehicles in consideration of various cases of vehicle-sharing services (e.g., vehicles move to pick passengers, or passengers move to the vehicle's location). However, since the focus was only on improving the performance of queries, it is not easy to apply the proposed queries directly to the actual services. In real-world services, resources are generally finite. So, it happens that service providers are unable to follow that derived from optimal results. This paper focuses on considering limited resources in collective travel planning, a kind of group query available in ride-sharing services. We call this novel query as Resource Capacitated Collective Travel Planning (RCCTP). Unfortunately, the RCCTP query is NP-hard. So, we propose three-level pruning rules to answer the correct result with theoretical proofs and propose a new approximation method that can answer the RCCTP query efficiently. We show that the experimental evaluation demonstrates those improvements in query performance compared with the existing method.

Keywords

• Aggregation query
• assignment problem
• network flow
• query processing
• spatial databases
• spatial group query