Population-based vs. Single-solution Heuristics for the Travelling Thief Problem

The Travelling Thief Problem (TTP) is an optimization problem introduced in order to provide a more realistic model for real-world optimization problems. The problem combines the Travelling Salesman Problem and the Knapsack Problem and introduces the notion of interdependence between sub-problems. In this paper, we study and compare different approaches for solving the TTP from a metaheuristics perspective. Two heuristic algorithms are proposed. The first is a Memetic Algorithm, and the second is a single-solution heuristic empowered by Hill Climbing and Simulated Annealing. Two other state-of-the-art algorithms are briefly revisited, analyzed, and compared to our algorithms. The obtained results prove that our algorithms are very efficient for many TTP instances.