Operations Research 2025
Abstract Submission

2393. Online Robust Capacitated Team Orienteering Problem

Invited abstract in session WC-10: Tour Planning Problems, stream Mobility, Transportation, and Traffic.

Wednesday, 13:30-15:00
Room: H16

Authors (first author is the speaker)

1. Siamak Khayyati
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

We introduce an online robust optimization extension of the Capacitated Team Orienteering Problem, called ORCTOP. We hedge against uncertainties in four key parameters: prizes, demand weights, service times, and travel times. We characterize uncertainty as a budget uncertainty set and analyze the problem in an online setting where uncertain parameters are revealed sequentially to the decision maker. We investigate ORCTOP through the lens of competitive ratio (CR) and, to reduce the inherent over-conservatism of this measure, adopt a novel setup-based analysis that evaluates algorithmic performance relative to each specific problem instance. We derive a theoretical lower bound on the setup-based CR of the optimal online algorithm for ORCTOP, quantifying the maximum potential advantage of having complete prior information in the worst case. We propose two formulation-based algorithms—one static and one adaptive—with provable setup-based CR guarantees, each matching our proposed lower bound. We extend our theoretical analysis by evaluating average case performance and proving that the adaptive algorithm outperforms the static one in terms of average-case CR. To enable real-time deployment, we develop robust evolutionary heuristics to efficiently approximate the solutions of both of our proposed formulation-based algorithms in real time. We test our proposed algorithms using a dataset derived from real-world urban networks in cities affected by the 2023 Türkiye earthquake. We confirm the effectiveness of our proposed heuristics by comparing them with our mathematical formulations through extensive computational experiments. Our empirical results demonstrate that the adaptive algorithm consistently outperforms the static algorithm in terms of average-case CR.

Keywords

Status: accepted

Back to the list of papers