EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4377. A consensus fixing heuristic for the stochastic prize collecting TSP
Invited abstract in session MA-26: Combinatorial optimization topics in transportation, stream Combinatorial Optimization.
Monday, 8:30-10:00Room: 012 (building: 208)
Authors (first author is the speaker)
| 1. | David Pisinger
|
| Management, DTU |
Abstract
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.
Keywords
- Combinatorial Optimization
- Stochastic Optimization
- Vehicle Routing
Status: accepted
Back to the list of papers