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.

A heuristic and exact solution procedure for Period Traveling Salesman Problems

The aim of this thesis is to develop algorithms for the Period Traveling Salesmen Problem with two different computer programs: XPRESS and C++. The algorithm developed with XPRESS uses the exact method of solving the problem, based on branch-and-bound algorithm. The algorithm developed with C++ uses heuristic approaches, based on the philosophy of Nearest Neighbor Search (NNS), a simple heuristic, which searches for the closest point. The main goal is thereby the achieved results and their comparison.

The exact algorithm was coded in XPRESS IVE 2007. The XPRESS experiments were performed on a PC with 3.2 GHz. The heuristic algorithm was coded in C++ 2005 express edition and performed on laptop with 1.6 GHz.

The advantage of the heuristic method lies primarily in its simplicity. In fact the procedure is exempted from elaborate calculations and a lot of memory. So the operating expense is focused on generating new combinations and comparing the solution values thus obtained.