A tarefa da entrega de mercadorias

Neste post, veremos como o Flexport usa a matemática e a ciência de dados para resolver problemas de entrega e entregar mercadorias no prazo, com o menor custo possível.

Considere um cenário especulativo: o remetente tem dez partidas e um voo de destino para qualquer remessa. A única decisão a ser tomada é se deve atribuir cada remessa a esse único voo. Se não atribuirmos uma carga específica ao voo, suponha que seja possível movê-la de outra maneira.

Cada remessa tem volume e custo, e o voo é limitado em volume. Você pode pensar nisso como um problema simplificado de mochila. Portanto, existem 1024-1 = 1023 soluções possíveis (não enviaríamos o avião completamente vazio).

Poderíamos criar uma planilha para listar toda a solução e escolher a mais rentável. Mas e se você tiver as mesmas dez partidas, mas dois vôos? São 59.049 soluções em apenas 10 remessas.

Um grande despachante tem mais de dez partidas e, é claro, mais de dois vôos para escolher, o que leva a trilhões a trilhões de possíveis soluções. Entre eles, apenas milhões são viáveis, o que significa que o método tradicional de planilha pode encontrar pelo menos uma solução viável. Mas não precisamos apenas de soluções viáveis. Precisamos das melhores e melhores soluções. Como encontrá-los entre inúmeras possibilidades? Uma resposta é usar a programação inteira.

A programação inteira é uma subseção da otimização discreta, uma área de estudo de operações relacionada à minimização de algumas funções objetivas sujeitas a restrições. Queremos minimizar os custos totais, desde que as mercadorias sejam entregues pontualmente nos lugares certos, empilhadas em ULD (Dispositivo de Carga da Unidade - um meio de embalar mercadorias). Nós nos esforçamos por uma solução ideal, mas na prática às vezes não conseguimos alcançá-la. Nesse caso, estamos satisfeitos com uma solução boa ou próxima. Aqui nos restringimos a um modelo simples no qual a solução ideal é alcançável.

O primeiro passo para resolver este problema é recorrer à literatura. A comunidade científica lida com o encaminhamento de frete há muitos anos. Encontramos vários trabalhos que lembram muito o nosso problema. Tiramos muitos dos seguintes conceitos e notações desses trabalhos e agradecemos aos autores por sua contribuição a essa área.

Começamos definindo a função objetivo. Para minimizar os custos, precisamos entender o conceito de peso padrão. Em resumo, o peso padrão é o peso mínimo com o qual o remetente concorda em trabalhar, independentemente do peso realmente oferecido. Temos peso total, peso padrão e chances de sobrecargas e, inversamente, baixo peso. O peso padrão vezes o baixo peso é uma subestimação, para que possamos ignorar o baixo peso e focar no fator de sobrecarga multiplicado pela própria sobrecarga.

A função objetivo é minimizar o custo total, definido como o peso total de todas as mercadorias atribuídas pela ULD, multiplicado pelo fator de carga. Por exemplo, se o ULD1 tiver 100 kg de congestionamento e a taxa de congestionamento do ULD1 for de US $ 4 por quilograma, o custo total do ULD 1 será de US $ 400. Portanto, precisamos de alguma notação por estar acima do peso e por seu valor.

Deixe ser$$$y_j^E$  - peso ULD j acima do padrão e $$$c_j^E$ - fator de custo para o mesmo ULD. Precisamos calcular$$$y_j^Ec_j^E$ para todos $$$j$. E se$$$j \in {1, 2, 3}$então a função objetivo será $$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$. Desmorona para$$$\sum y_j^Ec_j^E$. Queremos minimizar o valor, portanto, nosso objetivo final:

$$

$$\text{min} \sum_{j} y^E_j c^E_j$$

Valor para $$$c_j^E$não é um valor calculado. Este parâmetro é obtido de uma planilha ou banco de dados. Mas$$$y_j^E$ definimos como o peso total de sobrecarga para ULD $$$j$, que podemos calcular como o peso total de todos os suprimentos atribuídos pela ULD (denotá-lo $$$y_j$), menos o peso padrão deste ULD. O peso padrão é específico para o tipo ULD e também é um parâmetro. Deixe ser$$$U_j^P$  é o peso padrão para ULD $$$j$em quilogramas. Em seguida, a quantidade de peso extra para ULD$$$j$ definido como $$$y_j^E=y_j-U_j^P$.
O peso total do ULD, é claro, depende de quais pesos são atribuídos ao ULD e seu peso. Portanto, precisamos de uma expressão para calculá-lo, incluindo os detalhes mencionados acima.

