Meta-heurísticas hibridizadas com variações de busca local aplicadas ao problema do caixeiro viajante com coleta de prêmios.

Abstract

The Prize-Collecting Traveling Salesman Problem (PCTSP) is a variant of the traditional Traveling Salesman Problem (TSP). In PCTSP, the salesman traverses a Hamiltonian cycle within a subset of vertices and collects a prize at each visited vertex. The objective is to minimize the sum of the traveled distance and penalties associated with unvisited vertices, subject to collecting a minimum amount of prizes. PCTSP belongs to the NP-hard class and finds applications in both theoretical and practical scenarios, such as the production of steel sheets and strips. In recent years, research has demonstrated the potential of hybrid metaheuristics in finding high-quality solutions for NP-hard problems. Such techniques combine and exploit the best features of individual metaheuristics. The aim of this research is to develop hybrid metaheuristics for PCTSP. The focus is on hybridizing variations of local search with genetic algorithms and GRASP. Eight hybrid algorithms were developed, considering four local search variations: 2-opt, VNS, VND, and a combination of VNS-VND. The results obtained reveal significant insights into the performance and characteristics of hybrid metaheuristics, with particular emphasis on the memetic algorithm with VNS-VND, whose analysis suggests potential benefits in terms of solution quality and execution time.