Advances in Spatial and Temporal Databases

The increasing popularity of location-based applications creates new opportunities for users to travel together. In this paper, we study a novel spatio-social optimization problem, i.e., Optimal Group Route, for multi-user itinerary planning. With our problem formulation, users can individually specify sources and destinations, preferences on the Point-of-interest (POI) categories, as well as the distance constraints. The goal is to find a itinerary that can be traversed by all the users while maximizing the group’s preference of POI categories in the itinerary. Our work advances existing group trip planning studies by maximizing the group’s social experience. To this end, individual preferences of POI categories are aggregated by considering the agreement and disagreement among group members. Furthermore, planning a multi-user itinerary on large real-world networks is computationally challenging. We propose one approximate solution with bounded approximation ratio and one exact solution which computes the optimal itinerary by exploring a limited number of paths in the road network. In addition, an effective compression algorithm is developed to reduce the size of the network, providing a significant acceleration in our exact solution. We conduct extensive empirical evaluations on the road network and POI datasets of Los Angeles and our results confirm the effectiveness and efficiency of