O Problema do Caixeiro Viajante com Alugueis de Carros: Um Estudo Algorítmico
O Problema do Caixeiro Viajante com Aluguel de Carros. O Problema do Caixeiro Alugador. Metaheurísticas. GRASP/VNS. Colônia de Formigas. Transgenética Computacional.
O Problema do Caixeiro Viajante com Aluguel de Carros – o Caixeiro Alugador (PCA) é uma variante ainda não descrita na literatura do clássico Problema do Caixeiro Viajante onde seu tour de visitas pode ser decomposto em caminhos contíguos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final mínimo, considerado o custo da rota adicionado ao custo de uma provável penalização paga em cada troca de veículos na rota, penalização devida ao retorno do carro descartado até a sua base. O presente trabalho descreve o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma formulação matemática é sugerida para um dos casos descritos. Uma análise geral da complexidade desse problema combinatório também é esboçada, visando justificar sua classificação na classe NP-difícil. Um banco de instâncias para o problema é sugerido, descrevendo-se a metodologia de sua constituição. O problema proposto também é objeto de um estudo algorítmico experimental baseado na aplicação de três metaheurísticas de solução. Com base nessas metáforas, são desenvolvidos três algoritmos associados e apresentados resultados computacionais do teste desses protótipos sobre uma amostra de 40 diferentes instâncias do banco criado. Tendo em vista o experimento, a presente proposta propõe duas linhas de melhoria para os algoritmos desenvolvidos ao longo de um cronograma que cobre dezoito meses de pesquisa. Ao final as conclusões da pesquisa são firmadas de forma a sustentar sua viabilidade tanto em tempo quanto no que diz respeito ao mérito.