Itinerary planning with category constraints using a probabilistic approach

We propose a probabilistic approach for finding approximate solutions to rooted orienteering problems with category constraints. The basic idea is to select nodes from the input graph according to a probability distribution considering properties such as the reward of a node, the attractiveness of its neighborhood, its visiting time, and its proximity to the direct route from source to destination. In this way, we reduce the size of the input considerably, resulting in a much faster execution time. Surprisingly, the quality of the generated solutions does not suffer significantly compared to the optimal ones. We illustrate the effectiveness of our approach with an experimental evaluation also including real-world data sets.