“Inteligência Artificial: A Nova Fronteira da Ciência Brasileira”
19 a 24 de outubro de 2020
Trabalho 13700
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Ciência da computação |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Gabriel de Paula Félix |
| Orientador | JOSE ELIAS CLAUDIO ARROYO |
| Título | Otimização Combinatória Aplicada em Problemas de Programação da Produção e Transporte |
| Resumo | Neste projeto foi estudado o problema integrado de sequenciamento de tarefas em uma máquina e o roteamento de veículos com frota heterogênea. Neste problema, um conjunto de tarefas deve ser processado na máquina disponível numa fábrica e, utilizando um conjunto de veículos, as tarefas processadas devem ser entregues aos respetivos clientes. As tarefa possuem prazos de entregas. O objetivo do problema é determinar o sequenciamento das tarefas na máquina e as rotas dos veículos utilizados para fazer as entregas, de tal forma que seja minimizada a soma do atraso total ponderado das tarefas, o custo total dos veículos utilizados e o tempo total das viagens realizadas. Utilizando modelos convencionais de programação linear inteira, o tempo de execução requerido torna inviável encontrar soluções otimizadas para o problema a medida em que o número de tarefas/clientes aumenta. Nesta iniciação científica, é proposta uma nova versão do problema diferente da literatura em que: as tarefas possuem tamanhos distintos e os veículos fazem parte de uma frota heterogênea e limitada. Para resolver o problema, inicialmente é proposto um modelo de programação linear inteira. Assim, para instâncias de pequeno porte foi possível encontrar soluções-base para o problema por meio do software de otimização CPLEX. Em seguida, motivado pela complexidade computacional do problema, são propostos dois algoritmos heurísticos híbridos baseados nas meta-heurísticas Iterated Local Search (ILS) e Random Variable Neighborhood Descent (RVND). Por se tratar de um problema novo, para testar a eficiência dos algoritmos, foram geradas instâncias aleatórias de pequeno e grande porte com até 100 tarefas/clientes, seguindo parâmetros da literatura. Desenvolvidos na linguagem C++11, os algoritmos visam executar os conjuntos de instâncias de forma rápida e utilizando estruturas de dados eficientes para atingir este objetivo. Após sua implementação, os algoritmos passaram por uma calibragem de parâmetros e foram analisadas utilizando testes estatísticos. Os desempenhos dos algoritmos heurísticos propostos são avaliados e comparados através de experimentos computacionais e validados pelo Teste de Tukey. Os resultados mostram que uma das heurísticas propostas possui um desempenho de destaque quando comparada a um Algoritmo Genético da literatura e ao solver CPLEX, além de apresentar um tempo de execução rápido. Em projetos futuros, é interessante estudar o comportamento das heurísticas e outras técnicas de solução para o caso de uma fábrica que possua um ambiente com máquinas paralelas. |
| Palavras-chave | Otimização, scheduling, roteamento de veículos |
| Forma de apresentação..... | Vídeo |
| Link para apresentação | Vídeo |
|---|