Schnelle Rundreisen: Das Travelling Salesman-Problem
Please always quote using this URN: urn:nbn:de:0297-zib-8901
- Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einführung in das TSP gegeben. Es werden Problemstellungen erläutert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis TSPs von atemberaubender Größe lösen kann.
| Author: | Martin Grötschel |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Rundreisen; TSP; Travelling-Salesman-Problem; optimale Tour |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-01 Instructional exposition (textbooks, tutorial papers, etc.) |
| 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
| 97-XX MATHEMATICS EDUCATION / 97-01 Instructional exposition (textbooks, tutorial papers, etc.) | |
| Date of first Publication: | 2005/12/14 |
| Series (Serial Number): | ZIB-Report (05-57) |
| ZIB-Reportnumber: | 05-57 |
| Published in: | Ersch. in: Kombinatorische Optimierung erleben - In Studium und Unterricht von Stefan Hußmann und Brigitte Lutz-Westphal. Aus der Reihe: Mathematik erleben. Unter Mitarbeit von Brieden, Andreas / Gritzmann, Peter / Grötschel, Martin / Leuders, Timo. Vieweg, 2007. ISBN: 978-3-528-03216-6 S.95-128 |
