Hibridização de Meta-Heurísticas com Métodos Baseados em Programação Linear para o Problema do Caixeiro Alugador
Meta-heurísticas híbridas, programação linear, problema do caixeiro viajante com aluguel de carros, algoritmos científicos, computação evolucionária, busca em vizinhança variável, busca local adaptativa.
O Problema do Caixeiro Viajante com Aluguel de Carros, ou simplesmente Problema do Caixeiro Alugador (PCA), é uma generalização do clássico Problema do Caixeiro Viajante (PCV) onde seu tour de visitas pode ser decomposto em caminhos contíguos que podem ser percorridos com diferentes carros alugados. O objetivo é determinar o circuito hamiltoniano que resulte em um custo final mínimo, considerando a penalização paga em cada troca de veículos no tour. A penalização é o custo de retornar o carro até a cidade onde foi alugado. O PCA está classificado como um problema NP-difícil. O presente trabalho estuda a variante mais usada na literatura do PCA que é: completo, total, irrestrito, sem repetição, livre e simétrico. O foco da pesquisa são os procedimentos híbridos que combinam meta-heurísticas e métodos baseados na Programação Linear. São hibridizados: algoritmos científicos (ScA), algoritmos evolucionários (EA), busca em vizinhança variável (VND), busca local adaptativa (ALSP) e uma nova variante da ALSP chamada busca local adaptativa iterativa (IALSP). As seguintes técnicas são propostas para lidar com o PCA: ScA+ALSP, EA+IALSP, ScA+IALSP e ScA+VND+IALSP. É proposto um modelo de programação inteira mista para o PCA o qual é usado no ALSP e no IALSP. Testes não paramétricos são usados para comparar os algoritmos em um conjunto de instâncias da literatura.