Trip Recommendation Meets Real-World Constraints: POI Availability, Diversity, and Traveling Time Uncertainty

As location-based social network (LBSN) services become increasingly popular, trip recommendation that recommends a sequence of points of interest (POIs) to visit for a user emerges as one of many important applications of LBSNs. Personalized trip recommendation tailors to users' specific tastes by learning from past check-in behaviors of users and their peers. Finding the optimal trip that maximizes user's experiences for a given time budget constraint is an NP-hard problem and previous solutions do not consider three practical and important constraints. One constraint is POI availability, where a POI may be only available during a certain time window. Another constraint is uncertain traveling time, where the traveling time between two POIs is uncertain. In addition, the diversity of the POIs included in the trip plays an important role in user's final adoptions. This work presents efficient solutions to personalized trip recommendation by incorporating these constraints and leveraging them to prune the search space. We evaluated the efficiency and effectiveness of our solutions on real-life LBSN datasets.