Solving the stochastic team orienteering problem: comparing simheuristics with the sample average approximation method

Abstract

The team orienteering problem (TOP) is an NP-hard optimization problem with an increasing number of po-tential applications in smart cities, humanitarian logistics, wildfire surveillance, etc. In the TOP, a fixed fleetof vehicles is employed to obtain rewards by visiting nodes in a network. All vehicles share common originand destination locations. Since each vehicle has a limitation in time or traveling distance, not all nodes inthe network can be visited. Hence, the goal is focused on the maximization of the collected reward, takinginto account the aforementioned constraints. Most of the existing literature on the TOP focuses on its de-terministic version, where rewards and travel times are assumed to be predefined values. This paper focuseson a more realistic TOP version, where travel times are modeled as random variables, which introduces reli-ability issues in the solutions due to the route-length constraint. In order to deal with these complexities, wepropose a simheuristic algorithm that hybridizes biased-randomized heuristics with a variable neighborhoodsearch and MCS. To test the quality of the solutions generated by the proposed simheuristic approach, weemploy the well-known sample average approximation (SAA) method, as well as a combination model thathybridizes the metaheuristic used in the simheuristic approach with the SAA algorithm. The results showthat our proposed simheuristic outperforms the SAA and the hybrid model both on the objective functionvalues and computational time.

This work has been partially supported by the Spanish Ministry of Science, Innovation, and Uni-versities (PID2019-111100RB-C21/C22/AEI/10.13039/501100011033). Similarly, we appreciatethe financial support of the Barcelona City Council and “La Caixa” (21S09355-001).

Peer Reviewed

Postprint (published version)