Abstract
Personalized route planning applications are tools to help tourists to find itineraries of their personal liking. Let us consider two extremes: in one, the tourist requires to give a score to all, possibly hundreds, points of interests (POIs); in the other, there are fixed itineraries that leave no space for personalization. As a compromise between these two extremes, we add category information to the POIs, allowing the user to influence the scores by providing information on just few categories. To add diversity to itineraries, we also give the user the possibility to set up a limit to how many POIs of a category to visit. We formally define the problem, called Orienteering with Maximum Point Categories. The problem is NP-hard and it is difficult to adapt existing techniques because they are based on the divide-and-conquer approach; but joining subpaths may break category constraints. As baseline on quality and speed we develop an optimal and a greedy algorithm; then we implement three heuristics faster than the optimal algorithm and more scoring than greedy. The first is a static approach that uses clusters to reduce the size of the problem and limit the search space. The second uses graph pruning to reduce the graph instance before executing. The third is a dynamic approach, an anytime algorithm that explores the itineraries search space in best-first order and it prunes the search space using branch-and-bound techiques. To support dynamic algorithms and answers reachability queries we also tackle the isochrone computation problem using materialization. We evaluate our algorithms theoretically and experimentally using both artificial and real-world data sets. The results are nearby the optimal and the approaches result quite scalable also for larger data sets.