Doctoral thesis

Advanced metaheuristics for the probabilistic orienteering problem


102 p

Thèse de doctorat: Università della Svizzera italiana, 2020

English Stochastic Optimization Problems take uncertainty into account. For this reason they are in general more realistic than deterministic ones, meanwhile, more difficult to solve. The challenge is both on modelling and computation aspects: exact methods usually work only for small instances, besides, there are several problems with no closed-form expression or hard- to-compute objective functions. A state-of-the-art approach for several stochastic/probabilistic vehicle routing problems is to approximate their cost using Monte Carlo sampling. The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to be visited within a given time budget, so that a total revenue is maximized. Multiple stochastic variants of the problem have been studied. The Probabilistic Orienteering Problem is one of these variants, where customers will require a visit according to a certain given probability. The objective is to select a subset of customers to visit within a given time budget, so that an expected total reward is maximized while the expected travel time is minimised. The problem is NP-hard. In this work we propose different metaheuristics based on hybrid Monte Carlo sampling approximation to solve the problem. Detailed computational studies are presented, with the aim of studying the performance of the metaheuristics in terms of precision and speed, while positioning the new method within the existing literature. In this work, we also study the use of Machine Learning tools to help solve optimization problems. By shifting the problem of selecting the number of samples used by the Monte Carlo approximation to that of choosing a trade off between speed and precision, the best number of samples can be predicted by using Machine Learning models in a fast and efficient way. The Tourist Trip Design Problem (TTDP) is a variant of a route-planning problem for tourists interested in visiting multiple points of interest. A practical application of the POP to the probabilistic version of the TTDP is also discussed, and this provides inspiration for more possible applications.
  • English
Computer science and technology
License undefined
Persistent URL

Document views: 108 File downloads:
  • 2020INFO020.pdf: 37