Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On the recoverable robust traveling salesman problem

On the recoverable robust traveling salesman problem We consider an uncertain traveling salesman problem, where distances between nodes are not known exactly, but may stem from an uncertainty set of possible scenarios. This uncertainty set is given as intervals with an additional bound on the number of distances that may deviate from their expected, nominal values. A recoverable robust model is proposed, that allows a tour to change a bounded number of edges once a scenario becomes known. As the model contains an exponential number of constraints and variables, an iterative algorithm is proposed, in which tours and scenarios are computed alternately. While this approach is able to find a provably optimal solution to the robust model, it also needs to solve increasingly complex subproblems. Therefore, we also consider heuristic solution procedures based on local search moves using a heuristic estimate of the actual objective function. In computational experiments, these approaches are compared. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Optimization Letters Springer Journals

On the recoverable robust traveling salesman problem

Optimization Letters , Volume 10 (7) – Sep 19, 2015

Loading next page...
 
/lp/springer-journals/on-the-recoverable-robust-traveling-salesman-problem-SmAWTOkzCR

References (20)

Publisher
Springer Journals
Copyright
Copyright © 2015 by Springer-Verlag Berlin Heidelberg
Subject
Mathematics; Optimization; Operation Research/Decision Theory; Computational Intelligence; Numerical and Computational Physics
ISSN
1862-4472
eISSN
1862-4480
DOI
10.1007/s11590-015-0949-5
Publisher site
See Article on Publisher Site

Abstract

We consider an uncertain traveling salesman problem, where distances between nodes are not known exactly, but may stem from an uncertainty set of possible scenarios. This uncertainty set is given as intervals with an additional bound on the number of distances that may deviate from their expected, nominal values. A recoverable robust model is proposed, that allows a tour to change a bounded number of edges once a scenario becomes known. As the model contains an exponential number of constraints and variables, an iterative algorithm is proposed, in which tours and scenarios are computed alternately. While this approach is able to find a provably optimal solution to the robust model, it also needs to solve increasingly complex subproblems. Therefore, we also consider heuristic solution procedures based on local search moves using a heuristic estimate of the actual objective function. In computational experiments, these approaches are compared.

Journal

Optimization LettersSpringer Journals

Published: Sep 19, 2015

There are no references for this article.