Approximate approaches to the traveling thief problem

Abstract

This study addresses the recently introduced Traveling Thief Problem (TTP) which combines the classical Traveling Salesman Problem (TSP) with the 0-1 Knapsack Problem (KP). The problem consists of a set of cities, each containing a set of available items with weights and profits. It involves searching for a permutation of the cities to visit and a decision on items to pick. A selected item contributes its profit to the overall profit at the price of higher transportation cost incurred by its weight. The objective is to maximize the resulting profit. We propose a number of problem-specific packing strategies run on top of TSP solutions derived by the Chained Lin-Kernighan heuristic. The investigations provided on the set of benchmark instances prove their rapidity and efficiency when compared with an approximate mixed integer programming based approach and state-of-the-art heuristic solutions from the literature.