Solving the Traveling Thief Problem Based on Item Selection Weight and Reverse-Order Allocation

Abstract

The traveling thief problem (TTP) is a challenging combinatorial optimization problem that has attracted many scholars, the problem interconnects two well-known NP-hard problems: the traveling salesman problem and the 0-1 knapsack problem. Various approaches have increasingly been proposed to solve this novel problem that combines two interdependent subproblems. In this paper, the TTP is investigated theoretically and empirically. This paper proposed an approach based on item selection weight and reverse-order allocation. A novel method to calculate the score value of each item for item selection, which expands the effect of the item’s weight, was introduced. Furthermore, the approach adopted reverse-order allocation, which selects items in an inverse order according to the traveling route. Different approaches for solving the TTP are compared and analyzed. The experimental investigations suggest that our proposed approach is competitive for many instances of various sizes and types compared to other heuristics.

Keywords

• Traveling thief problem
• interdependence
• item selection weight
• reverse order allocation