Generate-and-Solve aplicada ao Problema de Seleção de Pedidos

- 325814
Trabalho completo (Oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Neste trabalho, abordamos o Problema de Seleção de Pedidos (PSP), um problema de Otimização Combinatória proposto pelo Mercado Livre durante o primeiro desafio de otimização realizado pela Sociedade Brasileira de Pesquisa Operacional (SOBRAPO). Em suma, o objetivo é maximizar a razão da quantidade de itens coletados por quantidade de corredores selecionados, respeitando limites mínimo e máximo de itens. Aplicamos o framework híbrido Generate-and-Solve, que combina um Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA) como gerador de instâncias reduzidas e um modelo de Programação Linear Inteira para resolvê-las. Nossa abordagem explora subconjuntos promissores de corredores para trabalhar com um modelo linear, reduzir a complexidade de resolução do problema e garantir soluções de alta qualidade. Experimentos computacionais com vinte instâncias mostraram que a heurística convergiu para a solução ótima da abordagem exata em quatro casos e que, nos demais casos, ambos apresentaram resultados próximos, demonstrando assim a eficácia do método proposto. 

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade de Fortaleza
  • 2 Universidade Federal de Pernambuco
Eixo Temático
  • 12. MH – Metaheurísticas
Palavras-chave
Programação Inteira
Algoritmos híbridos
Problema de Seleção de Pedidos