Made available in DSpace on 2015-03-03T15:48:41Z (GMT). No. of bitstreams: 1 MatheusSM_TESE.pdf: 3657538 bytes, checksum: 05bf71663b044728a1e70b6db57b834e (MD5) Previous issue date: 2014-03-21 / This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting Traveling Car Renter Problem. In this problem, a set of vertices, each associated with a bonus, and a set of vehicles are given. The objective is to determine a cycle that visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the tour that can be traveled with different vehicles. A mathematical formulation is presented and implemented in a solver to produce results for sixty-two instances. The proposed problem is also subject of an experimental study based on the algorithmic application of four metaheuristics representing the best adaptations of the state of the art of the heuristic programming.We also provide new local search operators which exploit the neighborhoods of the problem, construction procedures and adjustments, created specifically for the addressed problem. Comparative computational experiments and performance tests are performed on a sample of 80 instances, aiming to offer a competitive algorithm to the problem. We conclude that memetic algorithms, computational transgenetic and a hybrid evolutive algorithm are competitive in tests performed / Este trabalho apresenta uma nova variante do problema do Caixeiro Alugador ainda n?o descrita na literatura, denominada de Caixeiro Alugador com Coleta de Pr?mios. Neste problema s?o disponibilizados um conjunto de v?rtices, cada um com um b?nus associado e um conjunto de ve?culos. O objetivo do problema ? determinar um ciclo que visite alguns v?rtices coletando, pelo menos, um b?nus pr?-de nido e minimizando os custos de viagem atrav?s da rota, que pode ser feita com ve?culos de diferentes tipos. ? apresentada uma formula??o matem?tica e implementada em um solver produzindo resultados em sessenta e duas inst?ncias. O problema proposto tamb?m ? objeto de um estudo algor?tmico experimental baseado na aplica??o de quatro metaheur?sticas de solu??o, representando adapta??es do melhor do estado da arte em programa??o heur?stica. Nesse trabalho tamb?m apresentamos a constitui??o de novos operadores que exploram as vizinhan?as do problema, procedimentos construtivos e adapta??es, criados especifi camente para o problema abordado. Experimentos computacionais comparativos e testes de desempenho s?o realizados sobre uma amostra de 80 inst?ncias, visando oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se que algoritmos com abordagem mem?tica, transgen ?tica e evolucion?ria h?brida obtiveram resultados competitivos nos testes efetuados. Palavras-chave: Caixeiro Alugador com Coleta de Pr?mios. Metaheur?sticas. GRASP/VNS. Algoritmo Mem?tico. Transgen?tica Computacional. Computa??o Evolucion?ria