Ein Handlungsreisender will, ausgehend von seinem Wohnort, mehrere Städte genau
einmal besuchen und danach wieder nach Hause zurückkehren, welche Reihenfolge
der Städte führt zu einer möglichst kurzen Rundreise? Dies ist das sogenannte
Traveling Salesman Problem (TSP), ein zentrales Problem der kombinatorischen
Optimierung. Zum (wahrscheinlich) erstenmal wird es in dem 1832 erschienenen
Buch "Der Handlungsreisende, wie er sein soll und was er zu thun hat, um
Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss
zu sein, Von einem alten Commis-Voyageur" angesprochen, während
sich die Bezeichnung 'Traveling Salesman Problem' um 1931 etabliert hat. Es
hat vielfältige Anwendungen in Bereichen wie Routenplanung,
Fahrplangestaltung, Platinenlayout, Netzwerkplanung, Maschinenbelegung, ...
Prinzipiell läßt sich das Traveling Salesman Problem durch Untersuchung aller möglichen Permutationen eindeutig lösen. Dies erweist sich jedoch nur für kleine Städtezahlen n als praktikabel, da die Anzahl der möglichen Rundreisen gemäß n! wächst. Es gehört sogar zu den sogenannten NP-vollständigen Problemen, für die es nach heutigem Wissen keinen Algorithmus mit polynomialer Komplexität gibt. Das Thema dieser Arbeit ist es, Verfahren vorzustellen, mit denen man trotzdem in akzeptabler Zeit zu (Näherungs-)Lösungen kommt, und diese als Programme mit komfortabler Benutzeroberfläche zu implementieren.
Literatur zum Traveling Salesman Problem gibt es reichlich, warum also
noch eine weitere Arbeit? Merkmale der meisten vorhandenen Texte sind die
Konzentration auf einen Teilbereich der vorhandenen Lösungsmöglichkeiten und
daß häufig nur die prinzipielle Funktionsweise der Algorithmen,
nicht aber die Umsetzung in konkrete Programme, erläutert wird. Ist dies doch
der Fall, so sind sie mangels einer ausgearbeiteten Benutzeroberfläche
meist nur umständlich anzuwenden. Deshalb sollten in dieser Arbeit die
folgenden Punkte verwirklicht werden:
Graphentheorie ist in den Lehrplänen der Mathematik normalerweise nicht vorgesehen, weshalb die zur Verfügung stehende Zeit es im allgemeinen notwendig macht, sich auf ein oder zwei Probleme zu beschränken. Das Traveling Salesman Problem bietet sich hier aus mehreren Gründen an: Es verlangt nur ein Minimum an Definitionen und Grundlagen und ist anschaulich und leicht zu verstehen, trotzdem ist 'die Lösung' nicht trivial. Vielmehr gibt es ein breites Spektrum von Ansätzen und Verfahren in verschiedensten Schwierigkeitsgraden, was es erlaubt, den zu behandelnden Stoff auf die konkrete Situation hin auszuwählen und abzustimmen. Außerdem bieten die Heuristiken den Schülern Spielraum, eigene Ideen und Verbesserungen einzubringen, die sich mit den Bibliotheksroutinen leicht und trotzdem ansprechend realisieren lassen.
Unter "Programminfos" und
"Heuristiken" finden sich Auszüge aus der
Arbeit, der komplette Text (Inhaltsverzeichnis)
ist auf Anfrage erhältlich, Turbo Pascal
in der Version 5.5 bei
http://community.borland.com/museum/ Free Pascal bei
http://www.freepascal.org.
Über Rückmeldungen und Kommentare würde ich mich freuen
(thkle@gmx.net).
