Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-06-02T19:19:17Z No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-06-05T19:52:50Z (GMT) No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Made available in DSpace on 2017-06-05T19:52:51Z (GMT). No. of bitstreams: 1 RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) Previous issue date: 2017-02-17 / O Problema do Caixeiro Viajante com Passageiros e Lota??o ? uma vers?o do PCV cl?ssico onde o caixeiro ? o motorista de um ve?culo que compartilha os custos de viagem com passageiros. Al?m de dividir os custos do percurso, o caixeiro pode se valer, tamb?m, dos descontos das high-occupancy vehicle lanes, que s?o faixas de tr?nsito que isentam ve?culos lotados do pagamento de ped?gio. A adi??o de passageiros ao PCV, um problema restrito ao roteamento, cria um vi?s colaborativo que ? intensificado pela considera??o das faixas especiais. Tal cen?rio confere ao problema estudado um aspecto ecol?gico, uma vez que seu estudo tem consequ?ncias diretas sobre o uso eficiente do espa?o urbano e a diminui??o da emiss?o de gases poluentes, contribuindo sobremaneira para o incremento da qualidade de vida. A pesquisa compreendeu desde a correla??o entre esse novo problema e outros constantes na literatura at? a concep??o de um conjunto de seiscentas inst?ncias artificiais e a cria??o de diversos m?todos de solu??o. Para a determina??o de ?timos, ? proposto um modelo matem?tico que suportou as solu??es por Programa??o Matem?tica e por Restri??es. Adicionalmente, ? apresentado um algoritmo branch-and-bound especificamente desenvolvido para o problema. Visando a busca por solu??es de qualidade em curto espa?o de tempo, s?o expostos cinco algoritmos experimentais com base nas abordagens heur?sticas Simulated Annealing, Variable Neighborhood Search, Coloniza??o de Abelhas e Algoritmos Gen?ticos. Diversos procedimentos auxiliares para constru??o de solu??es e execu??o de buscas locais s?o tamb?m expostos. Um experimento computacional ? realizado para compara??o entre os m?todos de solu??o. Uma amostra de cem casos teste ? utilizada para o processo estat?stico de ajuste de par?metros dos algoritmos heur?sticos, enquanto o restante das inst?ncias ? extensivamente abordado pelos m?todos. S?o determinados os ?timos para cento e cinquenta e cinco casos com tamanhos 10 e 20 cidades. Dentre os m?todos experimentais, cabe destacar a superioridade do algoritmo heur?stico que une as meta-heur?sticas Simulated Annealing e Variable Neighborhood Search. / The Traveling Salesman with Passengers and High Occupancy Problem is a version of the classic TSP where the salesman is the driver of a vehicle who shares travels? expenses with passengers. Besides shared expenses, the driver also benefits from discounts of the highoccupancy vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from tolls. The addition of passengers to the TSP, a routing-only problem, creates a sharing view which is intensified by the consideration of special lanes. This scenario grants to the problem an ecological feature, since its study have direct consequences for the efficient use of urban space and the greenhouse gas emissions reduction, greatly contributing for quality of life improvement. This work addresses the study of this novel combinatorial optimization problem, going from the relationship it draws with other ones in the literature until the conception of a six hundred set of artificial test cases and the creation of many solution methods. To find optimal solutions, a mathematical model is proposed. This model supported the search for exact solutions by Mathematical and Constraint Programming. Additionally, is presented a branchand- bound algorithm specifically developed for the problem. Aiming the search for good quality solutions in short time period, five experimental algorithms based on the heuristics approaches Simulated Annealing, Variable Neighborhood Search, Bees Colony and Genetic Algorithms are introduced. Several auxiliary procedures for solutions generations and local search execution are revealed as well. A computational experiment is fulfilled to comparison between the solution methods. A sample of a hundred test cases is used for the heuristics algorithms? parameter tuning statistical process, while the rest of them are extensively addressed by the methods. The optimal solution for a hundred and fifty five test cases with sizes of 10 and 20 cities are determined. Among the experimental methods, one has to highlight the advantage of the heuristic algorithm that unites the metaheuristics Simulated Annealing and Variable Neighborhood Search.