A local search based approach for solving the Travelling Thief Problem: The pros and cons

The Travelling Thief Problem (TTP) is a novel problem that aims to provide a benchmark model of combinatorial optimization problems with multiple interdependent components. The TTP combines two other well known benchmark problems: the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP). The aim of this paper is to study the interdependence between the TTP's components, and how it makes solving each sub-problem independently from the other useless for solving the overall problem. A local search approach is proposed to solve the TTP. Two simple iterative neighborhood algorithms based on our approach are presented, analyzed, and compared to other algorithms. Initialization strategies are empirically investigated. The experimental results confirm that our approach was able to find new better solutions for many TTP instances.