Otimização Linear – Parte II

No primeiro artigo (Otimização– Parte I), apresentámos o conceito de Otimização: o que é um problema de otimização, como se constrói um modelo de Otimização e como é que o mesmo pode ser implementado com recurso ao Google OR-Tools. Para ilustrar as diferentes etapas deste processo, criámos um cenário fictício baseado num problema típico de otimização: O Problema de Transporte.

A ideia deste artigo consiste em apresentar um caso de uso real e descrever como o mesmo pôde ser resolvido, construindo e implementando um modelo de optimização.

Caso de Uso Real: Como otimizar um armazém?

O cenário que nos foi apresentado tinha como objetivo dar resposta a um dos desafios típicos de qualquer armazém: otimizar o espaço disponível. O modo como os produtos estão distribuídos pelo armazém influencia o tempo de viagem gasto pelos colaboradores quando estes se dirigem às prateleiras para recolher os produtos e preparar uma encomenda solicitada por um cliente. Como tal, foi-nos solicitada uma solução que satisfizesse os seguintes requisitos:

1. Sugerir a melhor localização para um determinado produto recebido pelo armazém, de modo a minimizar o tempo de viagem gasto pelos colaboradores no acesso aos produtos, a partir do corredor principal (ponto de referência);

2. Redistribuir os produtos de forma a que aqueles que pertencem ao mesmo depositante ficassem em localizações próximas entre si.

Figura 1 – Planta simplificada do armazém.

A Figura 1 representa a planta simplificada do armazém. O corredor onde circulam as empilhadoras é o corredor principal e os quadrados representam as estantes vistas de cima, onde os produtos são armazenados. Se não considerarmos as alturas de cada estante, podemos afirmar, de forma simplificada, que as melhores localizações para qualquer produto correspondem às estantes mais próximas do corredor principal.

Como redistribuir os produtos pelo armazém?

A abordagem adotada na resolução do problema de Otimização do armazém passou por aproximá-lo ao típico Problema de Transporte. A solução passaria assim por propôr a melhor localização para um determinado produto tendo em conta os seguintes critérios:

• Rotação de stock do produto: prazo médio, em meses, necessário para converter o stock de um produto em encomendas. A rotação de stock é usada para calcular a frequência com a qual o produto é requisitado numa encomenda, fazendo o seu inverso (1/rotação). Usando a rotação de stock conseguimos decidir que produtos devem ocupar as melhores localizações: os produtos com mais saída e que permanecem, no armazém, por menos tempo, serão os candidatos a ocupar as melhores estantes do armazém, uma vez que o armazém recebe diferentes produtos de vários depositantes e nem todos cabem nas estantes próximas ao corredor principal.
• Tempo desde o corredor principal até à localização do produto: isto é, o tempo dispendido na recolha do produto desde o corredor principal do armazém até à estante onde se encontra armazenado o produto.
• Capacidade máxima de cada estante: quantidade de produtos que cabem numa estante. Tal, corresponde ao somatório da capacidade máxima de todas as suas prateleiras.
• Número de produtos a serem alocados no armazém: isto é, quantidade de produtos recebidos pelo armazém e que têm de ser arrumados.
• Afinidade entre produtos: alocar produtos do mesmo depositante em prateleiras próximas entre si.

Modelo de Otimização– Fórmula I [2]

Os critérios supracitados foram utilizados para construir o modelo de Otimização que, matematicamente, descreve o problema de Otimização do armazém. Para tal, foi necessário identificar as variáveis de decisão do problema, as suas restrições e a função objetivo a otimizar.

Variáveis de Decisão:

Xij = números de produtos i alocados a j

Restrições: 

1. Quantidade de cada tipo de produto a alocar no armazém: após a redistribuição dos produtos pelo armazém, o número total de produtos i alocados na estante j deverá ser igual à quantidade total de produtos i a arrumar no armazém.

Pi = números de produtos i a serem alocados

2. Quantidade máxima de produtos que podem ser alocados em cada estante: o número de produtos i atribuídos à estante j não deve ultrapassar a sua capacidade máxima de armazenamento.

Capj = capacidade de estante j.

3. Quantidade mínima de produtos: o número de produtos i a arrumar na estante j deverá ser um número inteiro positivo ou igual a zero.

Função Objetivo:

tj = tempo desde a estante j até ao corredor principal.

ri = rotação de stock do produto i.

Aj = conjunto de produtos alocados na estante j.

Rik = peso atribuido à relação entre os produtos i e k

