Entrega de última milha de vários depósitos em Python

Modelagem matemática, solução e visualização usando PuLP e VeRoViz

Com o rápido crescimento das compras online, as empresas enfrentam exigências cada vez maiores por entregas rápidas e de baixo custo. Entrega da última milha refere-se ao estágio final da cadeia de abastecimento, onde os pacotes são entregues de um depósito até a porta do cliente. Este é um problema tático complexo que envolve determinar conjuntamente como atribuir pacotes aos caminhões e como encaminhar os caminhões aos clientes. É também um problema muito caro, com estimativas recentes colocando a entrega na última milha em 53% do custo total de envio. Isto sublinha a necessidade de gerar planos de entrega eficientes.

A forma clássica deste problema envolve um único depósito (geralmente um armazém) a partir do qual todos os caminhões são carregados e enviados em suas entregas. Uma versão mais complexa envolve vários depósitos próximos uns dos outros – por exemplo, quando cadeias de varejo entregam em lojas. Nesse caso, um determinado cliente pode ser atendido por mais de um depósito, portanto a empresa também deve determinar quais depósitos enviarão para quais clientes. Às vezes, nenhum depósito terá todos os itens do pedido de um cliente disponíveis, exigindo que o pedido seja dividido entre vários depósitos.

Abaixo discutiremos como modelar e resolver este problema mais complexo de múltiplos depósitos usando programação inteira (IP). Este problema tem os seguintes aspectos:

1. Existe um conjunto de caminhões, depósitos, clientes e produtos.
2. Cada cliente encomendou uma quantidade específica de cada produto e cada depósito possui uma determinada quantidade de cada produto disponível.
3. Cada caminhão está baseado em exatamente um depósito (ou seja, sua rota sempre começa e termina na sua base). Além disso, os camiões não precisam de ser idênticos – cada camião pode ter uma capacidade de volume e um custo por quilómetro diferente.

O objetivo é determinar simultaneamente 1) os produtos a serem enviados de cada depósito para cada cliente, 2) como atribuir pacotes aos caminhões e 3) como encaminhar cada caminhão para seus clientes, tudo de uma forma que atinja o menor custo total. custo de entrega possível.

Implementaremos e resolveremos um modelo IP com Polpa E use VeRoViz para visualizar as rotas dos caminhões. Para começar, importamos as bibliotecas necessárias:

Um cenário de exemplo

Uma empresa de móveis possui dois depósitos na área de Fredericksburg, VA, com oito pedidos de clientes a serem entregues. Os dados e o mapa são mostrados abaixo. Observação: A nósArray variável foi preparada com o Ferramenta de esboço VeRoViz, que permite a criação gráfica de dados de localização e exportações para Python.

Modelando o Problema

Embora existam várias maneiras de abordar esse problema, construiremos e resolveremos um modelo de programação inteira. Isso fornece uma especificação matemática precisa do problema e permite que instâncias de problemas de tamanho moderado sejam resolvidas de maneira otimizada usando solucionadores disponíveis no mercado (embora, além do nosso escopo, instâncias maiores muitas vezes não possam ser resolvidas rapidamente com solucionadores disponíveis no mercado e exijam soluções especialmente -algoritmos de solução projetados). Começamos com as entradas do modelo:

A seguir, definimos nossas variáveis ​​de decisão:

Finalmente, definimos o modelo de otimização:

Neste modelo, a função objetivo (1) que queremos minimizar é simplesmente a soma de todos os custos de viagem incorridos. As restrições em (2) garantem que, para cada local, se um determinado caminhão chegar ao local, então o caminhão também partirá. As restrições em (3) garantem que nenhum caminhão saia de um depósito que não seja sua base. As restrições em (4) garantem que cada cliente receba todos os produtos que solicitou. As restrições em (5) garantem que nenhum subcircuito ocorra em nenhuma rota. Como um grupo de locais formando um circuito terá o mesmo número de arestas que nós, evitamos que isso ocorra em todos os possíveis subconjuntos não vazios de clientes para cada caminhão. As restrições em (6) garantem que, para cada depósito e produto, o total de unidades do produto carregado em caminhões e enviado aos clientes desse depósito não exceda a disponibilidade no depósito. As restrições em (7) garantem que nenhuma unidade de qualquer produto seja carregada em um caminhão e enviada a um cliente, a menos que o caminhão visite o cliente. As restrições em (8) garantem que, para cada caminhão, o volume total de produtos carregados a bordo não exceda sua capacidade. Finalmente, as restrições em (9–10) especificam os domínios para as variáveis ​​de decisão (binárias para o x variáveis; inteiro não negativo para o u variáveis).

Para facilidade e capacidade de reutilização, criaremos uma função Python para construir instâncias deste modelo para dados de entrada específicos usando Polpa:

Resolvendo o problema do cenário de exemplo

Agora que formulamos o modelo, podemos usá-lo para encontrar uma solução ótima para nosso cenário. Abaixo usamos o solucionador CBC que está incluído com Polpa. Isso pode levar de 15 a 45 segundos para encontrar uma solução ideal. Se você tiver acesso ao mais poderoso CPLEX solucionador, você pode usar as linhas comentadas para obter uma solução muito mais rápida.

Executar isso nos dá a seguinte mensagem de saída:

Extraindo e visualizando os itinerários do caminhão

Agora precisamos extrair os itinerários dos caminhões das variáveis ​​de decisão no modelo resolvido. Para cada caminhão queremos saber suas paradas e quais produtos entregar em cada parada. Para obter essas informações, precisamos examinar as variáveis ​​de decisão diferentes de zero.

Isso constrói os seguintes itinerários de caminhão:

Observe que o cliente C1 é visitado por dois caminhões (T2 e T4) — portanto, um pedido dividido. Dadas as demandas simultâneas dos clientes e os recursos disponíveis, esta acaba sendo uma decisão ideal. Isto também pode ser necessário quando, por exemplo, um pedido contém um conjunto de itens não encontrados em nenhum depósito.

Visualizando as Rotas dos Caminhões

Como nosso último passo, usamos VeRoViz para criar uma boa visualização das rotas dos caminhões:

Conclusão

Embora sejam possíveis muitas variações deste problema, este exemplo ilustra como podemos modelar e resolver tal problema usando programação inteira. Ele também mostra como Python pode ser usado para unir componentes poderosos, como Polpa e VeRoViz para criar rapidamente sistemas úteis de apoio à decisão. Feliz entrega!

O código-fonte pode ser visualizado em um notebook SUA PARTICIPAÇÃO FAZ A DIFERENÇA ou baixado SUA PARTICIPAÇÃO FAZ A DIFERENÇA.

Entrega de última milha de vários depósitos em Python republicado da fonte https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 via https:// em direçãodatascience.com/feed

<!–

->