View article

A group of friends located at their working places may want to plan a trip to visit a shopping center, have dinner at a restaurant, watch a movie at a theater, and then finally return to their homes with the minimum total trip distance. For a group of spatially dispersed users a group trip planning (GTP) query returns points of interests (POIs) of different types such as a shopping center, a restaurant and a movie theater that minimize the aggregate trip distance for the group. The aggregate trip distance could be the sum or maximum of the trip distances of all users in the group, where the users travel from their source locations via the jointly visited POIs to their individual destinations. In this paper, we develop both optimal and approximation algorithms for GTP queries for both Euclidean space and road networks. Processing GTP queries in real time is a computational challenge as trips involve POIs of multiple types and …