.png){kind=icon}
.png){kind=icon}
Return
Distributed or integrated stochastic ALNS? — Two-stage stochastic team orienteering problem
.png){kind=icon}
OA
AI
D
DOI：10.1016/j.cor.2025.107365.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Two-stage stochastic optimization
Metaheuristics
Consensus fixing
Adaptive large neighborhood search
Orienteering problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available
Cited Papers