Efficiently Solving the Bi-Objective Traveling Thief Problem Using Imperialist Competitive Algorithm : Case of Small Instances

Real-life problems are complex because they are typically made up of several sub-problems interacting. These interactions establish an interdependent relationship in which the quality of one partial solution impacts the quality of other partial solutions. Recently, a new benchmark known as the Traveling Thief Problem (TTP) has been developed to present a more realistic model for multi-component optimization problems in the real world. TTP combines Traveling Salesman Problem (TSP) with Knapsack Problem (KP). While each component of the problem has been widely studied, solving them separately does not optimally solve the overall problem because of the existing interdependency between the TSP and KP. In this study, we investigated an Imperialist Competitive Algorithm (ICA) to deal with the TTP as a whole and solve its two components simultaneously. 30 TTP instances from the eil51 dataset are selected: 50 cities, one item in each town, all three types of the knapsack problem, and all ten knapsack capacities. We employed the proposed ICA to solve the selected instances and compared its results with 21 algorithms in the literature. The results indicated that ICA improves 11 best-known solutions (up to 14%), especially in instances with the Bounded Strongly Correlated (BSC) type. Moreover, ICA was the second-best algorithm in the other five cases