Advanced Metaheuristics for the Probabilistic Orienteering Problems

Staff - Faculty of Informatics

Date: / -


You are cordially invited to attend the PhD Dissertation Defense of Xiaochen Chou on Friday December 11th, 2020 at 10:30 on MS Teams (code: lueir67).

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.

Dissertation Committee:

  • Prof. Luca Maria Gambardella, Università della Svizzera italiana, Switzerland (Research Advisor)
  • Prof. Roberto Montemanni, Università degli Studi di Modena e Reggio Emilia, Italy (Research Co-Advisor)
  • Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Olaf Schenk, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Philipp Baumann, University of Bern, Switzerland (External Member)
  • Prof. Carlo Filippi, University of Brescia, Italy (External Member)