Hybrid Evolutionary Algorithm for Travelling Thief Problem

Abstract

Travelling Thief Problem (TTP) is a benchmark problem, where two sub-problems, namely Travelling Salesman Problem (TSP), and 0/1 Knapsack Problem (KP) interact. Since, the TSP and KP both comes under NP-hard, so the complexity to solve TTP will be decided by the investigation of inter-dependency factor. The objective of TTP problem is to suggest a picking plan with a best tour to a thief in such a way that the thief visits all cities exactly once with the collection of items in his knapsack leading to maximum benefits. With increasing size of TSP instance, a well-crafted search technique is required to maintain the inter-dependency. Here, we emphasis on the inter-dependency to design a solution framework which balance the interwoven between individual components. In this article, we suggest a hybrid Evolutionary Algorithm (EA) framework that strengthens the inter-dependency by giving best tour and picking plan concurrently. Here, we use a local search routine to improve the tour as well the objective function. Additionally, one more heuristic about KP component, is used for a better picking plan. On applying the proposed framework we have found that it gives most promising results compared to the classical EA approach.