Home > Research > Publications & Outputs > On the recoverable robust traveling salesman pr...

Associated organisational unit

Electronic data

  • paper_bw

    Rights statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-015-0949-5

    Accepted author manuscript, 337 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

On the recoverable robust traveling salesman problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published

Standard

On the recoverable robust traveling salesman problem. / Chassein, André; Goerigk, Marc.
In: Optimization Letters, Vol. 10, No. 7, 10.2016, p. 1479-1492.

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Harvard

Chassein, A & Goerigk, M 2016, 'On the recoverable robust traveling salesman problem', Optimization Letters, vol. 10, no. 7, pp. 1479-1492. https://doi.org/10.1007/s11590-015-0949-5

APA

Vancouver

Chassein A, Goerigk M. On the recoverable robust traveling salesman problem. Optimization Letters. 2016 Oct;10(7):1479-1492. Epub 2015 Sept 19. doi: 10.1007/s11590-015-0949-5

Author

Chassein, André ; Goerigk, Marc. / On the recoverable robust traveling salesman problem. In: Optimization Letters. 2016 ; Vol. 10, No. 7. pp. 1479-1492.

Bibtex

@article{e277c8ff13fa417fa58e03b56948ae29,
title = "On the recoverable robust traveling salesman problem",
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.",
keywords = "Recoverable robustness, Robust optimization, Traveling salesman problem",
author = "Andr{\'e} Chassein and Marc Goerigk",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-015-0949-5",
year = "2016",
month = oct,
doi = "10.1007/s11590-015-0949-5",
language = "English",
volume = "10",
pages = "1479--1492",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",
number = "7",

}

RIS

TY - JOUR

T1 - On the recoverable robust traveling salesman problem

AU - Chassein, André

AU - Goerigk, Marc

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s11590-015-0949-5

PY - 2016/10

Y1 - 2016/10

N2 - 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.

AB - 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.

KW - Recoverable robustness

KW - Robust optimization

KW - Traveling salesman problem

U2 - 10.1007/s11590-015-0949-5

DO - 10.1007/s11590-015-0949-5

M3 - Journal article

AN - SCOPUS:84942039461

VL - 10

SP - 1479

EP - 1492

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 7

ER -