A consensus fixing heuristic for the stochastic prize collecting TSP

Description

We consider the two-stage stochastic prize collecting traveling sales-
man problem, in which the objective is to maximize profit of served
customers minus driving costs. The first-stage customers are to be
served every day, while the second-stage customers fluctuate from day
to day. The task is to select a subset of the first-stage customers, such
that the expected earning is maximized. We present a highly paral-
lel heuristics based on consensus fixing: The problems are solved in-
dependently for each scenario using a variable neighborhood search
heuristic. Then, the scenarios try to reach consensus about fixing a
single first-stage variable, using various score functions. The process
of alternating between heuristic solution and variable fixing is repeated
until all first-stage variables have been fixed. Computational results are
reported for instances having up to 500 first-state and 500 second-stage
customers.

Period	1 Jul 2024
Event title	EURO-2024 Copenhagen: 33rd European Conference on Operational Research
Event type	Conference
Conference number	33
Location	Copenhagen, DenmarkShow on map
Degree of Recognition	International