Distributed or integrated stochastic ALNS? — Two-stage stochastic team orienteering problem

The team orienteering problem is a generalization of the selective traveling salesman problem. A fleet of vehicles is available to visit a subset of customers within a given time limit. Each customer has an associated profit, and the profit can be collected at most once. In the two-stage stochastic version of the problem, the customers are split into deterministic subscription customers, that (if selected) must be visited in all scenarios, and stochastic on-demand customers that are optional in each scenario. The task is to select a subset of the subscription customers, such that the expected profit of selected subscription customers and on-demand customers is maximized. We present a distributed and an integrated Stochastic Adaptive Large Neighborhood Search (SALNS) algorithm for the problem. In the distributed SALNS, an upper-level local search method operates on the first-stage decision variables, while a number of lower-level local search methods optimize the individual scenarios. In the integrated SALNS a single local search method operates on both the first-stage and second-stage decision variables. Computational experiments comparing the two approaches show that the distributed algorithm is able to find better solutions in shorter time. Furthermore, the distributed algorithm scales well with the number of scenarios, making it possible to solve instances with up to 400 first-stage and 400 second-stage customers for 128 scenarios. In many cases, we see an improvement of more than 20% compared to the initial solution.