Hybrid Evolutionary Algorithm for Travelling Thief Problem

Main Article Content

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.

Article Details

How to Cite
Hybrid Evolutionary Algorithm for Travelling Thief Problem. (2020). INFOCOMP Journal of Computer Science, 19(2), 132-140. Retrieved from http://infocomp.dcc.ufla.br/index.php/infocomp/article/view/1030
Section
Articles