O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

O Problema do Caixeiro Alugador (CaRS) é uma variante ainda não descrita na literatura do clássico Problema do Caixeiro Viajante onde o tradicional tour de visitas do caixeiro 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, considerando 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 cidade base. Sem perda para a generalidade do caso, os custos do aluguel do carro podem ser considerados embutidos nos custos da rota do carro. O presente trabalho introduz o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma análise geral da complexidade desse problema combinatório é descrita, visando justificar sua classificação na classe NP-difícil. Um banco de instâncias para o problema é apresentado, 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 seis metaheurísticas de solução, representando adaptações do melhor do estado da arte em programação heurística. Novas vizinhanças, procedimentos construtivos, operadores de busca, agentes evolucionários, cooperação por multiferomônios, são criados para o caso. Experimentos computacionais comparativos e testes de desempenho são realizados sobre uma amostra de 60 instâncias, visando oferecer um algoritmo de solução competitivo para o problema. Conclui-se pela vantagem do algoritmo transgenético em todos os conjuntos de instâncias