A Hybrid Genetic Algorithm with Tabu Search for Optimization of the Traveling Thief Problem

Until now, several approaches such as evolutionary computing and heuristic methods have been presented to optimize the traveling thief problem (TTP). However, most of these approaches consider the TTP components independently, usually considering the traveling salesman problem (TSP) and then tackling the knapsack problem (KP), despite their interdependent nature. In this paper, we investigate the use of a hybrid genetic algorithm (GA) and tabu search (TS) for the TTP. Therefore, a novel hybrid genetic approach called GATS is proposed and compared with the state-of-the-art approaches. The key aspect of GATS is that TTP solutions are considered by firmly taking into account the interdependent nature of the TTP subcomponents, where all its operators are simultaneously implemented on TSP and KP solutions. A comprehensive set of TTP benchmark datasets was adopted to investigate the effectiveness of GATS. We selected 540 instances for our investigation, which comprised five different groups of cities (51, 52, 76, 100 and 150 cities) and different groupings of items, from 50 to 745 items. All types of knapsack (uncorrelated, uncorrelated with similar weights and bonded strongly correlated) with all different knapsack capacities were also taken into consideration. Different initialization methods were empirically investigated as well. The results of the computational experiments demonstrated that GATS is capable of surpassing the state-of-the-art results for various instances.

@article{Alharbi2018,
  title     = {A Hybrid Genetic Algorithm with Tabu Search for Optimization of the Traveling Thief Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {9},
  number    = {11},
  year      = {2018},
  publisher = {The Science and Information Organization},
  author    = {Saad T Alharbi},
  doi       = {10.14569/IJACSA.2018.091138},
  url       = {https://doi.org/10.14569/IJACSA.2018.091138}
}