Matemática discreta na implementação de um sistema WMS: agrupamento de lotes de mercadorias em um armazém

O artigo descreve como implementar WMSNeste projeto, nos deparamos com a necessidade de resolver um problema de agrupamento não padronizado e descreveremos os algoritmos que utilizamos. Compartilharemos como aplicamos uma abordagem sistemática e científica para solucionar o problema, os desafios que encontramos e as lições que aprendemos.

Esta publicação inicia uma série de artigos nos quais compartilhamos nossa experiência bem-sucedida na implementação de algoritmos de otimização em processos de armazém. O objetivo desta série é apresentar ao público os tipos de desafios de otimização que surgem em praticamente qualquer armazém de médio e grande porte, bem como compartilhar nossa experiência na resolução desses desafios e as dificuldades encontradas ao longo do caminho. Esses artigos serão úteis para profissionais que atuam no setor de logística de armazéns, implementando algoritmos de otimização. WMS-sistemas, bem como programadores interessados ​​nas aplicações da matemática nos negócios e na otimização de processos empresariais.

Gargalo nos processos

Em 2018, concluímos um projeto de implantação WMS-sistemas no armazém da empresa "Trading House "LD" em Chelyabinsk. O produto "1C-Logistics: Warehouse Management 3" foi implementado em 20 estações de trabalho: operadores. WMS, lojistas, motoristas de empilhadeiras. O armazém médio é de cerca de 4 mil m2, o número de células é de 5000 e o número de SKUs é de 4500. O armazém armazena válvulas esfera de produção própria em diversos tamanhos de 1 kg a 400 kg. O estoque no almoxarifado é armazenado em lotes, pois há necessidade de seleção da mercadoria de acordo com o FIFO.

Ao projetar sistemas de automação de armazéns, deparamo-nos com o problema recorrente do armazenamento subótimo de estoque. A natureza específica do armazenamento e empilhamento por guindastes implica que cada compartimento de armazenamento individual só pode conter itens de um único lote. Os produtos chegam ao armazém diariamente, e cada chegada corresponde a um lote separado. Consequentemente, ao longo de um mês de operação do armazém, são criados 30 lotes distintos, cada um dos quais deveria ser armazenado em um compartimento separado. Os produtos são frequentemente coletados individualmente, em vez de em paletes completos. Como resultado, em muitos compartimentos na área de coleta individual, observa-se a seguinte situação: um compartimento com volume superior a 1 m³ contém vários guindastes, cada um ocupando menos de 5 a 10% do volume do compartimento.

Figura 1. Foto de vários itens em uma célula

A utilização subótima da capacidade do armazém é evidente. Para ilustrar a dimensão do problema, posso apresentar alguns números: em média, existem entre 100 e 300 desses compartimentos com capacidade superior a 1 metro cúbico contendo um estoque "ínfimo" em diferentes momentos da operação do armazém. Como o armazém é relativamente pequeno, esse fator se torna um gargalo durante os períodos de pico, atrasando significativamente os processos.

Ideia de solução de problema

Surgiu então uma ideia: combinar lotes de resíduos com datas mais próximas em um único lote e colocar esses resíduos de um lote unificado de forma compacta em uma célula, ou em várias, caso não haja espaço suficiente em uma só para acomodar o número total de resíduos.

Figura 2. Esquema para compactar resíduos em células

Isso permite uma redução significativa na quantidade de espaço de armazém necessário para novas mercadorias. Em situações em que a capacidade do armazém está sobrecarregada, essa medida é essencial; caso contrário, pode simplesmente não haver espaço livre suficiente para acomodar novas mercadorias, levando a uma paralisação nos processos de armazenamento e reabastecimento. Anteriormente, antes da implementação WMSAnteriormente, essa operação era realizada manualmente, o que era ineficiente, pois a busca por balanças adequadas nos silos consumia muito tempo. Agora, com a implementação de um sistema WMS, decidimos automatizar, agilizar e tornar o processo inteligente.

O processo de resolução de tal problema é dividido em 2 etapas:

• Na primeira etapa, identificamos grupos de partidos com datas próximas que são comprimidos;
• na segunda etapa, para cada grupo de lotes calculamos a colocação mais compacta dos demais produtos nas células.

Neste artigo, vamos nos concentrar na primeira etapa do algoritmo e deixar a segunda etapa para o próximo artigo.

Procure um modelo matemático do problema

Antes de começarmos a escrever código e reinventar a roda, decidimos abordar este problema cientificamente, ou seja: formulá-lo matematicamente, reduzi-lo a um problema de otimização discreta bem conhecido e usar algoritmos existentes eficazes para resolvê-lo, ou tomar esses algoritmos existentes como base e modificá-los para se adequarem às especificidades do problema prático a ser resolvido.

Uma vez que, a partir da formulação do problema, fica claro que estamos lidando com conjuntos, formularemos esse problema em termos da teoria dos conjuntos.

