Sempre gostei de problemas complexos. Quanto mais desafiador, melhor. Inevitavelmente, me graduei em Matemática, e assim sendo, escutei mais de uma vez que eu era louco. Como cada louco possui suas manias, sempre gostei de programar. Um dos meus primeiros algoritmos foi aos 14 anos: um script em batch que controlava um estoque fictício. Lembro que as operações básicas eram a de cadastro, busca e exclusão de itens do estoque. Basicamente um CRUD arcaico, onde eu salvava os dados em arquivos .txt (tenso).
Os anos se passaram e após a graduação em Matemática, fiz o mestrado em Ciência da Computação, com ênfase em otimização combinatória. Curiosamente, meu tema de pesquisa envolvia depósitos, exatamente o mesmo cenário dos meus primeiros códigos. Acontece que agora, eu estava trabalhando com um problema real: a redução de custos em grandes armazéns.
Neste artigo vou apresentar o problema que tratei no último ano, o Joint Order Batching and Picking Routing Problem (JOBPRP, que em tradução livre, significa Problema de loteamento e coleta simultânea de pedidos). Na primeira seção, vou introduzir o problema de forma intuitiva; na segunda seção, apresentarei novas propostas de abordagens algorítmicas; na terceira seção, irei expor parte dos resultados obtidos; finalmente, na última seção, vamos conversar sobre possíveis implicações do uso das abordagens.
Um grande problema... Ou seriam dois?
Assim que decidi resolver desafios relacionados à logística em armazéns, me debrucei na literatura internacional em busca do estado da arte no meu tema de pesquisa. Os problemas mais recorrentes são os seguintes:
- Order picking problem (OPP, em tradução livre, problema de coleta de pedidos)
- Order batching problem (OBP, em tradução livre, problema de loteamento de pedidos)
- Joint Order Batching and Picking Routing Problem (JOBPRP, em tradução livre, problema de loteamento e coleta simultânea de pedidos)
Estes problemas estão inseridos no contexto de grandes armazéns, onde os produtos são armazenados em prateleiras, dispostas em corredores paralelos.
Dada uma lista de produtos (o pedido de um cliente) com suas respectivas localizações, o OPP visa minimizar a distância que um funcionário humano (ou robô) irá percorrer ao longo do depósito a partir da área de despacho, para coletar os itens destacados no pedido e entregá-los ao setor de empacotamento.
A redução da distância percorrida pelo coletador está diretamente relacionada à redução de custos em armazéns, afinal, quase 60% dos custos operacionais em grandes depósitos estão diretamente relacionados ao processo de coleta de pedidos. Assim, justifica-se a importância da abordagem deste problema.
Porém, precisamos analisar o contexto de forma mais ampla: todos os produtos possuem um determinado peso (massa, certo?!) e um volume. Na prática, os coletadores também possuem um determinado limite de capacidade. Então, ao invés de coletar cada pedido individualmente, por que não agrupar os pedidos, para que os produtos sejam coletados em lotes?
É exatamente sobre isso que trata o OBP. Dado um conjunto de pedidos, o problema visa agrupar os pedidos em lotes, respeitando limites de capacidade dos coletadores, de forma que tal agrupamento minimize a distância total percorrida na coleta dos produtos de todos os lotes.
Começou a ficar interessante, certo? Geralmente, o cálculo da distância das rotas no OBP é feito através de políticas de roteamento, visto que a análise principal é no impacto de cada configuração de lotes na função objetivo. Porém, a literatura já fornece evidências de que tratar o OBP em conjunto com o OPP é uma estratégia mais vantajosa no ponto de vista prático. E é assim que surge o JOBPRP: otimizamos de forma simultânea, tanto o loteamento dos pedidos, quanto o roteamento de coleta de seus produtos. Dessa forma, esperamos como solução do problema, uma configuração de pedidos em lotes, juntamente com um conjunto de rotas de coleta.
Na próxima seção, vou te mostrar as abordagens que propus ao JOBPRP na minha dissertação.
Abordagens algorítmicas
Ok, aposto que era aqui que você queria chegar, certo? Mas se você pulou o texto da seção anterior, recomendo fazer ao menos uma leitura rápida, para que entenda o contexto dos algoritmos que vou descrever a seguir. Tenha em mente que vou abstrair totalmente de aspectos técnicos por uma questão de espaço. Em breve, cada uma das abordagens presentes nessa seção terá um post dedicado.
Uma heurística com dois níveis de programação dinâmica
Essa heurística funciona através de duas fases de programação dinâmica (PD): em um primeiro momento, o algoritmo agrupa os pedidos em lotes através de um procedimento muito similar ao algoritmo de PD que resolve o problema da mochila. Ou seja, os lotes são gerados de forma que seus limites de capacidade fiquem o mais próximos do máximo o possível. Após isso, é realizado um filtro, onde determinamos quais locais do depósito devem ser visitados em cada rota de coleta. Finalmente, utilizamos outro algoritmo de programação dinâmica para computar a rota de coleta ótima para cada lote.
Apesar de ser uma ideia aparentemente simples, o resultado surpreendeu bastante: em centésimos de segundos, o algoritmo devolve uma solução válida para o problema, sendo mais veloz em comparação com algoritmos estado da arte (testando com as mesmas instâncias). Por outro lado, a função objetivo poderia melhorar, e assim, decidi partir para uma estratégia meta-heurística.
Um algoritmo genético de agrupamento
Uma das grandes motivações para se trabalhar com meta-heurísticas é a fuga dos temidos ótimos locais, através de técnicas específicas - daí, se dá um melhoramento das médias da função objetivo.
No momento, não entrarei no mérito de explicar a fundo o que é um algoritmo genético, porém, posso defini-lo informalmente como um conjunto de estratégias algorítmicas baseadas no processo evolutivo natural, que tem por objetivo otimizar problemas combinatórios complexos.
A principal ideia dessa meta-heurística é codificar uma possível solução de um problema particular em uma representação conhecida como cromossomo. Operações genéticas são realizadas sobre esta estrutura, a fim de que a função objetivo do problema-alvo seja otimizada, até que um critério de parada seja alcançado.
As operações genéticas podem ser sumarizadas em:
- Geração da população inicial: um conjunto de soluções iniciais (cromossomos) é criado de forma aleatória ou através de estratégias heurísticas. Este conjunto de soluções iniciais, compõe o que chamamos de população inicial
- Avaliação: as soluções são avaliadas de acordo com o seu fitness, ou seja, o quão aptas estão para satisfazerem o problema. É frequente atrelar o fitness ao valor objetivo da função que está sendo otimizada
- Crossover (cruzamento): geralmente, o conjunto de pais é pareado de forma aleatória, são cruzados e geram um filho, que possui características gênicas de ambos os pais. O conjunto de filhos é denominado descendência
- Mutação: os filhos gerados têm chances de sofrerem uma mutação. Mutações são fatores externos ao cruzamento, que podem influenciar na conformação do novo cromossomo. Essa etapa é fundamental para garantir variabilidade genética, proporcionando fuga de ótimos locais
Além das operações citadas acima, ainda há a seleção parental e a substituição da nova população (replacement). Durante todos estes processos, o indivíduo com melhor fitness é indicado como a solução do problema.
Agora, que você já foi introduzido ao conceito de algoritmos genéticos, vou explicar algumas características especiais da implementação que utilizei para resolver o JOBPRP! Lembra que ali em cima falei que uma etapa importante de um algoritmo genético é "codificar uma possível solução de um problema particular em uma representação conhecida como cromossomo"? Pois é, podemos representar uma solução do problema de várias formas. Eu utilizei a técnica de agrupamento, visto que este tipo de codificação reduz soluções simétricas e em consequência, melhora a performance geral do algoritmo.
Para gerar a solução inicial, criei uma heurística especial, que de forma resumida, funciona agrupando pedidos mais similares (ou seja, aqueles que tem produtos mais próximos para serem coletados) a partir de uma escolha de pedido aleatória. A grande sacada desta heurística é o fato de que o valor objetivo da solução inicial já fica bem pequeno, porque o próprio algoritmo já se encarrega de agrupar os pedidos de acordo com um grau de similaridade, então as distâncias percorridas em cada lote se torna menor.
Outra característica interessante adotada durante o design dessa meta-heurística, foi o procedimento de crossover, que utiliza de uma técnica de transmissão gênica controlada. Não entrarei nos pormenores em relação à isso, mas entenda que essa abordagem permite a criação de uma solução filha de alta qualidade, herdando as características mais interessantes de cada pai. Por si só, isso já acelera a convergência da solução.
Após implementar o código todo e rodar os experimentos (com 30 seeds diferentes para cada instância), ficamos muito satisfeitos com o resultado final: apesar de um tempo de execução um pouco maior, conseguimos melhores funções objetivo que a literatura, o que implica em uma boa redução de custos!
Resultados
Testamos as abordagens em um popular dataset, utilizado em problemas combinatórios envolvendo depósitos. São 64 instâncias divididas em quatro grandes grupos: ABC1, ABC2 (os itens do depósito com maior rotatividade, ficam dispostos mais próximos da área de despacho), RAN1 e RAN2 (os itens são dispostos aleatoriamente pelo depósito).
As instâncias de cada grupo são conformadas a partir da combinação entre número de pedidos (40, 60, 80, 100) e limite total de capacidade de cada lote (30, 45, 60, 76).
Os gráficos acima indicam um comparativo da função objetivo entre a proposta heurística (2-level-DP-JOBPRP), meta-heurística (GGACGT-JOBPRP) e estudo estado da arte (MS-VNS, que tratava apenas o OBP, utilizando uma política de roteamento S-Shape).
Os resultados evidenciaram que o GGACGT-JOBPRP promoveu uma diminuição média de 3.1% na função objetivo em relação ao MS-VNS. Para cada uma das 64 instâncias, levamos em consideração o valor médio entre 30 replicatas com seeds diferentes, garantindo fidelidade ao teste. A média do desvio padrão entre todas as instâncias foi menor do que 0.5%, conferindo estabilidade ao modelo. Além disso, formulamos um programa linear inteiro para o problema (mais detalhes serão apresentados em posts futuros) e realizamos a implementação no solver Gurobi. Ao executar o solver, nossos resultados ficaram dentro da margem (gap) fornecida.
Todas as implementações foram realizadas em C++, inclusive a integração com o solver Gurobi. As automatizações de testes, gerações de resultados, gráficos e tabelas (LaTeX) foram efetuadas em Python. Os hiperparâmetros da meta-heurística foram determinados através do pacote iRace da linguagem R.
Discussão
Já imaginaram o custo de processamento computacional, caso os processos de loteamento e roteamento fossem feitos por força-bruta ou sem alguma boa estratégia de otimização? Pior ainda seria resolvê-los de forma aleatória ou de forma gulosa, o que aumentaria muito a distância percorrida pelos funcionários e o tempo total do processo.
Assim, neste breve artigo, introduzi o JOBPRP, juntamente com suas principais características e implicações. Também, apresentei duas novas possíveis soluções algorítmicas, uma delas sendo mais veloz que a literatura, enquanto a outra apresentou melhora na função objetivo do problema.
Em um contexto comercial onde os clientes estão cada vez mais exigentes em relação à condições de pagamento e redução do prazo de entrega, ao analisar os resultados experimentais, torna-se clara a relevância do porquê investir em pesquisa/desenvolvimento de novos métodos de otimização de problemas complexos, como o JOBPRP.
Além disso, otimizar o roteamento e o loteamento de pedidos implica em uma economia enorme de combustível, energia e alocação de pessoal. Ou seja, por um lado, a empresa melhora a experiência de compra dos clientes e aumenta seu faturamento. Por outro lado, ainda diminui os custos operacionais internos.
Já deu pra entender que investir em otimização é sinônimo de aumentar lucros, certo? Confie na matemática, confie nos cientistas de dados, confie na computação. Otimize!
Parte pública do projeto: Github
Top comments (0)