Use este identificador para citar ou linkar para este item:
https://repositorio.ufrn.br/handle/123456789/24203| Título: | O problema do caixeiro viajante com passageiros |
| Título(s) alternativo(s): | Traveling salesman with passengers problem |
| Autor(es): | Calheiros, Zailton Sachas Amorim |
| Orientador: | Goldbarg, Marco César |
| Palavras-chave: | Caixeiro viajante;Passageiros;Algoritmos evolucionários;Genético;Memético |
| Data do documento: | 31-Jul-2017 |
| Referência: | CALHEIROS, Zailton Sachas Amorim. O problema do caixeiro viajante com passageiros. 2017. 90f. 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. |
| Resumo: | 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. |
| Abstract: | 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. |
| URI: | https://repositorio.ufrn.br/jspui/handle/123456789/24203 |
| Aparece nas coleções: | PPGSC - Mestrado em Sistemas e Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| ZailtonSachasAmorimCalheiros_DISSERT.pdf | 976,43 kB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.