Heurísticas computacionais para o Problema do Comprador Viajante

Resumo

Este artigo trata sobre metodologias para indicar soluções para Problema do Comprador Viajante, uma generalização do clássico Problema do Caixeiro Viajante. Na determinação de possíveis métodos de resolução do problema proposto, foi realizada uma revisão sistemática da literatura a fim de identificar heurísticas computacionais capazes de resolvê-lo. Dentre os diferentes algoritmos heurísticos identificados, foram selecionados para esse trabalho combinações metodológicas que utilizam as técnicas, Algoritmo Genético com operadores de Busca Local e heurísticas de refinamento denominadas Tour Reduction e Path Relinking. Os testes computacionais realizados permitiram comparar a performance das combinações propostas e determinar as mais robustas, no que se refere ao custo de processamento de cada combinação, bem como à sua capacidade de convergência para soluções subótimas.