Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-03-02T23:39:14Z No. of bitstreams: 1 BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-03-13T18:44:23Z (GMT) No. of bitstreams: 1 BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5) / Made available in DSpace on 2018-03-13T18:44:23Z (GMT). No. of bitstreams: 1 BrennerHumbertoOjedaRios_DISSERT.pdf: 2438215 bytes, checksum: 3e559bfdaf797a4b9164e336ebd13429 (MD5) Previous issue date: 2018-02-02 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O Problema do Caixeiro Viajante com Aluguel de Carros, ou simplesmente Problema do Caixeiro Alugador (PCA), ? uma generaliza??o do cl?ssico Problema do Caixeiro Viajante (PCV) onde seu tour de visitas pode ser decomposto em caminhos cont?guos que podem ser percorridos com diferentes carros alugados. O objetivo ? determinar o circuito hamiltoniano que resulte em um custo final m?nimo, considerando a penaliza??o paga em cada troca de ve?culos no tour. A penaliza??o ? o custo de retornar o carro at? a cidade onde foi alugado. O PCA est? classificado como um problema NP-dif?cil. O presente trabalho estuda a variante mais usada na literatura do PCA que ?: completo, total, irrestrito, sem repeti??o, livre e sim?trico. O foco da pesquisa s?o os procedimentos h?bridos que combinam meta-heur?sticas e m?todos baseados na Programa??o Linear. S?o hibridizados: algoritmos cient?ficos (ScA), descida em vizinhan?a vari?vel (VND), busca local adaptativa (ALSP) e uma nova variante do ALSP chamada busca local adaptativa iterativa (IALSP). As seguintes t?cnicas s?o propostas para lidar com o PCA: ScA+ALSP, ScA+IALSP e ScA+VND+IALSP. ? proposto um modelo de programa??o inteira mista para o PCA o qual ? usado no ALSP e no IALSP. Testes n?o param?tricos s?o usados para comparar os algoritmos em um conjunto de inst?ncias da literatura. / The Traveling Car Renter Salesman Problem, or simply Traveling Car Renter Problem (CaRS), is a generalization of the Traveling Salesman Problem (TSP) where the tour can be decomposed into contiguous paths that are traveled by different rented cars. The objective is to construct a minimal cost Hamiltonian circuit, considering the penalty paid for changing cars in the tour. This penalty is the cost of returning a car to the city where it was rented. CaRS is classified as an NP-hard problem. This work studies the CaRS version classified as: complete, total, unrestricted, with no repetition, free and symmetric. This research is focused on hybrid procedures that combine metaheuristics and methods based on Linear Programming (LP). The following methods were investigated: scientific algorithms (ScA), variable neighborhood descent (VND), adaptive local search (ASLP) and a new variant of ALSP called iterated adaptive local search (IALSP). The following techniques are proposed to deal with CaRS: ScA+ALSP, ScA+IALSP and ScA+VND+IALSP. A mixed integer programming model is proposed for CaRS which was used in the ALSP and IALSP. Non-parametric tests were used to compare the algorithms within a set of instances from the literature.