Fast Heuristics for the Multiple Traveling Thieves Problem

The traveling thief problem (TTP) is fast gaining attention for being a challenging combinatorial optimization problem. A number of algorithms have been proposed for solving this problem in the recent past. Despite being a challenging problem, it is often argued if TTP is realistic enough because of its formulation, which only allows a single thief to travel across hundreds or thousands of cities to collect (steal) items. In addition, the thief is required to visit all cities, regardless of whether an item is stolen there or not. In this paper we discuss the shortcomings of the current formulation and present a relaxed version of the problem which allows multiple thieves to travel across different cities with the aim of maximizing the group's collective profit. A number of fast heuristics for solving the newly proposed multiple traveling thieves problem (MTTP) are also proposed and evaluated.