Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/23382
Title: O problema do caixeiro viajante com passageiros e lotação
Other Titles: The traveling salesman with passengers and high occupancy problem
Authors: Bastos, Ranmsés Emanuel Martins
Keywords: Problema do caixeiro viajante;Problema ridesharing;Carpool;Metaheurísticas;High-occupancy vehicle lanes
Issue Date: 17-Feb-2017
Citation: BASTOS, Ranmsés Emanuel Martins. O problema do caixeiro viajante com passageiros e lotação. 2017. 139f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2017.
Portuguese Abstract: 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.
Abstract: 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.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/23382
Appears in Collections:PPGSC - Mestrado em Sistemas e Computação

Files in This Item:
File Description SizeFormat 
RanmsesEmanuelMartinsBastos_DISSERT.pdf3,46 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.