Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903368 | Electronic Notes in Discrete Mathematics | 2018 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rodolfo Pereira Araujo, Eyder Rios, Igor Machado Coelho, Leandro A.J. Marzulo, Maria Clicia Castro,