Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing

Many real-world problems are composed of multiple interacting sub-problems. However, few investigations have been carried out to look into tackling problems from a metaheuristics perspective. The Traveling Thief Problem (TTP) is a new NP-hard problem with two interdependent components that aim to provide a benchmark model to better represent this category of problems. In this paper, TTP is investigated theoretically and empirically. Two algorithms based on a 2-OPT steepest ascent hill climbing algorithm and the simulated annealing metaheuristic named CS2SA* and CS2SA-R are proposed to solve the problem. The obtained results show that the proposed algorithms are efficient for many TTP instances of different sizes and properties and are very competitive in comparison with two of the best-known state-of-the-art algorithms. (C) 2017 Elsevier Inc. All rights reserved.