Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/23716| Título: | Uso do Ant Colony Optimization como solução para o problema de discagem para caronas |
| Título(s) alternativo(s): | Using Ant Colony Optimization as a solution to the carpool dialing problem |
| Autor(es): | Heimoski, Ricardo |
| Orientador(es): | Gonçalves, Marcelo Mikosz |
| Palavras-chave: | Formigas Programação heurística Sistemas de controle inteligente Árvores (Teoria dos grafos) Algorítmos computacionais Ants Heuristic programming Intelligent control systems Trees (Graph theory) Computer algorithms |
| Data do documento: | 6-Dez-2019 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | HEIMOSKI, Ricardo. Uso do Ant Colony Optimization como solução para o problema de discagem para caronas. 2019. Trabalho de Conclusão de Curso (Bacharelado em Sistemas da Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2019. |
| Resumo: | Este trabalho apresenta uma solução para um modelo do problema de discagem para caronas através do uso da meta-heurística baseada no comportamento das formigas, conhecida como Ant Colony Optimization ou ACO. Sabendo-se que vários algoritmos baseados em comportamentos da natureza são utilizados para resolução de problemas em grafos, e que problemas de locomoção urbana podem ser modelados como problemas em grafos, percebeu-se a possibilidade da utilização de uma técnica dessas para a aproximação de um problema real relacionado à discagem de caronas. Foi utilizada uma abordagem extremamente elitista que somente atualiza com feromônio a melhor solução encontrada. Com a solução proposta foi possível resolver o modelo do problema proposto para instâncias de tamanhos variados, com melhorias na qualidade e velocidade da resposta com iterações sobre resultados anteriores seguindo a meta-heurística. Os resultados mostram a importância da calibragem da parametrização a ser utilizada, pois impacta diretamente na qualidade das soluções e na velocidade das mesmas. Conclui-se que a meta-heurística de ACO pode ser utilizada para resolução desse tipo de problema e que trabalhos posteriores podem buscar otimizações sobre esse modelo de resolução. |
| Abstract: | This work proposes a solution for a model of the dial a ride problem through the use of the metaheuristic based on ant’s behavior, Ant Colony Optimization or ACO. From the observation that several algorithms based on behaviors found in nature are used to solve problems in graphs, and that problems of urban locomotion can be modeled as problems in graphs, the possibility of using such a technique to approximate a real problem was perceived. An extremely elitist approach was used, which only updates with pheromone the best solution found. With the proposed solution it was possible to solve the model problem for instances of varied sizes, with improvements in the quality and speed of the response with iterations on previous results following the metaheuristic. The results show how the calibration of the parameterization directly impacts the quality and speed of the solution. We concluded that the metaheuristic can be used to solve this type of problem and that later works look optimizations on this resolution model. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/23716 |
| Aparece nas coleções: | CT - Sistemas de Informação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| CT_COSIS_2019_2_08.pdf | 375,96 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.