Esta é simplesmente a soma dos pesos atribuídos pela ULD. Como indicar que um lote de mercadorias foi atribuído a um ULD específico? Para fazer isso, não precisamos de um parâmetro, mas de uma variável de solução. Uma variável de decisão é algo que o solucionador pode controlar enquanto minimiza a função objetivo.

Deixe o parâmetro$$$g_i$ representa peso bruto $$$i$em quilogramas.
Por exemplo,$$$g_4=500$significa que uma carga de 4 pesa 500 kg.

Deixe ser$$$x_{i, j}$  - uma variável de decisão que assume o valor 1, se a remessa $$$i$atribuído por ULD $$$j$e $$$0$de outra forma. Assim, quando queremos contar todas as remessas atribuídas pelo ULD 3, podemos percorrer todas as variáveis$$$x_{i, j}$Onde $$$j=3$. Se tivéssemos 4 remessas e os números de remessa 1 e 3 fossem atribuídos ao ULD 3, ficaria assim:

$$

$$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} = 1 + 0 + 1 + 0 = 2$$

Mas precisamos de peso total, não de quantidade. Para obtê-lo, você pode simplesmente multiplicar cada variável da solução por um parâmetro de peso. Como a variável de decisão assume o valor 0, se não for atribuído um peso, esse peso será redefinido e não incluído no total. Suponha que os pesos das cargas de um a quatro sejam 10, 50, 25 e 5. Em seguida, o peso total na ULD 3 será:

$$

$$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3} = (10)(1) + (50)(0) + (25)(1) + (5)(0) = 10 + 25 = 35$$

Vamos escrever este cálculo do peso total em geral. Determinar o peso total do ULD$$$j$ Como $$$y_j$. Então$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$e $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. Podemos recolher isso usando a notação de soma$$$y_1 = \sum g_ix_{i, 1}$ e $$$y_2=\sum g_ix_{i, 2}$. Como queremos que isso seja verdade para todos os possíveis$$$j$, usamos o sinal "para todos": $$$\forall$. Isso nos dá a forma final do nosso limite de peso total:

$$

$$y_j=\sum_{i \in I}g_ix_{i,j} \forall j \in J$$

Peso extra

Agora que temos o peso total, podemos aplicar nossa fórmula para a carga extra:

$$

$$y_j^E = y_j-U_j^P \quad \forall j \in J$$

Por exemplo, se $$$y_1=1500$e e $$$U_1^P=1000$então peso extra $$$y_1^E = 1500 - 1000 = 500$quilogramas. Multiplique isso pelo fator de custo para obter o resultado em dólares. À primeira vista, isso pode parecer suficiente, mas e o caso em que o peso total de toda a carga para ULD não excede o peso padrão? Nesse caso, se usássemos a fórmula "como está", o peso da sobrecarga seria um número negativo. Por exemplo, se o peso padrão for 1650 kg e o peso total designado for 1000 kg, sobrecarga = 1000-1650 = -650. A função objetivo multiplica esse número por um fator para sobrecargas e obtemos um número negativo. Como se a transportadora nos pagasse enviando menos do que o custo de um peso padrão.

Aqui está o que realmente queremos:$$$\text{max}(y_j^E, 0)$.
É o mesmo que definir 0 para uma variável, o que é tão simples quanto criar uma restrição$$$y_j^E>=0$.

$$$y_j^E >= y_j - U_j^P \quad \forall j \in J$, $$$y_j^E >= 0 \quad \forall j \in J$

