Optimal Route Search with the Coverage of Users' Preferences

Yifeng Zeng, Xuefeng Chen, Xin Cao, Shengchao Qin, Marc Cavazza, Yanping XiangIJCAI 2015

Introduction

Traditional route planning typically focuses on finding the shortest path between two points. However, modern users often seek routes that satisfy specific interests, such as "shopping" or "dining," along the way. Existing systems often treat keyword satisfaction as a binary attribute—either a location matches a keyword or it doesn't. This paper introduces the Optimal Route Search for Keyword Coverage (ORS-KC) problem, which addresses two critical gaps:

  1. Degrees of Satisfaction: Locations are rated on a scale (0 to 1) reflecting how well they match a keyword (e.g., based on popularity or reviews).
  2. Diminishing Returns: The model uses a submodular function to account for redundancy, recognizing that visiting multiple similar locations (e.g., three malls) yields decreasing marginal utility.
Graph model of the ORS-KC problem showing nodes with keyword satisfaction weights.

The ORS-KC problem is NP-hard, requiring a balance between maximizing total satisfaction and adhering to a distance or time budget. Unlike greedy approaches, the algorithm must consider the entire path's coverage to optimize the final result.

Methodology

The authors propose an efficient solution using a specialized A* Search Algorithm. The core innovation is a novel admissible heuristic function ($h^n$) designed to provide an optimistic estimate of the remaining potential satisfaction. To compute this heuristic, the authors:

  • Reformulate as Budgeted Maximum Coverage (BMC): The remaining trip is modeled as an optimization problem aimed at covering the most weighted keywords within the remaining budget.
  • Greedy Approximation: Since BMC is also NP-hard, a greedy approximation is used to calculate a tight upper bound on satisfaction.
  • Pruning Optimization: Partial routes are discarded if they cannot reach the destination within the budget or cannot exceed the current best-found route's score.

Additionally, a Weighted A (WA) variant is introduced to trade a small amount of accuracy for significantly faster computation, improving scalability for larger search spaces.

Experimental Setup

The approach was evaluated using two real-world datasets from location-based social networks:

  • Singapore (SG): 189,306 check-ins at 5,412 locations from Foursquare.
  • Austin (AS): 201,525 check-ins at 6,176 locations from Gowalla.

Keyword satisfaction weights were derived from check-in density, serving as a proxy for location popularity. Edge costs were defined by Euclidean distances between consecutive check-ins.

Results and Discussion

The proposed A algorithm demonstrated significant performance gains, running 2 to 3 times faster* than brute-force methods with pruning. Key findings include:

  • Scalability: While standard A struggles as budgets increase, the WA variant maintains efficiency by managing the search space explosion.
  • Precision-Complexity Trade-off: Setting the weighting parameter $\omega$ to 0.2 reduced computation time drastically while maintaining approximately 95% of the optimal route quality.
  • Qualitative Utility: In real-world scenarios, the algorithm successfully adapted routes based on user weights. For instance, prioritizing "shopping" led to routes through major malls, while prioritizing "nature" directed users through parks within the same budget.
Qualitative comparison of Route 1 and Route 2 generated based on different user preferences.

Conclusion

The ORS-KC framework provides a robust model for personalized route planning by incorporating submodular satisfaction and keyword weights. While the A* variant is highly effective, future work may explore more advanced approximation techniques for massive, city-scale road networks and incorporate dynamic constraints like time-of-day availability.

Summary updated

BibTeX
@inproceedings{zeng2015optimal,
  author = {Yifeng Zeng and Xuefeng Chen and Xin Cao and Shengchao Qin and Marc Cavazza and Yanping Xiang},
  title = {{Optimal Route Search with the Coverage of Users' Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure