Monte Carlo sampling for the tourist trip design problem

• Main Authors: Xiaochen Chou (Author), Luca Maria Gambardella (Author), Roberto Montemanni (Author)
• Format: Book
• Published: Instituto Politécnico de Viseu, 2019-09-01T00:00:00Z.
• Subjects: article
• Online Access: Connect to this object online.
• Notes: 10.29352/mill0210.09.00259; 0873-3015; 1647-662X
• Keywords: The Tourist Trip Design Problem; Probabilistic Orienteering Problem; Monte Carlo Sampling; Combinatorial Optimization; Special aspects of education; LC8-6691; Public aspects of medicine; RA1-1270
• Source: Millenium, Vol 2, Iss 10 (2019)

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.