TOP-ST-MIN: dealing with uncertainties

We introduce two different types of uncertainties arising in a new variant of Team Orienteering Problem (TOP). The TOP [1] is a combinatorial optimization problem that can be described through a complete and directed graph. Each node has a score and each arc has a travel time. The aim of the problem is to find a set of routes that maximizes the overall score collected without exceeding a specific budget of time for each of them.
From the generalization of two real application problems, that is the daily swab test collection problem [2] and the ambulance routing problem [3], it emerges a new variant of the TOP that combines all the features introduced for these problems.
In this talk, we briefly present the Team Orienteering Problem with Service Times and Mandatory and Incompatible Nodes (TOP-ST-MIN) to highlight these new features, that is the service times, the mandatory nodes and the incompatibilities. Afterwards, we describe the uncertainty factors that may characterise the problem: the stochasticity of the travelling times and the dynamicity of the nodes (the set of nodes changes over time and some node could become mandatory).
Finally, we conclude the presentation focusing our attention on the methods we are using to deal with the uncertainties: we formulated a two-stage with recourse model (solved with a Branch & Cut) to deal with the stochastic travel times and a Branch & Regret algorithm [4] to handle the dynamicity of the nodes. Concluding remarks close the talk.

[1] I-Ming Chao and Bruce L. Golden and Edward A. Wasil. The team orienteering problem. European Journal of Operational Research, 88: 464-474, 1996.
[2] R. Aringhieri, S. Bigharaz, A. Druetto, D. Duma, A. Grosso, and A. Guastalla. The daily swab test collection problem. Annals of Operations Research, 2022.
[3] R. Aringhieri, S. Bigharaz, D. Duma, and A. Guastalla. Fairness in ambulance routing for post disaster management. Central European Journal of Operations Research, 30:189-211, 2021.
[4] Jean-François Côté, Thiago Alves de Queiroz, Francesco Gallesi, Manuel Iori. A branch-and-regret algorithm for the same-day delivery problem. Transportation Research Part E: Logistics and Transportation Review, 2023.