Fachbereich 04 - Wirtschaftswissenschaftliche Fakultät
Lehrstuhl für Betriebswirtschaftslehre, insbes. Unternehmensforschung
Unternehmensforschung

Untersuchungen zur heuristischen Lösung des
euklidischen, zweidimensionalen Traveling Salesman Problems

Beim Problem des Handlungsreisenden (Traveling Salesman Problem, TSP) handelt es sich um das wohl prominenteste Mitglied der Gruppe der kombinatorischen Optimierungsprobleme. Nach wie vor sind nur relativ kleine Probleminstanzen exakt lösbar. Im Rahmen des Forschungsprojektes werden ausgesuchte heuristische Lösungsansätze implementiert und an ausgewählten, meist bekannten Probleminstanzen getestet. Schwerpunkt der Untersuchung ist die Auswirkung der jeweiligen Problem-Relaxationen auf die mögliche Güte der besten gefundenen Lösung. Von besonderem Interesse sind dabei die Definition und zahlenmäßige Beschränkung der zu berücksichtigenden Variablen. Aufbauend auf diesen Erkenntnissen wird eine neue Heuristik formuliert, deren Variablenzahl nur linear mit der Problemgröße wächst und die dennoch gute Lösungen für eine bestimmte Gruppe von TSP erwarten läßt. Die Eigenschaften dieser Heuristik werden anhand der bekannten Beispiele getestet, dokumentiert und analysiert.

Beteiligte Wissenschaftler:

Prof. Dr. Wolfgang von Zwehl, Dipl.-Kfm. Andreas Rohleder