<div class="csl-bib-body">
<div class="csl-entry">Wachter, C. (2015). <i>Solving the travelling thief problem with an evolutionary algorithm</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2015.27702</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2015.27702
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/4106
-
dc.description
Zusammenfassung in deutscher Sprache
-
dc.description.abstract
Optimierungsprobleme in wirklichen Einsatzszenarien bestehen oftmals aus verschiedenen, miteinander verknüpften und sich gegenseitig beeinflussenden NP-schweren Optimierungsproblemen. Daher wird in dieser Diplomarbeit das Travelling Thief Problem (TTP) näher betrachtet. Das TTP besteht aus dem bereits sehr gut erforschten Knapsack Problem (KP) und dem Travelling Salesman Problem (TSP). Beim TTP versucht ein Dieb, auf seiner Tour, so viele Gegenstände wie möglich, einzusammeln, wobei er die Maximalkapazität seines Rucksacks nicht überschreiten darf. Alle Gegenstände sind sowohl mit einem Gewicht als auch einem Profit verknüpft. Durch das Mitnehmen eines Gegenstandes erhöht der Dieb seinen Profit, aber er reduziert auch seine Reisegeschwindigkeit auf seiner restlichen Tour. Da er für seinen Rucksack eine Miete pro Zeiteinheit bezahlen muss versucht er seine Reisezeiten zu minimieren und den Profit durch eingesammelte Gegenstände zu maximieren. Ein mögliches Anwendungsszenario wäre zum Beispiel eine Lieferfirma, welche Packete an bestimmten Orten abholt welche in einer Route abgefahren werden. Das Abholen der Packete erhöht den Profit, erhöht aber die Fahrtdauer der Route und zusätzlich hat der Lieferwagen nur ein begrenztes Fassungsvermögen. Diese Diplomarbeit wird einen neuen, state-of-the-art hybriden genetischen Algorithmus vorstellen um das TTP heuristisch zu lösen. Der Algorithmus besteht aus einem genetischen Algorithmus und zusätzlichen lokalen Suche Operatoren. Die meisten dieser Operatoren versuchen entweder das TSP oder das KP alleine zu lösen. Die Lösung für das andere Subproblem wird dann von der bereits existierenden Lösung des anderen Subproblems abgeleitet. Zusätzlich wird ein Lösungsversuch vorgestellt, bei dem jedes Subproblem einfach für sich gelöst wird und die beiden Lösungen in einer Gesamtlösung für das TTP zusammengefügt. Dies dient dazu um die Wichtigkeit der Betrachtung der Koppelung der Subprobleme zu untersuchen. Alle Varianten des Algorithmus werden miteinander und so weit existierenden Lösungsversuchen aus der Literatur verglichen. Die Ergebnisse zeigen, dass der eingeführte hybride genetische Algorithmus vergleichbare und auf kleinen Instanzen sogar bessere Resultate erzielt.
de
dc.description.abstract
Optimization problems in real world scenarios often consist of different, interconnected NP-hard optimization problems. In this thesis the Travelling Thief Problem (TTP) is considered. It combines the well known knapsack problem (KP) and the travelling salesman problem (TSP). In the TTP a person called "thief" tries to collect as many items, on different nodes he is visiting during his tour, respecting the capacity of his knapsack, as possible. These items have associated a weight and a profit. Collecting an item increases the profit but also decreases the thief's travel speed on his remaining tour. As he has to pay a rent for his knapsack per time unit he tries to minimize his travel time for his tour and to maximize his profit by collecting items. A possible application for the TTP could be a delivery company which has to pick up packages at different locations which are combined in a route. Picking up packages leads to a profit gain but decreases travel speed and the delivery has a maximum cargo capacity. This thesis will provide a new state of the art hybrid genetic algorithm to solve the TTP heuristically. This algorithm consists of a genetic algorithm and additional local search operators. Most of these operators will focus on either the embedded TSP or the KP subproblem. For each partial candidate solution the other part is derived from this partial solution. Additionally, an approach where each subproblem will be solved on its own and combined in a solution for the TTP will be provided to examine the importance of the interconnection between the two subproblems. All algorithmic variants are compared to each other and to so far existing solution approaches from the literature. Computational results show that our hybrid genetic algorithm is competitive to these approaches and even outperforms them especially on smaller instances.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Travelling Thief Problem
de
dc.subject
Evolutionärer Algorithmus
de
dc.subject
Kombinatorische Optimierung
de
dc.subject
Travelling Thief Problem
en
dc.subject
Evolutionary Algorithm
en
dc.subject
Combinatorial Optimization
en
dc.title
Solving the travelling thief problem with an evolutionary algorithm
en
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.27702
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Christoph Wachter
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Hu, Bin
-
dc.contributor.assistant
Biesinger, Benjamin
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC12685806
-
dc.description.numberOfPages
69
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-78760
-
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
-
tuw.assistant.staffStatus
exstaff
-
tuw.advisor.orcid
0000-0002-3293-177X
-
item.mimetype
application/pdf
-
item.grantfulltext
open
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
crisitem.author.dept
E194-04 - Forschungsbereich Data Science
-
crisitem.author.parentorg
E194 - Institut für Information Systems Engineering