Portanto, implementamos a função max () na programação matemática: a = max (b, c), ou seja, a> = b && a> = c. Vejamos nossas definições.
Função objetiva:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: Taxa de sobrecarga ULD $$$j$
$$$y_j^E$: Sobrecarga de ULD $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: ULD de peso padrão $$$j$
$$$g_i$: Peso bruto de envio $$$i$
$$$x_{i, j}$: variável de decisão; $$$x_{i, j}=1$se remessa $$$i$atribuído por ULD $$$j$, $$$0$de outra forma.
$$$y_j$: peso total de todas as remessas designadas pela ULD $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Toda carga deve voar

Nesse ponto, poderíamos escrever isso em Python e enviá-lo ao solucionador. Se fizermos isso, descobriremos que o solucionador atribuiu zero entregas a qualquer voo e podemos entender rapidamente o motivo: a melhor maneira de minimizar a função objetivo é não acumular custos. Isso leva à seguinte restrição: cada lote deve ser atribuído a algum ULD. Estenderemos isso a cada carga que deve ser atribuída a um e apenas um ULD, embora na realidade possamos dividir a carga em vários ULD e até vários vôos.

Significa que$$$x_{i, j}$só pode ser 1 para um valor único de $ j $. Por exemplo, se estamos pensando em enviar 13, então$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. Queremos aplicar essa restrição a cada remessa.$$$i$ (que escrevemos como $$$\forall i\in I$) e podemos recolher a adição usando o operador de soma ($$$\sum$), então nossa limitação final é:

$$

$$\sum_{j \in J} x_{i, j}=1\quad\forall i \in I$$

Dada essa limitação, o solucionador começará a atribuir remessas aos vôos, mas ele simplesmente distribuirá as remessas entre todos os vôos disponíveis até que os pesos sejam atingidos. O solucionador colocaria cada remessa restante em um ULD com o menor custo adicional. Excluindo o volume ou peso deste ULD. Portanto, as seguintes restrições adicionais são volume e peso.

Limitações de volume e peso

Vamos decidir $$$U_j^M$como carga útil máxima em quilogramas de ULD $$$j$e $$$U_j^$como volume máximo em metros cúbicos ULD $$$j$. Vamos decidir$$$v_i$, e o volume em metros cúbicos de carga $$$i$. Para limitar o modelo à capacidade máxima de carga e volume máximo, temos as condições:

$$

$$y_j<=U_j^M \quad \forall j \in J$$

$$

$$\sum_{i \in I} x_{i,j} v_ i <= U_j^V \quad \forall j \in J$$

Um veterano da indústria perceberá imediatamente que isso não é verdade. Por quê? Porque essas restrições tratam a carga como se pudesse ser despejada, como água, em qualquer volume. Na realidade, as cargas são rígidas ou têm outras restrições, como empilhamento. 10 metros cúbicos de carga não podem ser embalados em um volume arbitrário igual a exatamente 10 metros cúbicos. Para lidar com esses casos, você precisa resolver o problema de empacotar em contêineres. Verificamos se certos volumes cabem dentro de outros, mas isso está além do escopo deste artigo.

Agora, o solucionador atribui o ULD da remessa, respeitando o peso e o volume máximo e minimizando o custo total. Mas há outro problema: não dissemos nada sobre a nomeação dos itens e a observância das datas de entrega. De fato, existem quatro registros de data e hora que você deve considerar ao atribuir uma remessa: O

horário em que a remessa está realmente pronta para consolidar-se com outras remessas no ULD e carregar no voo. Vamos usar$$$Q_i^-$para representar o tempo em que a remessa está pronta $$$i$.
O tempo em que as mercadorias devem ser descarregadas no destino é desconsolidado e disponível para recebimento, em regra, do terminal de carga. Vamos usar $ Q_i ^ + $ para representar o prazo de entrega$$$i$.
O horário em que toda a carga deve ser entregue no terminal de carga para ser carregada no voo. Vamos usar$$$T_j^ -$para representar o tempo de recorte da carga ULD $ j $.
Hora de chegada do voo: é a hora em que a carga no voo fica disponível no armazém de destino. Vamos usar$$$T_j^+$ para representar a hora de chegada do voo da ULD $$$j$

Origem e Destino

