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 potential applications in smart cities, humanitarian logistics, wildfire surveillance, etc. In the TOP, a fixed fleet of vehicles is employed to obtain rewards by visiting nodes in a network. All vehicles share common origin and destination locations. Since each vehicle has a limitation in time or traveling distance, not all nodes in the network can be visited. Hence, the goal is focused on the maximization of the collected reward, taking into account the aforementioned constraints. Most of the existing literature on the TOP focuses on its deterministic version, where rewards and travel times are assumed to be predefined values. This paper focuses on a more realistic TOP version, where travel times are modeled as random variables, which introduces reliability issues in the solutions due to the route-length constraint. In order to deal with these complexities, we propose a simheuristic algorithm that hybridizes biased-randomized heuristics with a variable neighborhood search and MCS. To test the quality of the solutions generated by the proposed simheuristic approach, we employ the well-known sample average approximation (SAA) method, as well as a combination model that hybridizes the metaheuristic used in the simheuristic approach with the SAA algorithm. The results show that our proposed simheuristic outperforms the SAA and the hybrid model both on the objective function values and computational time.