Seit seiner ersten Beschreibung im Jahr 1930 ist das Traveling Salesman Problem eines der prominentesten Beispiele ungelöster Probleme der kombinatorischen Optimierung. Es fragt auf einem vollständigen, symmetrischen Graphen nach einem kürzesten Ha- miltonkreis. Im ersten Teil der vorliegenden Arbeit werden grundlegende Verfahren zur Lösung des Problems vorgestellt. Dazu zählen die beiden Heuristiken Nearest-Neighbor und Multiple-Fragment. Als Vertreter exakter Lösungsverfahren wird eine auf Eins-Bäumen basierende Lagrange-Relaxierung in Verbindung mit dem Branch-and-Bound-Algorithmus betrachtet. Diese Verfahren sind Teil der in der zweiten Hälfte beschriebenen Webapplikation, die im Zuge der Arbeit erstellt wurde. Sie dient der anschaulichen Darstellung der Algorith- men mit dem Ziel, Schülern und Studenten Methoden der kombinatorische Optimierung näherzubringen. Die Applikation bedient sich dabei neuester Webtechnologien wie HTML 5 und jQuery.     «

Seit seiner ersten Beschreibung im Jahr 1930 ist das Traveling Salesman Problem eines der prominentesten Beispiele ungelöster Probleme der kombinatorischen Optimierung. Es fragt auf einem vollständigen, symmetrischen Graphen nach einem kürzesten Ha- miltonkreis. Im ersten Teil der vorliegenden Arbeit werden grundlegende Verfahren zur Lösung des Problems vorgestellt. Dazu zählen die beiden Heuristiken Nearest-Neighbor und Multiple-Fragment. Als Vertreter exakter Lösungsverfahren wird eine auf Ei...     »

Since its first description in the year 1930, the Traveling Salesman Problem is one of the most prominent examples of combinatorial optimization. It asks for the shortest Hamiltonian cycle on a complete, symmetric graph. In the first part of this thesis, basic methods for solving this problem are presented. These include the two heuristics nearest-neighbor and multiple-fragment. Representing exact algorithms, a Lagrangian relaxation method based on 1-trees is examined in connection with a branch-and-bound algorithm. These methods are part of the web application, which was developed during the creation of this thesis and is described in the second part. It is meant to depict the presented algorithms in order to give students an understanding of combinatorial optimization methods. The application therefore uses state-of-the-art web-based technologies such as HTML 5 and jQuery.     «

Since its first description in the year 1930, the Traveling Salesman Problem is one of the most prominent examples of combinatorial optimization. It asks for the shortest Hamiltonian cycle on a complete, symmetric graph. In the first part of this thesis, basic methods for solving this problem are presented. These include the two heuristics nearest-neighbor and multiple-fragment. Representing exact algorithms, a Lagrangian relaxation method based on 1-trees is examined in connection with a branc...     »