A função objetivo é constituída por 3 somatórios. Com o primeiro somatório estamos a calcular o custo de alocar qualquer produto i na estante j. Esta função será usada para identificar como os produtos devem ser distribuídos pelas estantes, de forma a minimizar o tempo total desde as mesmas até ao corredor principal e, simultaneamente, garantir que os produtos com menor rotatividade ocupem as melhores localizações do armazém. O segundo e o terceiro somatório representam a afinidade entre 2 tipos de produtos [2]:

• Afinidade entre produtos alocados e não alocados (2º somatório): Atribuir um produto i a uma estante onde já se encontre alocado um produto j, sabendo que ambos pertencem ao mesmo depositante, conduz à atribuição de um “bónus”  caso ambos sejam arrumados na mesma estante, minimizando ainda mais o valor total da função objetivo.
• Afinidade entre produtos por alocar (3º somatório): Alocar dois produtos i e k, recebidos pelo armazém, sabendo que ambos pertencem ao mesmo depositante, conduz à atribuição de um  “bónus”  caso ambos ocupem a mesma estante, minimizando ainda mais o valor total da função objetivo.

Problemas com o Modelo de Otimização– Fórmula I

Elevado número de variáveis de decisão

A implementação da fórmula descrita na secção anterior implicaria que um elevado número de variáveis de decisão tivessem de ser computadas. Para diminuir o número de variáveis de decisão existentes no modelo, dividímos tanto os produtos como as estantes em 3 categorias: A, B e C. Assim sendo, os produtos da categoria A representam os produtos com maior saída, enquanto os produtos da categoria C aqueles com menos saída, ou seja, que mais tempo permanecem no armazém. De forma idêntica dividímos as estantes em 3 categorias, tal como ilustrado na Figura 2. Analogamente, as estantes classificadas com a categoria A correspondem às estantes mais próximas do corredor principal e as de categoria C, aquelas que se encontram mais afastadas deste corredor. Tendo os produtos e as estantes classificadas em ABC, a ideia seria alocar os produtos do tipo A, B e C em estantes do tipo A, B e C, respetivamente, restringindo assim o universo de procura de prateleiras livres.

Figura 2 – Planta simplificada do armazém de acordo com as categorias ABC

Termo quadrático da função objetivo

O 3º somatório da função objetivo contém a multiplicação de duas variavéis de decisão, tornando-o, por isso, num termo quadrático e, consequentemente, a função objetivo passa a ser um problema de programação quadrática. Muitas bibliotecas de Otimização open-source encontram-se disponíveis online, todavia, esse tipo de bibliotecas não são adequadas para resolver problemas de programação quadrática, mas sim para resolver problemas de programação linear. Muitos dos solvers utilizados em programação quadrática são comerciais, exigindo, por isso, uma licença para a sua utilização. Alguns disponibilizam um período experimental, pelo que podem ser usados gratuitamente, mas por um curto período de tempo. Perante este desafio, optámos, então, por aplicar um workaround: converter a função quadrática numa função linear, utilizando para o efeito o método McCormick Envelopes.

McCormick Envelopes

Este método é muitas vezes utilizado para resolver problemas de programação não linear inteira mista (Mixed-Integer Non Linear Programming) [1].  A ideia consiste em substituir a multiplicação de 2 variáveis por uma nova variável e adicionar 4 novas restrições que definem o valor mínimo e máximo que essa nova variável pode ter, com base nos valores mínimo e máximo estabelecido para cada uma das 2 variáveis envolvidas na multiplicação. Tome-se como exemplo, 2 variáveis x, y que multiplicam entre si e são substituídas por w. Ou seja, xy = w. As restrições definidas para a nova variável w são inequações definidas da seguinte forma:

Modelo de Otimização– Fórmula II

Aplicando o método supracitado McCormick Envelopes ao nosso problema de otimização, obtemos o seguinte modelo:

Variáveis de Decisão:

Xij = número de produtos i alocados na estante j.

Wijkj = representa a multiplicação: Xij Xkj

Função Objetivo:

Tj = tempo desde a estante j até ao corredor principal

Ri = rotação de stock do produto i

Aj = conjunto de produtos alocados na estante j

Rik = peso atribuido à relação entre os produtos i e k

Restrições

Como implementar o modelo de Otimização do armazém com o Google OR-Tools?

Esta secção descreve como foi implementado o modelo de Otimização(Fórmula II) com o Google OR-Tools, usando como exemplo um cenário simplificado do problema de Otimização do armazém, ilustrado na Figura 3. Neste cenário, o armazém tem de alocar 3 caixas do produto P1, 2 caixas do produto P2 e 2 caixas do produto P4 em 3 estantes com capacidade livre para os guardar: NN.23, NN.25 e NN.27. Todos os produtos e as estantes pertencem à categoria A. Note-se que a estante NN.25 possui uma caixa do produto P3, alocada, previamente, a essa estante.

Figura 3 – Cenário simplificado do problema de Otimização do armazém

Na implementação do modelo de Otimização foram criadas 5 classes para representar o problema:

• Produto (Product): produtos recebidos pelo armazém. Esta classe contém dados como o nome do produto, a sua rotação de stock, a quantidade a arrumar, o depositante e a categoria a que pertence.
• Localização (Location): estantes onde são arrumados os produtos. Esta classe contém dados como o nome da estante, o tempo desde a estante até ao corredor principal, a categoria, capacidade máxima, capacidade livre e lista de produtos armazenados nessa estante.
• Custo (Cost): custo de armazenar um produto i numa estante j. O valor desse custo é dado por: tempo corredor principal j * (1/rotaçãostocki)
• Relação entre Produtos Alocados e Não Alocados (AllocatedProductRelationship): afinidade entre produtos alocados e não alocados. Esta classe possui um atributo chamado weight que pode ser 0 ou 10 (valor configurável). Se um produto for alocado numa estante que contenha pelo menos um produto do mesmo depositante, a variável weight é igual a 10, caso contrário é 0.
• Relação entre Produtos Não Alocados (UnallocatedProductRelationship): afinidade entre dois produtos não alocados. Esta classe possui um atributo chamado weight que pode ser 0 ou 1 (valor configurável). Se dois produtos não alocados, do mesmo depositante, ficarem na mesma estante, a variável weight assume o valor 1, caso contrário o seu valor é 0.

De seguida, são apresentados os seguintes passos para a implementação do modelo de optimização:

1. Importar as bibliotecas necessárias

Figura 4 – Importe das bibliotecas do Google OR-TOOLS

2. Criar e instanciar o modelo de dados com a seguinte informação:

• Custo de atribuir cada produto (P1, P2 e P4) a cada estante (NN.23, NN.25 e NN.27);

Figura 5 – Função de criação do Modelo de Dados e Custos de atribuição dos produtos a cada estante

• Afinidade de cada produto (P1, P2 e P4) com os produtos alocados em cada estante (NN.23, NN.25 e NN.27). Neste exemplo, só a estante NN.25 tem 1 produto alocado (P3), pelo que a afinidade é calculada apenas entre P1 e P3; P2 e P3 e P4 e P3. Como P2 e P3 são do mesmo depositante (X), o valor do weight só é igual a 10 para este par de produtos. 

Figura 6 – Afinidade entre Produtos Alocados e Não Alocados

• Afinidade entre produtos a alocar do mesmo depositante (P1 e P4). Estes dois produtos são ambos do depositante Z.

Figura 7 – Afinidade entre Produtos Não Alocados

• Produtos a alocar e Prateleiras com capacidade disponível

Figura 8 – Produtos a Alocar e Estantes com Capacidade Disponível

3. Declarar o solver

Figura 9 – Declaração do solver CBC

4. Criar as variáveis de decisão

Figura 10 – Variáveis de Decisão

5. Definir as restrições

6. Definir a função objetivo

7. Chamar o solver e imprimir os resultados

Figura 11 – Resultado sugerido pelo Otimizador

Figure 12 – Solução sugerida pelo Otimizador

A Figura 14 ilustra a sugestão devolvida pelo otimizador e que passa por alocar as 3 caixas do produto P1 (o que tem mais saída) na estante NN.23 (a mais próxima do corredor principal), dando preferência por alocar o produto P2 na estante NN.25, onde já existe uma caixa do Produto P3 (ambos do depositante X). Quanto ao produto P4, este ocupou a prateleira vaga da estante NN.23 (onde foi alocado P1, uma vez que ambos pertencem ao depositante Z) e a outra prateleira vaga da estante NN.25, a única que sobrou, após a alocação de P2 junto de P3. Nesta fórmula, a afinidade entre produtos influencia a sua destribuição pelas estantes, pelo que valores diferentes do weight implicariam uma distribuição diferente dos produtos pelo armazém.

Em suma, neste artigo foi apresentado, não só um problema de Otimização aplicado a um caso de uso real, como também como o mesmo pôde ser resolvido através da construção e implementação de um modelo de optimização, usando a biblioteca Google OR-Tools.

Bibliografia

[1] https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes

[2] Li, Jiaxi; Moghaddam, Mohsen; Nof, Shimon Y. (2015). Dynamic storage assignment with product affinity and ABC classification—a case study, páginas 2 – 6.