Abordagens heurísticas para tratar o problema do Caixeiro Viajante Preto e Branco

Abstract

O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema.

The Black and White Traveling Salesman Problem (TSP-BW) is a generalization of the Travelling Salesman Problem (TSP), set on a graph where the vertices are classified as black or white. As in the classical PCV, a solution of the TSP-BW is a Hamiltonian cycle of minimal cost. However, two additional constraints are considered. While the cardinality constraint limits the number of white vertices between two consecutive black vertices, the length constraint restricts the maximum distance therebetween. Applications of TSP-BW can be observed in aircraft scheduling and telecommunications network settings. The purpose of this study is to analyze different heuristic strategies applied to TSP-BW. Literature constructive heuristics have been improved and a new strategy for building the solution was presented. In this context it used methods such as Lin Kernighan and Inserção Específica de Brancos. Also, it has been proposed heuristic approaches based on metaheuristics GRASP, VND, ILS and SA. Several computational experiments were performed to compare effectiveness of approa- ches. The results ensure the applicability of the proposed algorithms to the problem.