Abordagens heurísticas para tratar o problema do Caixeiro Viajante Preto e Branco - Cazetta, Paôla Pinto (2015)
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.