Investigation of the Traveling Thief Problem

Abstract

Traveling Thief Problem (TTP) is a relatively new benchmark problem created to study problems which consist of interdependent subproblems. In this thesis various operators and strategies in the literature of TTP are investigated in order to understand if and how they work and whether they can be improved. Operators include 2-opt, Insertion, Bitflip and Exchange. Strategies include greedy packing plan heuristic, neighborhood reduction and use of various tour crossovers in a genetic algorithm. The investigation is done in part by fitness landscape analysis. The first part of the thesis is a literature study and discusses TTP, the subproblems of TTP and fitness landscape analysis. The second part of the thesis consists of experiments which investigate these various operators and strategies in the literature. The second part also consists of time complexity improvements for the commonly used local search operators for TTP. Experiments show that greedy packing heuristics have a high chance of finding optimal or near-optimal solutions. Other experiments show that between nearest neighbor reduction, k-quadrant nearest neighbor reduction and reduction by Delaunay triangulation there is no significant difference in performance. Fitness landscape analysis shows among other things that TTP instances contain a lot of local optima but their distance to the global optimum is correlated with its fitness. Local optima networks with respect to an iterated local search shows that TTP has a multi-funnel structure. Other experiments show that a steady state genetic algorithm with edge assembly crossover outperforms multistart local search, iterated local search and genetic algorithms with other tour crossovers. At last there is a comprehensive comparative study which contains new best solutions to almost all studied instances of the commonly used benchmark suite.