UNIVERSITÄTSBIBLIOTHEK

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 value. 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. Finally, an alternative recovery model is discussed, where a second-stage recovery tour is not required to visit all nodes of the graph. We show that the previously NP-hard evaluation of a fixed solution now becomes solvable in polynomial time.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Andre Chassein, Marc Goerigk
URN (Permalink):urn:nbn:de:hbz:386-kluedo-38988
Dokumentart:Preprint
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):15.10.2014
Jahr der Veröffentlichung:2014
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.10.2014
Seitenzahl:17
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012