Introduzir mais um conjunto $$$J_i$, que definimos como um conjunto de voos, cuja origem e destino coincidem com a partida e o recebimento da carga $$$i$. Em outras palavras, se a partida 85 for de Hong Kong e destino em Londres, então $ J_ {85} $ é o conjunto de todos os ULDs com partida de Hong Kong e destino em Londres.
Agora podemos usar$$$j \in J_i$ para obter um kit ULD que corresponda à rota comercial de remessa $$$i$ou podemos usar $$$j \notin J_i$para obter um conjunto de ULD que não corresponde. Para proibir a ligação de carga à ULD, que não corresponde à sua origem e destino, simplesmente restringimos$$$x_{i,j} = 0$para todos esses vôos. A restrição é totalmente descrita da seguinte maneira:

$$

$$\sum_{j \notin J_i} x_{i,j}=0 \quad \forall i \in I$$

Tempo de entrega

Ao trabalhar com carimbos de data e hora na otimização, é conveniente apresentar os momentos necessários como horário do Unix. Vantagens da abordagem:

1. Armazenando datas como números.
2. Não há necessidade de lidar com fusos horários.
3. O solucionador usa comparações diretas mais-menos.

O voo deve chegar antes do horário de entrega:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Observe que, assim como para a restrição acima sobre partida e destino, indicamos que essa restrição se aplica apenas ao ULD no conjunto $$$J_i$Onde $$$J_i$ é um conjunto de ULDs que correspondem ao envio e recebimento de remessas $$$i$. Isso é tudo! Vamos olhar para o modelo inteiro.

Modelo completo

Sob essas restrições, o solucionador atribui os itens da ULD da maneira mais barata, com cada carga sendo entregue do local certo de partida para o destino certo. Obviamente, a carga é entregue no prazo e sem sobrecarregar os itens por volume ou peso.

Parâmetros

$$$I$: Um conjunto de todas as remessas. Uma remessa enviada$$$i$
$$$J$: Um conjunto de todos os ULD. ULD individual é minúsculo$$$j$.
$$$J_i$: Um conjunto de todos os ULDs que correspondem ao remetente e ao destinatário $$$i$.
$$$g_i$: Peso bruto de envio $$$i$em quilogramas.
$$$v_i$: Volume em metros cúbicos de embarque $$$i$
$$$c_j^E$: Taxa de sobrecarga ULD $$$j$em dólares americanos por quilograma
$$$U_j^M$: Capacidade máxima de peso ULD $$$j$em quilogramas
$$$U_j^V$: Potência surround máxima da ULD $$$j$em metros cúbicos
$$$U_j^P$: ULD de peso padrão $$$j$em quilogramas

$$$T_j^-$: Tempo de entrega permitido no terminal ULD $$$j$.
$$$T_j^+$: Hora de chegada da ULD $$$j$.
$$$Q_i^-$: Horário de embarque $$$i$. 
$$$Q_i^+$: Tempo de entrega $$$i$.

Variáveis ​​de decisão e função objetivo:
$$$y_j$: Peso total da ULD $$$j$
$$$y_j^E$: Sobrecarga de ULD $$$j$em quilogramas.
$$$x_{i,j}$: 1 se estiver enviando $$$i$atribuído por ULD $$$j$0 caso contrário.

Função alvo

$$

$$\text{Minimize} \sum y_j^Ec_j^E$$

Limitações

$$$y_j$ - peso total das remessas em ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
O peso extra jE é máximo (0, yj-UjP):
$$$y_j^E >=y_j-U_j^P \quad \forall j \in J$
$$$y_j^E >=0 \quad \forall j \in J$
Cada entrega deve ser atribuída exatamente a 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ não pode exceder o peso máximo: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$não pode exceder a capacidade máxima: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Passos adicionais

Este artigo descreve a programação matemática subjacente ao objetivo da carga do voo. Mas apenas escrever matemática não é suficiente. A próxima etapa é implementar o programa, provavelmente em AML, como Pyomo, ou usando sua própria API do solver, por exemplo, API Python Gurobi. Depois disso, o desenvolvedor escreverá um código para transferir os parâmetros de todas as partidas e vôos disponíveis. Em seguida, a instância do modelo é enviada ao solucionador. O solucionador define os valores das variáveis ​​de decisão da maneira ideal. Em seguida, o desenvolvedor deve fazer algo com os valores das variáveis ​​de decisão.