Solving the travelling thief problem with an evolutionary algorithm

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.