Aplicação de técnicas de otimização para o problema de seleção de pedidos ótima.

Abstract

Este trabalho aborda o Problema da Seleção de Pedidos Ótima (PSPO), um problema intralogístico de otimização da coleta de pedidos (order picking) e formação de lotes (order batching) em centros de distribuição de comércio eletrônico (e-commerce). Fundamentada no desafio do LVII Simpósio Brasileiro de Pesquisa Operacional (SBPO) em parceria com o Mercado Livre, a problemática modela-se como um problema de Programação Fracionária NP-Hard, cuja função objetivo visa a maximizar a produtividade da onda de coleta (wave), expressa pela razão entre itens selecionados e corredores ativados, sob restrições de capacidade e estoque. Para sua resolução, desenvolveu-se o OOSP-MetaSolver Framework na linguagem Rust, integrando avaliação incremental de saldos em complexidade temporal O(k), heurísticas construtivas orientadas a pedidos (Order-Centric) e a corredores (Aisle-Centric), exploração multi-vizinhança com o Variable Neighborhood Descent (VND) e as metaheurísticas GRASP Reativo (R-GRASP) e Otimização por Enxame de Partículas Binário Adaptativo Reativo (AR-BPSO) com paralelismo nativo. Conduziu-se avaliação experimental nas 50 instâncias oficiais do problema sob o limite fixo de 600 segundos. Os experimentos indicam que a razão de densidade pedidos/corredores (R = Ped./Cor.) orienta a eficácia construtiva: quando R ≥ 1, a consolidação por corredores apresenta desvio médio de 7,64% em menos de 0,05 segundos, margem reduzida para 1,71% pela busca local VND. Na avaliação global, o R-GRASP obteve desvio médio de 1,00% e convergiu para a melhor solução conhecida (Best Known Solution, BKS) em 46,00% das instâncias em 77,34 segundos. O AR-BPSO alcançou o menor desvio do estudo (0,79%) e convergiu para a BKS em 50,00% das instâncias em 247,57 segundos médios. No confronto com a literatura, as abordagens propostas apresentaram resultados superiores à heurística de referência do estado da arte em 9 instâncias (convergindo para a BKS em 5 delas) e encontraram soluções viáveis com desvios residuais inferiores aos de modelos exatos de Programação Linear Inteira onde estes não fecharam o gap dual. De modo geral, os resultados indicam a aplicabilidade do método para operações intralogísticas.