Deixar – o conjunto de todos os lotes de mercadorias restantes em um armazém. Deixe – uma constante dada de dias. Seja – um subconjunto de partes em que a diferença entre as datas de todos os pares de partes no subconjunto não excede uma constante É necessário encontrar o número mínimo de subconjuntos disjuntos. , de forma que todos os subconjuntos Juntos, eles dariam muito. .

Em outras palavras, precisamos encontrar grupos ou agrupamentos de partes semelhantes, onde o critério de similaridade é determinado por uma constante. Este problema nos lembra o conhecido problema de agrupamento. É importante notar que o problema em questão difere do problema de agrupamento, pois o nosso problema possui uma condição estritamente definida para o critério de similaridade dos elementos do cluster, determinada por uma constante. , mas no problema de agrupamento não existe tal condição. O enunciado do problema de agrupamento e informações sobre este problema podem ser encontrados aqui.

Assim, conseguimos formular o problema e encontramos um problema clássico com uma formulação semelhante. Agora precisamos considerar algoritmos consagrados para resolvê-lo, a fim de não reinventar a roda, mas sim adotar as melhores práticas e aplicá-las. Para resolver o problema de agrupamento, consideramos os algoritmos mais populares, a saber: -significa, -means, um algoritmo de extração de componentes conectados, e um algoritmo de árvore geradora mínima. Descrições e análises desses algoritmos podem ser encontradas em aqui.

Para resolver nosso problema, algoritmos de agrupamento -significa e As médias não são aplicáveis, pois o número de clusters nunca é conhecido antecipadamente. e tais algoritmos não levam em consideração a restrição de dias constantes. Inicialmente, esses algoritmos foram descartados.
A extração de componentes conectados e os algoritmos de árvore geradora mínima são mais adequados para resolver nosso problema, mas verifica-se que não podem ser aplicados diretamente ao problema em questão e produzir uma boa solução. Para esclarecer isso, vamos considerar a lógica por trás desses algoritmos e como eles se aplicam ao nosso problema.

Vamos considerar o gráfico. , em que os vértices são um conjunto de partes e a aresta entre os vértices и tem um peso igual à diferença em dias entre os lotes и No algoritmo para extrair componentes conectados, um parâmetro de entrada é especificado. Onde e no gráfico Todas as arestas com peso superior ao recomendado são removidas. Apenas os pares de objetos mais próximos permanecem conectados. O objetivo do algoritmo é encontrar um desses valores. , em que o grafo se “desfará” em vários componentes conectados, onde as partes pertencentes a esses componentes satisfarão nosso critério de similaridade, determinado pela constante Os componentes resultantes são clusters.

O algoritmo da árvore geradora mínima primeiro constrói uma árvore no grafo. A árvore geradora mínima é utilizada para construir o grafo, removendo sequencialmente as arestas com os maiores pesos até que o grafo se "desfaça" em vários componentes conectados, onde as partes pertencentes a esses componentes também satisfazem nosso critério de similaridade. Os componentes resultantes serão os clusters.

Ao utilizar tais algoritmos para resolver o problema em questão, pode surgir uma situação como a da Figura 3.

Figura 3. Aplicação de algoritmos de agrupamento ao problema em questão.

Vamos supor que temos uma diferença constante de 20 dias entre os lotes. Gráfico A representação espacial foi utilizada para facilitar a percepção visual. Ambos os algoritmos produziram uma solução com três agrupamentos, que pode ser facilmente melhorada combinando os lotes colocados em agrupamentos separados! Claramente, tais algoritmos precisam ser refinados para o problema específico a ser resolvido, e sua aplicação em sua forma pura ao nosso problema produzirá resultados insatisfatórios.

Assim, antes de começarmos a escrever código para algoritmos de grafos modificados para nossa tarefa e reinventarmos a roda (em cujas silhuetas os contornos de rodas quadradas já eram discerníveis), decidimos, mais uma vez, abordar esse problema cientificamente, ou seja: tentar reduzi-lo a outro problema de otimização discreta, na esperança de que os algoritmos existentes para resolvê-lo pudessem ser aplicados sem modificação.

Outra busca por um problema clássico semelhante foi bem-sucedida! Encontramos um problema de otimização discreta cuja formulação é idêntica à nossa. Este problema acabou sendo problema de cobertura de conjuntoVamos formular o problema em relação à nossa situação específica.

Existe um conjunto finito e família todos os seus subconjuntos disjuntos de partes, de modo que a diferença nas datas para todos os pares de partes de cada subconjunto da família não excede uma constante Uma cobertura é uma família da potência mais baixa, cujos elementos pertencem , de modo que a união de conjuntos da família deve fornecer o conjunto de todas as partes .

