Monte Carlo sampling for the tourist trip design problem

Authors

  • 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

DOI:

https://doi.org/10.29352/mill0210.09.00259

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.

Downloads

Download data is not yet available.

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.

Downloads

Published

2019-09-30

How to Cite

Chou, X., Gambardella, L. M., & Montemanni, R. (2019). Monte Carlo sampling for the tourist trip design problem. Millenium - Journal of Education, Technologies, and Health, 2(10), 83–90. https://doi.org/10.29352/mill0210.09.00259

Issue

No. 10 (2019): Série 2 Nº10

Section

Engineering, Technology, Management and Tourism

License

Authors who submit proposals for this journal agree to the following terms:

a) Articles are published under the Licença Creative Commons (CC BY 4.0), in full open-access, without any cost or fees of any kind to the author or the reader;

b) The authors retain copyright and grant the journal right of first publication, allowing the free sharing of work, provided it is correctly attributed the authorship and initial publication in this journal;


c) The authors are permitted to take on additional contracts separately for non-exclusive distribution of the version of the work published in this journal (eg, post it to an institutional repository or as a book), with an acknowledgment of its initial publication in this journal;

d) Authors are permitted and encouraged to publish and distribute their work online (eg, in institutional repositories or on their website) as it can lead to productive exchanges, as well as increase the impact and citation of published work

Documents required for submission

Article template (Editable format)

Article sheet