Um Algoritmo Evolutivo para o Problema do Caixeiro Alugador

Abstract

Este artigo aborda uma variante do Problema do Caixeiro Viajante chamado Problema do Caixeiro Alugador, onde um cliente deseja viajar entre as cidades usando um veı́culo alugado. Basicamente, o cliente tem duas opções quando chega em uma cidade: devolver o veı́culo para a cidade de onde alugou e alugar outro para continuar a viagem ou manter o mesmo veı́culo. Cada vez que um carro é entregue em uma cidade, uma taxa de retorno deve ser paga. O custo de deslocamento entre qualquer par de cidades também depende do carro escolhido. O objetivo é estabelecer um ciclo hamiltoniano minimizando os custos de deslocamento e as taxas de retorno. Um novo algoritmo evolutivo é proposto para este problema e comparado com a melhor técnica conhecida da literatura.