Monte Carlo sampling for the tourist trip design problem

  • Xiaochen Chou IDSIA - Dalle Molle Institute for Artificial Intelligence (USI-SUPSI), Switzerland
  • Luca Maria Gambardella IDSIA - Dalle Molle Institute for Artificial Intelligence (USI-SUPSI), Switzerland
  • Roberto Montemanni Dept. of Engineering Sciences and Methods, University of Modena and Reggio Emilia, Italy
Keywords: The Tourist Trip Design Problem, Probabilistic Orienteering Problem, Monte Carlo Sampling, Combinatorial Optimization

Abstract

Introduction: The Tourist Trip Design Problem is a variant of a route-planning problem for tourists interested in multiple points of interest. Each point of interest has different availability, and a certain satisfaction score can be achieved when it is visited.

Objectives: The objective is to select a subset of points of interests to visit within a given time budget, in such a way that the satisfaction score of the tourist is maximized and the total travel time is minimized.

Methods: In our proposed model, the calculation of the availability of a POI is based on the waiting time and / or the weather forecast. However, research shows that most tourists prefer to travel within a crowded and limited area of very attractive POIs for safety reasons and because they feel more in control.

Results: In this work we demonstrate that the existing model of the Probabilistic Orienteering Problem fits a probabilistic variant of this problem and that Monte Carlo Sampling techniques can be used inside a heurist solver to efficiently provide solutions.

Conclusions: In this work we demonstrate the existing model of the Probabilistic Orienteering Problem fits the stochastic Tourist Trip Design Problem. We proposed a way to solve the problem by using Monte Carlo Sampling techniques inside a heuristic solver and discussed several possible improvements on the model. Further extension of the model will be developed for solving more practical problems.

References

Angelelli, E.; Archetti, C.; Filippi, C., & Vindigni, M. (2017). “The probabilistic orienteering problem”. Computers and Operations Research. 81, 269-281.

Campbell, A.M. & Thomas, W. (2008). “Probabilistic traveling salesman problem with deadlines”. Transportation Science. 42(1), 1-21.

Chou, X., Gambardella, L. M., & Montemanni, R. (2018). “Monte Carlo Sampling for the Probabilistic Orienteering Problem”. New Trends in Emerging Complex Real Life Problems. AIRO Springer, Serie s 1, 169-177.

Gunawana, A., Laua, H. C., & Vansteenwegenb, P. (2016). “Orienteering Problem: A Survey of Recent Variants, Solution Approaches and Applications”. European Journal of Operational Research. Volume 255, Issue 2, 315-332.

Kramer, R., Modsching, M., & Ten Hagen, K. (2006). “A city guide agent creating and adapting individual sightseeing tours based on field trial results”. International Journal of Computational Intelligence Research. 2(2), 191–206.

Papapanagiotou, V., Montemanni, R., & Gambardella, L. M. (2015). “Hybrid sampling-based evaluators for the orienteering problem with stochastic travel and service times”. Journal of Traffic and Logistics Engineering. 3(2), 108-114.

Weyland, D., Montemanni, R., & Gambardella, L. M. (2013). “Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel monte carlo sampling”. Computers and Operations Research. 40(7), 1661-1670.

Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009). “Metaheuristics for tourist trip planning”. In Lecture Notes in Economics and Mathematical Systems Springer, 15-31.

Published
2019-09-30
Section
Engineering, Technology, Management and Tourism