MODELO MATEMÁTICO E ALGORITMO MEMÉTICO PARA UMA VARIANTE DO PROBLEMA DO CAIXEIRO ALUGADOR

O Problema do Caixeiro Alugador ou The Traveling Car Renter Problem (CaRS) é uma generalização do Problema do Caixeiro Viajante (PCV) onde o percurso pode ser realizado utilizando diferentes carros alugados, também caracterizado como NP-Difícil. Todos os trabalhos relatados na literatura abordaram o problema sob a mesma ótica, onde o mesmo carro não pode ser alugado mais de uma vez, o carro alugado pode ser devolvido em qualquer cidade e existe uma cidade pré-definida para o início e final do percurso, denominada cidade base. Este artigo analisa o problema através da modificação destas características. O modelo matemático do problema é ajustado para considerar essa variação e é implementado em um solver, produzindo resultados para cinquenta e oito instâncias do problema. Um algoritmo memético é proposto, com buscas locais adequadas à variação do problema. O desempenho computacional do algoritmo memético proposto é comparado com a performance do solver.