Uma análise detalhada deste problema pode ser encontrada aqui и aqui. Outras aplicações práticas do problema de cobertura e suas modificações podem ser encontradas. aqui.

Algoritmo para resolver o problema

Definimos o modelo matemático para o problema a ser resolvido. Agora, vamos examinar o algoritmo para resolvê-lo. Subconjuntos da família Pode ser facilmente encontrado seguindo o procedimento abaixo.

1. Ordene as partes a partir do conjunto em ordem decrescente de suas datas.
2. Encontre as datas mínimas e máximas dos jogos.
3. Para cada dia Da data mínima à data máxima, encontre todas as partes cujas datas diferem de não mais que (portanto, o significado) É melhor escolher um número par.

A lógica do procedimento para formar uma família de conjuntos em Os dias são mostrados na Figura 4.

Figura 4. Formação de subconjuntos de partidos

Em tal procedimento, não é necessário que todos participem. Analise todos os outros lotes e verifique a diferença entre as datas ou em relação ao valor atual. Mova-se para a esquerda ou para a direita até encontrar um lote cuja data seja diferente de Por mais da metade do valor constante. Todos os elementos subsequentes, sejam eles à direita ou à esquerda, não nos interessarão, pois a diferença em dias só aumentará para eles, visto que os elementos na matriz foram inicialmente ordenados. Essa abordagem economizará um tempo considerável quando o número de lotes e a dispersão de suas datas forem significativamente maiores.

O problema de cobertura de conjuntos é -difícil, o que significa que não existe um algoritmo rápido (com tempo de execução igual a um polinômio nos dados de entrada) e exato para resolvê-lo. Portanto, um algoritmo guloso rápido foi escolhido para resolver o problema de cobertura de conjuntos. Embora não seja exato, ele apresenta as seguintes vantagens:

• Para problemas de pequena escala (que é precisamente o nosso caso), ele calcula soluções bastante próximas do ótimo. À medida que o tamanho do problema aumenta, a qualidade da solução deteriora, mas ainda de forma bastante lenta;
• Muito fácil de implementar;
• É rápido porque seu tempo de execução é estimado em .

O algoritmo guloso seleciona conjuntos com base na seguinte regra: em cada etapa, é selecionado um conjunto que cubra o número máximo de elementos não cobertos. Uma descrição detalhada do algoritmo e seu pseudocódigo podem ser encontrados [aqui]. aqui.

A precisão deste algoritmo guloso nos dados de teste do problema a ser resolvido não foi comparada com outros algoritmos bem conhecidos, como o algoritmo guloso probabilístico, o algoritmo da colônia de formigas, etc. Resultados comparativos desses algoritmos em dados aleatórios gerados podem ser encontrados. No trabalho.

Implementação e execução do algoritmo

Este algoritmo foi implementado na linguagem 1S e foi incluído em um processamento externo chamado "Compressão de Resíduos", que estava conectado a WMS-sistema. Não implementamos o algoritmo na linguagem C ++ e usá-lo a partir de um componente nativo externo, o que seria mais correto, visto que a velocidade do código em C + + várias vezes, e em alguns exemplos até dezenas de vezes, supera a velocidade de códigos semelhantes em 1SNa língua 1S O algoritmo foi implementado para economizar tempo de desenvolvimento e simplificar a depuração no ambiente de produção do cliente. O resultado do algoritmo é mostrado na Figura 5.

Figura 5. Processamento por “compressão” de resíduos

A Figura 5 mostra que os saldos de estoque atuais nas células de armazenamento do armazém especificado estão divididos em grupos, dentro dos quais as datas de lote diferem em no máximo 30 dias. Como o cliente fabrica e armazena válvulas de esfera metálicas no armazém, que têm um prazo de validade medido em anos, essa diferença de datas pode ser ignorada. Deve-se notar que esse tipo de processamento é atualmente utilizado sistematicamente na produção, e os operadores... WMS Confirmar a boa qualidade do agrupamento partidário.

Conclusões e continuação

A principal experiência que obtivemos ao resolver um problema prático como esse foi a confirmação da eficácia do paradigma da formulação matemática do problema. modelo matemático bem conhecido algoritmo bem conhecido Um algoritmo adaptado às especificidades do problema. A otimização discreta existe há mais de 300 anos e, durante esse tempo, as pessoas consideraram uma ampla gama de problemas e acumularam vasta experiência em resolvê-los. É melhor aproveitar essa experiência primeiro e só depois tentar reinventar a roda.

No próximo artigo, daremos continuidade à nossa discussão sobre algoritmos de otimização e abordaremos algo mais interessante e muito mais complexo: um algoritmo para a "compressão" ideal de resíduos celulares que utiliza dados de entrada provenientes de um algoritmo de agrupamento em lote.

Preparou o artigo
Roman Shangin, programador do departamento de projetos,
Primeira empresa BIT, Chelyabinsk

Fonte: habr.com