On the Modeling and Analysis of the Set Orienteering Problem under Uncertain Travel Costs

Abstract

: This paper studies the impact of edge-based uncertainty in the Set Orienteering Problem, where travel costs are modeled as random variables instead of deterministic values. In this problem, a single traveler departs from and returns to a depot and selects a sequence of sets so that the total travel cost remains within a predefined budget while maximizing the collected profit. Unlike classical SOP formulations that assume fixed edge costs, we incorporate stochastic travel times using Gamma and Normal distributions to better capture real-world variability arising in applications such as logistics and transportation. An integer linear programming formulation based on expected travel costs is proposed and solved using GAMS/CPLEX. To evaluate the effect of uncertainty, a scenario-based analysis is performed on benchmark instances derived from the Generalized Traveling Salesman Problem. The obtained solutions are evaluated under multiple stochastic scenarios to analyze their feasibility and variability in collected profit. Computational results indicate that uncertainty affects route structure and profit stability, even for small instances. In particular, solutions derived under deterministic assumptions may become infeasible when variability in travel costs is considered. These findings highlight the limitations of deterministic planning and motivate the need for incorporating uncertainty in clustered routing problems.