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.

Itinerary planning with category constraints using a probabilistic approach

Persia F.;
2017

Abstract

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.
978-3-319-64470-7
978-3-319-64471-4
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/166613
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact