Detailansicht
A heuristic and exact solution procedure for period traveling salesman problems
Devrnja Elitsa Karaeneva
Art der Arbeit
Magisterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.4873
URN
urn:nbn:at:at-ubw:1-29843.53215.797065-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
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.
Abstract
(Englisch)
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.
Schlagwörter
Schlagwörter
(Englisch)
Branch-and-bound-Algorithm XPRESS C++ PTSP NNS TSP Repair procedur exact method
Schlagwörter
(Deutsch)
Branch-and-bound-Algorithmus XPRESS C++ PTSP NNS TSP Repair Procedure exacte Methode
Autor*innen
Devrnja Elitsa Karaeneva
Haupttitel (Englisch)
A heuristic and exact solution procedure for period traveling salesman problems
Paralleltitel (Deutsch)
A heuristic and exact solution procedure for period traveling salesman problems
Paralleltitel (Englisch)
A heuristic and exact solution procedure for Period Traveling Salesman Problems
Publikationsjahr
2009
Umfangsangabe
VI, 71 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikation
85 Betriebswirtschaft > 85.32 Beschaffung, Materialwirtschaft
AC Nummer
AC07653946
Utheses ID
4343
Studienkennzahl
UA | 066 | 915 | |