Online Robust Capacitated Team Orienteering Problem

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 formulationbased algorithms—one static and one adaptive—with provable setupbased 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. Weconfirm 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.