Goldbarg, Elizabeth Ferreira GouveaRios, Brenner Humberto Ojeda2018-03-132018-03-132018-02-02RIOS, Brenner Humberto Ojeda. Hibridização de meta-heurísticas com métodos baseados em programação linear para o problema do caixeiro alugador. 2018. 100f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2018.https://repositorio.ufrn.br/jspui/handle/123456789/24822The 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.Acesso AbertoMeta-heurísticas híbridasProgramação linearProblema do caixeiro viajante com aluguel de carrosAlgoritmos científicosComputação evolucionáriaBusca em vizinhança variávelBusca local adaptativamasterThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO