Abstract (deu)
Heuristisches und exaktes Verfahren zur Lösung von Period Traveling Salesman Probleme
Das Ziel dieser Magisterarbeit ist die Entwicklung von Algorithmen für die Period Traveling Salesman Probleme mit zwei verschiedenen Computer-Programmen: XPRESS und C++. Der Algorithmus, entwickelt mit XPRESS, nutzt die genaue Methode zur Lösung des Problems, basierend auf der Grundlage des Branch-and-bound-Algorithmus. Der Algorithmus, entwickelt mit C++, verwendet heuristische Ansätze, die auf der Philosophie der Nearest Neighbor Suche ("NNS") beziehen, eine einfache Heuristik, die nach dem nächstgelegenen Punkt sucht. Das Hauptziel der Arbeit ist, die erzielten Ergebnisse zu vergleichen.
Der genaue Algorithmus in dieser Arbeit ist in XPRESS IVE 2007 codiert. Die XPRESS Experimente wurden auf einem PC mit 3,2 GHz durchgeführt. Der heuristische Algorithmus ist in C++ 2005 Express Edition codiert und auf Laptop mit 1,6 GHz implementiert.
Der Vorteil der heuristischen Methode liegt in erster Linie in ihrer Einfachheit. In der Tat ist das Verfahren von aufwändigen Berechnungen und von Anforderung viel Arbeitsspeicher ausgenommen. Die betrieblichen Aufwendungen sind auf die Generierung von neuen Kombinationen und den Vergleich der so erhaltenen Werte konzentriert.