Title: Solving the travelling thief problem with an evolutionary algorithm
Language: English
Authors: Wachter, Christoph 
Qualification level: Diploma
Advisor: Raidl, Günther 
Assisting Advisor: Hu, Bin 
Biesinger, Benjamin
Issue Date: 2015
Number of Pages: 69
Qualification level: Diploma
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.

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.
Keywords: Travelling Thief Problem; Evolutionärer Algorithmus; Kombinatorische Optimierung
Travelling Thief Problem; Evolutionary Algorithm; Combinatorial Optimization
URI: http://media.obvsg.at/AC12685806-2001
Library ID: AC12685806
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

11
checked on Aug 24, 2021

Download(s)

10
checked on Aug 24, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.