RE - Série 2, n.º 10: (2019)
Permanent URI for this collection
Browse
Browsing RE - Série 2, n.º 10: (2019) by Subject "Combinatorial Optimization"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- Monte Carlo sampling for the tourist trip design problemPublication . Chou, Xiaochen; Gambardella, Luca Maria; Montemanni, RobertoIntroduction: 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.