EURO 2025 Leeds
Abstract Submission

834. An Online Optimization Framework for the Robust Capacitated Team Orienteering Problem under Uncertainty

Invited abstract in session WC-58: Team Orienteering Problems, stream Vehicle Routing and Logistics.

Wednesday, 12:30-14:00
Room: Liberty 1.13

Authors (first author is the speaker)

1. Siamak Khayyati
HEC Liege, University of Liege
2. Masoud Shahmanzari
Brunel Business School, Brunel University
3. Jyotirmoy Dalal
OMDS, University of Sheffield
4. Davood Shiri
Operations Management and Decision Sciences, The University of Sheffield

Abstract

The increasing frequency and severity of natural disasters create a need for fast and robust methods for managing disaster response under uncertainty. Robust optimization incorporates the possible ranges that each uncertain parameter has and plans for the worst-case scenario given some limits on how bad the worst-case scenario can be.
In this context, we propose an extension of the Capacitated Team Orienteering Problem (CTOP), namely the Robust CTOP (RCTOP) by considering the uncertainties related to node prizes, node weights, node service time and arc travel times. Solving RCTOP using commercial solvers can be time-consuming. We devise a heuristic method for solving RCTOP based on a genetic algorithm, simulating the interconnected behaviour of the uncertain parameters and the chosen solution as a sequential game. As time passes during the operation, the uncertainties for the visited nodes and arcs are resolved and as a result, better plans that were not feasible at the start of the operation might become feasible. We give an online algorithm (ORCTOP) that can utilize these opportunities to improve the solution in real time.
We assess the performance of our method by applying it to a dataset derived from real-world urban networks in disaster-affected cities from the Türkiye 2023 earthquake. Using this dataset, we show the effectiveness and speed of our heuristic algorithm and the ability of the online variant to correct the initial over-conservatism of the RCTOP.

Keywords

Status: accepted

Back to the list of papers