<div class="csl-bib-body">
<div class="csl-entry">Moldovan, M. (2015). <i>Implementing variations of the Traveling Salesperson Problem in a declarative dynamic programming environment</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2015.25364</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2015.25364
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/4680
-
dc.description
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zsfassung in dt. Sprache
-
dc.description.abstract
Das D-FLAT System ist ein Framework das die Vorteile von dynamischer Programmierung (DP) und Answer Set Programming (ASP) vereint. Hierbei wird die Eingabeinstanz zuerst in einen Baum zerlegt und anschließend wird ASP für das Befüllen der DP-Tabellen, basierend auf der deklarativen Spezifikation, verwendet. Dies wird entlang der Baumzerlegung von unten nach oben durchgeführt. Für einfache Graphenprobleme hat sich D-FLAT als durchaus effizient erwiesen, solange die Instanzen niedrige Baumweite aufweisen. Komplexere Probleme, wie zum Beispiel das NP-schwierige Optimierungsproblem des Handlungsreisenden, stellen weiterhin eine Herausforderung dar. Obwohl zahlreiche exakte sowie auch heuristische Ansätze für dieses Problem bekannt sind, gibt es bis dato noch keine Methode die sowohl durch praktische Effizienz, als auch durch eine einfache Handhabe und Adaptierbarkeit besticht. In dieser Diplomarbeit verwenden wir D-FLAT um eine vielseitige Lösung für das Handlungsreisendenproblem vorzuschlagen, welche in einem deklarativen, flexiblen Umfeld implementiert ist und eine kompetitive Alternative zu monolythischen ASP-Implementierungen auf Instanzen mit niedriger Baumweite darstellt.Wir stellen ein Konzept nach den Prinzipien der dynamischen Programmierung für das Handlungsreisendenproblem vor und implementieren zwei konkrete Versionen dieses Problems in D-FLAT. Unsere Aussagen untermauern wir mit den Ergebnissen unserer Experimente, die wir sowohl auf generierten Graphen, als auch auf Instanzen die auf dem öffentlichenWiener Verkehrsnetz basieren, durchgeführt haben. Neben den vielversprechenden Resultaten für Probleminstanzen mit niedriger Baumweite bekommt unsere Arbeit zusätzliche Bedeutung durch die Tatsache, dass das neu entwickelte, deklarative Konzept auch für zahlreiche weitere Probleme, die mit dem Handlungsreisendenproblem verwandt sind, angewandt werden kann.
de
dc.description.abstract
The D-FLAT System is a free framework that combines the advantages of dynamic programming with those of answer set programming (ASP). Hereby, the input instance is first decomposed into a so-called tree decomposition, then ASP is used to declaratively specify the materialization of the tables for the dynamic programming, which is done along the tree decomposition in a bottom-up manner. D-FLAT proved to perform well for simple graph problems when applied on instances with small treewidth. A more complex and prominent combinatorial problem is the traveling salesperson problem (TSP), which is an NP-hard optimization problem. Solving the TSP on large instances still represents a big challenge. There exist both exact algorithms and heuristics which deal with the TSP, but to the best of our knowledge neither of the two methods is at the same time practically efficient and allows for rapid prototyping. In this master's thesis we use the D-FLAT System to propose a versatile solution for the TSP, which is implemented in a declarative, flexible environment and offers a competitive alternative to monolithic ASP implementations on instances with small treewidth. We present the dynamic programming concept we developed for the TSP and introduce the implementations of two variations of the TSP for D-FLAT. To prove the aforementioned claim, we conduct a series of experiments on generated graphs, as well as on real world instances based on the Viennese public transportation system. The significance of our work derives not only from the results of these experiments but also from the fact that the concept we proposed can be adapted for other NP-hard combinatorial optimization problems that are related to the TSP.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Dynamische Programmierung
de
dc.subject
Answer-Set Programming
de
dc.subject
Traveling Salesperson
de
dc.subject
Dynamic Programming
en
dc.subject
Answer-Set Programming
en
dc.subject
Traveling Salesperson
en
dc.title
Implementing variations of the Traveling Salesperson Problem in a declarative dynamic programming environment
en
dc.title.alternative
Lösen von TSP Problemen in einer deklarativen Dynamic-Programming Umgebung
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2015.25364
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Marius Moldovan
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Abseher, Michael
-
tuw.publication.orgunit
E184 - Institut für Informationssysteme
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC12270210
-
dc.description.numberOfPages
95
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-79192
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence