Quando empresas de produtos com vários armazéns compõem várias remessas para atender a um pedido do cliente, isso é chamado de remessa multiorigem. Uma parte do pedido pode vir de um depósito enquanto outra parte vem de outro. O cliente receberia esse pedido como duas entregas separadas, provavelmente em momentos diferentes. A principal razão para usar a remessa multiorigem é reduzir os prazos de entrega para um cliente e geralmente é apenas uma coisa para grandes empresas que podem pagar por ter armazéns em todo o país.

Como a maioria de nós sabe, o negócio de compras online disparou nos últimos anos . Isso se deve em parte à pandemia de corona, mas os negócios aumentaram muito antes disso. No entanto, durante o período de pandemia, as lojas varejistas tiveram dificuldades em lidar com a forte queda de clientes na loja, enquanto, ao mesmo tempo, os clientes online estavam dispostos a pagar mais por entregas no mesmo dia ou em menos tempo. Isso levou à ideia de transformar lojas varejistas tradicionais de tijolo e argamassa em depósitos parciais e permitir que empresas de entrega terceirizadas entregassem a clientes próximos em horas, em comparação com entregas de pelo menos um dia de algum depósito distante.

Neste artigo, mostrarei como programar essa otimização. Passaremos passo a passo para entender o que estamos otimizando, como podemos representar os dados e as variáveis, como construir o modelo e as relações entre as variáveis. Depois disso, formulamos explicitamente o que minimizar e executamos o solucionador. Por fim, damos uma olhada na solução, tentamos ver se está correta e também dou uma indicação de desempenho e tempo para problemas maiores ‍♂.

Vamos codificar!

Primeiras coisas primeiro, vamos colocar um novo ambiente conda . Nesse caso, usaremos o Python versão 3.9.

conda create --name=opt-example-0 python=3.9
conda activate opt-example-0

Usaremos um pacote Python de código aberto, criado especificamente para problemas de otimização combinatória, chamado Puan. Ele tem todas as ferramentas necessárias para resolver esse problema com bastante facilidade. Antes de começarmos a codificar, precisamos saber o que realmente estamos tentando otimizar aqui. Como mencionado no início, a remessa multiorigem envolve prazos de entrega rápidos, mas é claro que não estaríamos dispostos a pagar um valor irracional por isso. Portanto, há algum tipo de objetivo múltiplo em que, por um lado, gostaríamos de prazos de entrega rápidos e, por outro lado, um baixo custo de envio. Para solucionadores de problemas de otimização combinatória comuns, não há configuração multiobjetivo incorporada. Em vez disso, devemos definir uma função linear que considera o custo e o tempo de entrega como entrada e gera um valor que, se baixo, significa que obteremos uma entrega rápida a um custo baixo, e se alto, é um custo de entrega alto ou um tempo de entrega longo, ou ambos. Em seguida, poderíamos usar um valor de proporção para decidir como queremos que eles se relacionem.

from typing import Tuple

# itertools is built into any python >= 2.7
# It is a variant of the built-in `map` function.
# The difference being that it will call the callback function (lambda i,j: ...)
# as fn(*args) instead of fn(args) as in the `map` case.
from itertools import starmap

def delivery_burden(cost: int, time: int, ratio: Tuple[int, int]) -> int:
    """
        A value representing the total delivery burden as a mix of the
        delivery cost and delivery time. The ratio defines the
        relationship between cost and time. 
    """
    return sum(
        starmap(
            lambda x,y: x*y, 
            zip(
                [cost, time], 
                ratio,
            )
        )
    )

# pip install numpy
import numpy as np

# We put up an example here with 3 warehouses and 5 articles
# to choose from. The customer order contains only choises from
# four of them. Then delivery cost and time

in_stock = np.array([    
    # each column is an article   
    [  1,  1,  1,  1,  0], # each row is a warehouse
    [  1,  1,  0,  1,  2],
    [  1,  0,  1,  1,  3],
])
# ... so for instance, warehouse 0 has only one of article 0

customer_order = np.array(
    # each column is a product
    # for instance, two items of article 0 is ordered
    [  2,  2,  1,  2,  0],
)

delivery_costs = np.array(
    # each element is a delivery cost, per warehouse.
    # For instance, it costs 10 units to deliver from warehouse 0
    [ 10,  2,  1],
)

delivery_times = np.array(
    # each element is delivery time, per warehouse
    # For instance, it takes 5 time units to deliver from warehouse 1
    [  1,  5, 10]
)

Para este caso, usarei uma combinação de programação orientada a objetos e funcional. É bastante confortável definir cada variável de decisão como uma classe. Isso torna muito mais fácil modelar com base em propriedades variáveis ​​dessa maneira. O processo de construção do modelo, no entanto, será puramente funcional. Isso pode ser um pouco intimidador, mas como a solução de otimização combinatória geralmente requer muito tempo e esforço de computação, gostaríamos que a construção do modelo fosse uma bênção em comparação.

Começamos criando todas as variáveis ​​de decisão (o valor de uma variável de decisão é o que será decidido por um solucionador posteriormente no processo e retornado junto com todos os outros valores de variáveis ​​como uma solução ótima para o problema em questão). No nosso caso, precisamos de uma variável de decisão para cada warehouse e uma variável de decisão para cada variável em cada warehouse (para que possamos diferenciá-las). Mas primeiro ☝️! Criamos classes para representar os nossos armazéns e artigos.

# pip install puan
from puan import variable, Bounds

class Article(variable):

    """
        An ``Article`` is unique from which warehouse (i) it
        is in and which product (j) it represents.
    """

    def __init__(self, i: int, j: int, bounds: Bounds) -> ():
        super().__init__(

          # variable id would be a string constructed
          # from the class name, warehouse `i` and product `j`.
          id=f"{self.__class__.__name__}_{i}{j}", 
          
          # variable bounds to decide where on the number line
          # this variable will vary. E.g. varying from 0 to 10
          # would be `Bounds(lower=0, upper=10)`
          bounds=bounds,
        )
        self.i = i
        self.j = j

class Warehouse(variable):

    """
        A ``Warehouse`` is unique from a row index i.
        It also takes delivering cost and time (in hours).
    """

    def __init__(self, i: int, cost: int, time: int) -> ():
        super().__init__(

          # variable id would be a string constructed
          # from the class name and warehouse `i`.
          id=f"{self.__class__.__name__}_{i}", 

          # variable bounds
          # (a quick way to say the variable can take 0 or 1 as value
          # is to specify a bool type for it)
          dtype="bool"
        )
        self.i = i
        self.cost = cost
        self.time = time

Para construir um modelo de otimização combinatória, precisamos de variáveis ​​de decisão para representar os dados que temos. Começamos construindo todas as variáveis ​​Article .

articles = starmap(
    lambda i,j: Article(
        i, j,
        # The lower bound for the article would be 0,
        # since we want the solver to select what article, how many and
        # from what warehouse to pick and not us here and now.
        # The upper bound however must take the the value from the
        # stock table, since we can't of course let it take more than
        # what's possible.
        bounds=Bounds(
            lower=0,
            upper=in_stock[i,j],
        ),
    ),
    np.argwhere(
        # We compute which articles is of interest by
        # just catching articles that has a value in the
        # warehouse's stock and also was ordered by the customer.
        (in_stock != 0) * (customer_order != 0)
    )
)

Em seguida, construindo todos os armazéns.

# We can just use a simple `map` for this case
warehouses = map(
    lambda i: Warehouse(
        # set the index of the warehouse and get
        # the delivery cost and hours from the data 
        i=i,
        cost=delivery_costs[i],
        time=delivery_times[i],
    ),

    # ... difference here is that we check that a
    # warehouse (row) has at least one article, and
    # that it is also in the customer's order.
    np.argwhere(
        (
            (in_stock != 0) * (customer_order != 0)
        ).any(axis=1)
    
    # we know that we'll just get one column from `argwhere` expression
    # (because of .any(axis=1)) so we index it out directly.
    ).T[0]
)

from itertools import chain

variables = list(
    # `chain` is a method for concatenating iterables into one iterable,
    # which we'll then exhaust into a list.
    chain(
        articles,
        warehouses,
    ),
)

import puan.logic.plog as pg

warehouse_article_relationships = map(

    # Creates a logic relationship saying that
    # if any of the warehouses (i) is selected,
    # then select at least one of the articles (j).
    # Also, if any of articles (j) of warehouse (i) is selected,
    # then select warehouse (i).
    # This logic relationship can simply be achived using the XNor
    # logic connector.
    lambda warehouse: pg.XNor(

        # Here we just put the current warehouse 
        warehouse,

        # And here declare all of warehouse (i)'s articles
        pg.Any(
            # filter all articles that has a connection
            # to the current warehouse.
            *filter(
                lambda article: article.i == warehouse.i,    
                filter(
                    lambda variable: issubclass(
                        variable.__class__, 
                        Article,
                    ),
                    variables,
                )
            )
        ), 
    ),
    # filter out all Warehouse variables
    filter(
        lambda variable: issubclass(
            variable.__class__, 
            Warehouse,
        ),
        variables
    )
)

order_articles_relationships = map(

    # Here we want to create a lower bound on customer's
    # order such that all articles in the order actually gets selected.
    # So for each column in `customer_order`, we make sure the sum
    # of them is at least what the customer ordered 
    # (
    #   yes, this means that we can get too many since there's no upper bound, 
    #   but we'll fix that in how we construct the objective function later
    # )
    lambda j: pg.AtLeast(

        # Get the customer order's article value
        # (how much of article (j) the customer wants)
        value=customer_order[j],

        # Filter all articles (j) that was in the customer's order
        propositions=filter(
            lambda article: article.j == j,    
            filter(
                lambda variable: issubclass(
                    variable.__class__, 
                    Article,
                ),
                variables,
            )
        )
    ),

    # Gets all indices where customer order is not zero
    # The column index in customer order is the article (j).
    np.argwhere(
        customer_order != 0,
    ).T[0]
)

model = pg.All(
    *warehouse_article_relationships,
    *order_articles_relationships,
)

… Exceto a função objetivo. Conforme mencionado no início do processo de implementação, precisamos saber o que estamos otimizando. Definimos uma delivery_burdenfunção que deve nos dar algum valor para cada custo e tempo de entrega do armazém, e deve ser essa soma que queremos minimizar. Lembre-se, a solução que queremos é aquela que minimiza o custo e o tempo de entrega. No entanto, o solucionador que usaríamos neste caso (que obteremos da irmã de Puan repo puan-solvers ) faz apenas maximizações. Mas não se preocupe ! Em vez disso, simplesmente negaremos o valor da carga de entrega.

# This constant ratio we could play around with later.
# It will result in preferring lesser delivering costs over longer
# times, and vice versa. But for now we'll keep it simple.
delivery_cost_time_ratio = (1,1)

# The objective datatype declared as input into `puan-solvers` solvers
# is a dict mapping id to a value. 
objective = {

    # Notice the multiplying with -1 as mentioned.
    warehouse.id: -1 * delivery_burden(
        cost=warehouse.cost, 
        time=warehouse.time, 
        ratio=delivery_cost_time_ratio,
    )
    for warehouse in filter(
        lambda variable: issubclass(
            variable.__class__, 
            Warehouse,
        ),
        variables,
    )
}

# ... pip install puan-solvers
from puan_solvers import scipy_solver

solution, objective_value, status = next(
  # we use the solve method directly on the model instance
  # which takes a `solver` as argument. This is if we'd like
  # to easily switch between other solvers.
  model.solve(
      [objective], 
      solver=scipy_solver,
  )
)
# The solve method returns an iterator which will iterate over
# all solutions for each objective that was put into the method.
# We use the built-in `next` method to get the first

# you should have `maz` installed already from puan.
# If not, just pip install maz
from maz import pospartial
from itertools import product

optimal_warehouse_article_order = np.array(
    list(
        map(
            pospartial(

                # We create a dict mapping from index pairs (i,j) to 
                # its corresponding solution value. We then want to
                # preload dict.get function (using maz.pospartial) with 
                # it and hardcode a default value to zero (in other words, if
                # we iterate on an index pair that we didn't considered
                # in the problem we default to zero)
                dict(
                    zip(
                        map(
                            # We want to map variable -> (i,j) since that
                            # is what we've got later
                            lambda variable: (variable.i, variable.j),
                            filter(
                                lambda variable: issubclass(
                                    variable.__class__, 
                                    Article,
                                ),
                                variables
                            ),
                        ),
                        map(
                            # here we extract values from solution
                            # for each variable that is an Article
                            lambda variable: solution[variable.id],
                            filter(
                                lambda variable: issubclass(
                                    variable.__class__, 
                                    Article,
                                ),
                                variables
                            ),
                        )
                    )
                ).get, # <- Notice the calling of `get` here
                # hard codes argument on index 2 for dict.get to be zero
                [(2,0)] 
            ),
            # `product` will create an iterable for us containing index
            # pairs ranging from 0 to the number of warehouses (i) and
            # ranging from 0 to the number of articles (j)
            product(
                *map(
                    range, 
                    in_stock.shape,
                )
            )
        )
    ), 
    dtype=int,
# lastly here we reshape it back into the same shape as in stock were
).reshape(in_stock.shape)

def minimum_shipping_cost_time(
    in_stock:           np.ndarray, 
    customer_order:     np.ndarray,
    delivery_costs:    np.ndarray,
    delivering_time:    np.ndarray,
    cost_time_ratio:    Tuple[int, int] = (1,1),
) -> np.ndarray:

    """
        Returns an article-warehouse configuration that minimizes delivery cost and time 
        and fulfills requested customer order, with respect to a given cost-time ratio.

        Parameters
        ----------
            in_stock: np.ndarray
                A `n x m` matrix where a row represents a warehouse and a column an article.

            customer_order: np.ndarray
                A vector of size `m` where each element `i` represents how many of article `i` was ordered.

            delivery_costs: np.ndarray
                A vector of size `n` where each element `i` represents the cost to deliver from warehouse `i`.

            delivery_times: np.ndarray
                A vector of size `n` where each element `i` represents the time it takes to deliver from warehouse `i`.

            cost_time_ratio: Tuple[int, int] = (1,1)
                A ratio between cost and time (`cost:time`). For instance if (2,1) then delivery cost is twice as
                less valuable as delivery time.

        Returns
        -------
            out : np.ndarray
                A  `n x m` matrix where a row represents a warehouse and a column an article.
    """  
    # copy necessary code into here...

Correção e complexidade

Duas coisas são importantes saber antes de podermos realmente usar nossa função: ela funciona e como funciona. Na verdade, é bastante complicado verificar a exatidão de tal função de otimização combinatória. Isso ocorre porque verificar se uma solução é ótima para tal problema é tão difícil quanto encontrá-la. Então, o que podemos fazer é gerar várias instâncias para as quais sabemos a resposta e, em seguida, apenas testar se a função retorna as mesmas soluções. Isso não prova nada, mas pelo menos nos dá uma dica de que está funcionando como esperamos. (Outra coisa a fazer é usar testes baseados em propriedades. Pode-se criar relacionamentos entre entradas e saídas e, em seguida, verificar se alguma condição entre elas é válida para várias instâncias. Sinta-se à vontade para verificar a biblioteca de hipótesesque fornece uma estrutura para testes baseados em propriedades). Vou colocar alguns testes aqui.

# Simple case. All articles in all warehouses
# and deliberately set higher cost and time on warehouse 1.
# Solution should be just picking all from warehouse 0.
actual = minimum_shipping_cost_time(
    in_stock=np.array([    
        [1, 1, 1],
        [1, 1, 1],
    ]), 
    customer_order=np.array(
        [1, 1, 1],
    ), 
    delivery_costs=np.array(
        [1, 2],
    ), 
    delivery_times=np.array(
        [1, 2]
    ),
)
expected = np.array([
    [1, 1, 1],
    [0, 0, 0],
])
assert (actual == expected).all()

# Check that it rather select two cheaper warehouses
# over one expensive warehouse
actual = minimum_shipping_cost_time(
    in_stock=np.array([    
        [1, 1, 1],
        [1, 1, 1],
        [0, 0, 2],
    ]), 
    customer_order=np.array(
        [1, 1, 2],
    ), 
    delivery_costs=np.array(
        [1, 2, 3],
    ), 
    delivery_times=np.array(
        [1, 2, 3]
    ),
)
expected = np.array([
    [1, 1, 1],
    [0, 0, 1],
    [0, 0, 0],
])
assert (actual == expected).all()

# Check ratio works. Here we
# have identical warehouses with
# opposite cost/time values.
actual = minimum_shipping_cost_time(
    in_stock=np.array([    
        [1, 1, 1],
        [1, 1, 1],
    ]), 
    customer_order=np.array(
        [1, 1, 1],
    ), 
    delivery_costs=np.array(
        [2, 1],
    ), 
    delivery_times=np.array(
        [1, 2]
    ),
    cost_time_ratio=(2,1)
)
expected = np.array([
    [0, 0, 0],
    [1, 1, 1],
])
assert (actual == expected).all()

from timeit import default_timer as timer

min_articles = 2
min_warehouses = 2
max_articles = 20
max_warehouses = 20

time_records = []
for iw, ia in product(range(min_warehouses, max_warehouses+1), range(min_articles, max_articles+1)):

    start = timer()
    minimum_shipping_cost_time(
        in_stock=np.ones((iw, ia), dtype=int), 
        customer_order=np.ones(ia, dtype=int), 
        delivery_costs=np.ones(iw, dtype=int), 
        delivery_times=np.ones(iw, dtype=int),
    )
    time_records.append(
        (
            (iw, ia), 
            timer()-start,
        )
    )

É claro que isso varia de acordo com o desempenho do computador em execução. Estou executando isso em um MacBook Pro com Intel Core i7 de 2,6 GHz e 6 núcleos.

Existem dois gráficos aqui representando os resultados de tempo. O primeiro tem “tamanho”, que é o número de armazéns vezes o número de artigos, no eixo x, e o tempo (em segundos) no eixo y. Há uma grande variação quando aumentamos de tamanho, onde os menores parecem crescer linearmente e os maiores exponencialmente. Pode depender se a instância tem um elevado número de armazéns ou um elevado número de artigos.

No segundo gráfico, em vez disso, mostramos o eixo x como o número de armazéns e no eixo y o número de artigos. O tamanho do ponto de cada medição é o tempo (em segundos). É bastante claro a partir deste gráfico que o tamanho nos armazéns aumenta o tempo mais lentamente, enquanto um maior número de artigos aumenta o tempo mais rapidamente. Do ponto de vista da construção do modelo, sabemos que o segundo tipo de relacionamento lógico que criamos depende apenas do número de artigos e cria um novo relacionamento lógico para cada artigo, enquanto o primeiro tipo de relacionamento lógico depende tanto do número de artigos quanto do número de armazéns. Esta é provavelmente a razão pela qual o número de artigos tem um impacto maior no tempo de computação.

Para concluir

Então agora você viu como minimizar o tempo e o custo de remessas de várias origens. Você também pode ajustar este programa ao seu gosto, talvez você queira otimizar em relação às emissões de carbono dos transportes também? E você pode brincar com a importância das diferentes partes de entrada da carga de entrega. O fluxo de trabalho descrito aqui também pode ser usado para outros casos de otimização. Contanto que você possa descrever formalmente os dados, variáveis ​​e relacionamentos entre eles, você pode otimizar uma enorme variedade de coisas com este método!