Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-21T19:17:51Z
No. of bitstreams: 2
THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:10:55Z (GMT) No. of bitstreams: 2
THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:10:55Z (GMT). No. of bitstreams: 2
THIAGO AUGUSTO SOARES MASUTTI.pdf: 2397295 bytes, checksum: 601ae7fc072d419958ea8f13ddff366e (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016-08-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Fundo Mackenzie de Pesquisa / Combinatorial optimization problems are widely studied in the literature. On the one hand, their
challenging characteristics, such as the constraints and number of potential solutions, inspire
their use to test new solution techniques. On the other hand, the practical application of these
problems provides support on daily tasks of people and companies. Vehicle routing problems
constitute a well-known class of combinatorial optimization problems, from which the
Traveling Salesman Problem (TSP) is one of the most elementary problems. Despite its
simplicity, the difficulty in finding its exact solution and its direct application in practical
problems in multiple areas make it one of the most studied problems in the literature.
Algorithms inspired by biological phenomena are being successfully applied to optimization
problems, mainly combinatorial optimization problems. Those inspired by the collective
behavior of insects produce good results for solving such problems. This work proposes the
VRoptBees, a framework inspired by honeybee behavior to tackle vehicle routing problems.
Together with the framework, two examples of implementation are described, one to solve the
TSP and the other to solve the Capacitated Vehicle Routing Problem (CVRP). Tests were
conducted with benchmark instances from the literature, on which the implementation for the
TSP presented the third best results in a comparison with other bee-inspired algorithms. / Problemas de otimização combinatória são largamente estudados na literatura. De um lado, suas
características desafiadoras, como o número de restrições e possíveis soluções, inspiram seu
uso para testar novas técnicas de solução. Por outro lado, a aplicação prática desses problemas
auxilia no dia a dia de pessoas e empresas. Os problemas de roteamento de veículos constituem
uma classe muito conhecida da otimização combinatória, tendo o Problema de Caixeiro
Viajante (PCV) como um dos mais elementares. Apesar de sua simplicidade, a dificuldade em
encontrar uma solução exata e sua direta aplicação prática em diversas áreas o faz um dos
problemas mais estudados na literatura. Algoritmos inspirados em fenômenos naturais têm sido
utilizados com sucesso em problemas de otimização, principalmente de natureza combinatória.
Aqueles inspirados no comportamento coletivo de insetos apresentam bons resultados para
esses problemas. Nesse trabalho é proposto um framework inspirado no comportamento de
abelhas para a solução de problemas de roteamento de veículos, chamado de VRoptBees. Junto
ao framework, dois exemplos de implementações são propostos, um para a solução do PCV e
outro para o Problema de Roteamento de Veículos Capacitados (PRVC). Testes foram feitos
com instâncias de benchmark comumente utilizadas na literatura, com a implementação ao PCV
apresentando o terceiro melhor resultado entre os algoritmos inspirados em abelhas.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.mackenzie.br:tede/3123 |
| Date | 10 August 2016 |
| Creators | Masutti, Thiago Augusto Soares |
| Contributors | Silva, Leandro Nunes de Castro, Vallim Filho, Arnaldo Rabello de Aguiar, Coelho, Guilherme Palermo |
| Publisher | Universidade Presbiteriana Mackenzie, Engenharia Elétrica, UPM, Brasil, Escola de Engenharia Mackenzie (EE) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações do Mackenzie, instname:Universidade Presbiteriana Mackenzie, instacron:MACKENZIE |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
Page generated in 0.0025 seconds