Efficient trip scheduling algorithms for groups

Abstract Given the source and destination locations of n group members and a set of required point of interest (POI) types such as restaurants and shopping centers, a Group Trip Scheduling (GTS) query schedules n individual trips such that each POI type is included in exactly one trip and an aggregate trip overhead distance for visiting the required POI types is minimized. Each trip starts at a member’s source location, goes through some POIs, and ends at the member’s destination location. The trip distance of a group member is the distance from her source to destination via the POIs that the group member visits, and the trip overhead distance of the group member is measured by subtracting the distance between her source and destination locations (without visiting any POI type) from her trip distance. The aggregate trip overhead distance is either the summation or the maximum of the trip overhead distances of the group members for visiting the POIs. A GTS query enables a group to schedule independent trips for its members in order to perform a set of tasks with the minimum travel cost. For example, family members normally have many outdoor tasks to perform within a short time for the proper management of home. The members 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 different POI types to perform many tasks. These scenarios motivate us to introduce a GTS query, a novel query type in spatial databases. We develop an efficient approach to process GTS queries and variants for the Euclidean space and road networks. By exploiting geometric properties, we refine the POI search space and prune POIs, which in turn reduce the query processing overhead significantly. In addition, we propose a dynamic programming technique to eliminate the trip combinations that cannot be part of the optimal query answer. We show that processing a GTS query is NP-hard and propose an approximation algorithm to further reduce the query processing overhead. We perform extensive experiments using real and synthetic datasets and show that our approach outperforms a straightforward approach with a large margin.