A novel List-Constrained Randomized VND approach in GPU for the Traveling Thief Problem

The Traveling Thief Problem (TTP) is a multi-component combinatorial optimization problem that combines two well-known problems in the literature: the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP). This paper proposes a novel list-constrained local search process inspired in Variable Neighborhood Descent (VND) for multiple neighborhood structures, combined with a metaheuristic Greedy Randomized Adaptive Search Procedure (GRASP). The local search implementation was made in a Graphics Processing Unit (GPU) architecture in order to explore the massive number of computing cores to simultaneously explore neighbor solutions, while the GRASP was implemented exploring the natural parallelism of a multi-core CPU. The computational results were compared to state-of-the-art results in literature and indicate promising research directions for the design of novel search algorithms in high performance architectures.