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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/23382 |
| Date | 17 February 2017 |
| Creators | Bastos, Ranms?s Emanuel Martins |
| Contributors | 25841025953, http://lattes.cnpq.br/1371199678541174, Gouvea, Elizabeth Ferreira, 81652011749, http://lattes.cnpq.br/2888641121265608, Cabral, Luc?dio dos Anjos Formiga, 37383388372, http://lattes.cnpq.br/6699185881827288, Menezes, Matheus da Silva, 03329300418, http://lattes.cnpq.br/7790866637385232, Maia, Silvia Maria Diniz Monteiro, 01397968435, http://lattes.cnpq.br/1498104590221901, Goldbarg, Marco Cesar |
| Publisher | PROGRAMA DE P?S-GRADUA??O EM SISTEMAS E COMPUTA??O, UFRN, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds