A consensus fixing heuristic for the stochastic prize collecting TSP

We consider the two-stage stochastic prize collecting traveling salesman 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 parallel heuristics based on consensus fixing: The problems are solved independently 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.