Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-11-01T21:17:49Z
No. of bitstreams: 1
ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-11-07T21:20:44Z (GMT) No. of bitstreams: 1
ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5) / Made available in DSpace on 2017-11-07T21:20:44Z (GMT). No. of bitstreams: 1
ZailtonSachasAmorimCalheiros_DISSERT.pdf: 970322 bytes, checksum: b3f4c21bcb05d3c25bba593777a5b94a (MD5)
Previous issue date: 2017-07-31 / Este trabalho apresenta um modelo de compartilhamento de assentos veicular de modo
a reduzir os custos de viagem de motoristas e passageiros, contribuindo de maneira
significativa ao meio ambiente e ? sociedade. O problema tamb?m ? descrito atrav?s
de um modelo de programa??o linear e s?o discutidas algumas variantes de um subproblema
importante para resolu??o do modelo proposto. Al?m disso, algumas abordagens
computacionais s?o implementadas, compostas de algoritmos evolucion?rios (gen?tico e
mem?tico) e construtivos (formigas e GRASP). Al?m da adapta??o de algoritmos j? existes
para o problema do caixeiro viajante tradicional como o algoritmo de Lin-Kernighan. Ap?s
a realiza??o de experimentos, o algoritmo baseado em formiga revela-se promissor para
inst?ncias assim?tricas enquanto que o algoritmo de Lin-Kernighan leva vantagem pela
sua robustez atrav?s da implementa??o de Helsgaun que desempenha bons resultados para
inst?ncias sim?tricas. / This thesis presents a vehicle seat sharing model in order to reduce travel costs for drivers
and passengers, contributing significantly to the environment and society. The problem
is also described by a linear programming model and it is discussed in some variants of
an important subproblem for solving the main problem. Besides, some computational approaches
are implemented, composed by evolutionary (genetic and memetic) e constructive
(ant optimization) algorithms. In addition to the adaptation of already existing algorithms
for the travaling salesman problem as the Lin-Kernighan algorithm. After performing
experiments, ant-based algorithms prove itself promising for asymmetric instances while
the Lin-Kernighan algorithm takes advantage of its robustness through the implementation
of Helsgaun and has a good performance for symmetric instances.
Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24203 |
Date | 31 July 2017 |
Creators | Calheiros, Zailton Sachas Amorim |
Contributors | 25841025953, Gouvea, Elizabeth Ferreira, 81652011749, Maia, Silvia Maria Diniz Monteiro, 01397968435, Menezes, Matheus da Silva, 03329300418, Goldbarg, Marco C?sar |
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.0023 seconds