Scheduling multiple trips for a group in spatial databases

Abstract

Planning user trips in an e ective and e cient manner has become an important topic in recent years. In this thesis, we introduce Group Trip Scheduling (GTS) queries, a novel query type in spatial databases. Family members normally have many outdoor tasks to perform within a short time for the proper management of home. For example, the members of a family may need to go to a bank to withdraw or deposit money, a pharmacy to buy medicine, or a supermarket to buy groceries. Similarly, organizers of an event may need to visit di erent types of points of interests (POIs) such as restaurants and shopping centers to perform many tasks. A GTS query distributes the tasks among group members in an optimized manner. Given source and destination locations of n group members, a GTS query schedules n individual trips such that each POI type is included in a scheduled trip and the aggregate trip overhead distance for visiting required POI types is minimized. The aggregate trip overhead distance can be either the summation or the maximum of the trip overhead distances of group members. Each trip starts at a member's source location, goes through any number of POI types, and ends at the member's destination location. The trip distance of a group member is measured as the distance between her source to destination via the POIs that the group member visits. The trip overhead distance of a group member is measured by deducting the distance between the source and destination locations of a group member from the trip distance. We develop an e cient approach to process GTS queries and variants for both Euclidean space and road networks. The number of possible combinations of trips among group members increases with the increase of the number of POIs that in turn increases the query processing overhead. We exploit geometric properties to re ne the POI search space and prune POIs to reduce the number of possible combinations of trips among group members. We propose a dynamic programming technique to eliminate the trip combinations that cannot be part of the query answer. We perform experiments using real and synthetic datasets and show that our approach outperforms a straightforward approach with a large margin.