Sim-approaches for the stochastic clustered team orienteering problem
TL;DR
A Simheuristic method integrating Monte Carlo simulations within an Adaptive Large Neighborhood Search (SimALNS) to address the Stochastic Clustered Team Orienteering Problem (SCTOP), a variant of the recently defined CluTOP where travel times are non-negative random variables.
Abstract
This paper introduces the Stochastic Clustered Team Orienteering Problem (SCTOP), a variant of the recently defined CluTOP where travel times are non-negative random variables. This problem aligns with the growing interest in prize-collecting problems and the challenge of optimizing routes under uncertainty. To address the Stochastic CluTOP, we propose a Simheuristic method integrating Monte Carlo simulations within an Adaptive Large Neighborhood Search (SimALNS). Additionally, we incorporate two policies, Continuous and Reactive, to adaptively manage the maximum route length in route generation process. The proposed approaches are validated on a well-established benchmark of the scientific literature to test the benefits of including Monte Carlo simulations in the route-design process and to evaluate the possible contributions of the two policies in case of higher profit variances. The results demonstrate that the Monte Carlo simulation allows SimALNS to consistently achieve higher stochastic performance compared to its deterministic counterpart. Moreover, the results highlight that across all algorithms tested, the Reactive strategy is the most effective.