EURO 2025 Leeds
Abstract Submission

1951. Stochastic ALNS for the the stochastic team orienteering problem

Invited abstract in session MC-20: Metaheuristic algorithms, stream Combinatorial Optimization.

Monday, 12:30-14:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. David Pisinger
Management, DTU

Abstract

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 only be collected once. In the stochastic version of the problem, the customers are split into subscription customers that must be visited every day, and stochastic on-demand customers. The task is to select a subset of the subscription customers, such that the expected profit of served subscription and on-demand customers is maximized.

We present a stochastic Adaptive Large Neighborhood Search (SALNS) algorithm for the problem, in which 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.
Both customers, demands and travel times can be stochastic as long as they can be represented by a number of scenarios. Various destroy and repair neighborhoods are presented for both the upper-level and lower-level ALNS algorithms.

Computational experiments show that the algorithm scales well with the number of scenarios, making it possible to solve instances with up to 1000 customers and 64 scenarios.

Keywords

Status: accepted

Back to the list of papers