Otimização de Redes Logísticas Sob Incerteza

Desafios na Otimização da Rede de Middle-Mile

Na AITY, compreendemos que a jornada de um produto até o cliente é complexa, e a rede de middle-mile — centros de distribuição e de triagem — é fundamental para cumprir as promessas de entrega. Por anos, engenheiros e cientistas têm expandido os limites computacionais para otimizar essa rede, um esforço intensificado pela sua crescente complexidade.

Eventos como grandes nevascas, interrupções de energia em centros de triagem ou picos de demanda por um produto viral são choques óbvios. Contudo, as fontes mais significativas de incerteza são as variações sutis diárias na demanda e nos tempos de viagem, que podem erodir a eficiência de toda a rede se não forem cuidadosamente observadas. Estimamos que otimizar apenas a variabilidade da demanda pode gerar economias potenciais de 0,5%, percentual que, embora pequeno, reflete diretamente na experiência do cliente.

Meses antes de uma compra, nossos especialistas em logística consideram questões complexas de roteamento: * Quais rotas os caminhões devem seguir entre os armazéns? * Quando os carregamentos devem partir? * Onde o inventário deve ser posicionado para atender à demanda?

O planejamento proativo da estrutura e sincronização da rede é conhecido como projeto de rede. Nosso desafio não é otimizar para condições perfeitas, mas sim construir planos que permaneçam eficazes mesmo quando as coisas não saem como o esperado.

Um Quebra-Cabeça Computacional de Complexidade Estonteante

Mesmo em condições ideais, otimizar a rede de middle-mile é desafiador, exigindo a coordenação de dezenas de milhões de produtos em centenas de instalações, cada uma com capacidade limitada e horários operacionais específicos.

Uma dificuldade central é a mistura de decisões de otimização: * Algumas são uma questão de grau (volume de pacotes em uma rota específica). * Outras são binárias (abrir ou não uma via de remessa; partir agora ou esperar por mais carga).

Combinadas, resultam em um problema de otimização de inteiros mistos, onde as estratégias de solução explodem combinatoriamente em tempo computacional e espaço de memória. Com apenas 300 decisões de "sim ou não", o número de combinações possíveis supera os átomos no universo observável. A rede da Amazon envolve milhões dessas decisões, complicadas por janelas de entrega que restringem horários de chegada e partida. Softwares de otimização de ponta já enfrentam dificuldades com este problema, mesmo com "informações perfeitas". Na realidade, as informações são imperfeitas, e um plano aparentemente ótimo pode desmoronar com a mudança das condições.

O Desafio de Lidar com a Incerteza

A incerteza se manifesta de duas maneiras principais: * Flutuações diárias: Variações em variáveis como demanda ou tempos de viagem. * Choques estruturais: Fechamento de estradas devido ao clima ou paralisações inesperadas de instalações.

A estratégia acadêmica comum de modelar muitos cenários e "robustificar" a solução falha na escala da Amazon. A infinidade de problemas potenciais torna ineficaz tentar robustificar contra cada um individualmente.

Em vez de buscar uma garantia impossível, focamos na optionalidade. Nosso objetivo é projetar um sistema com rotas alternativas suficientes e opções viáveis que permitam que flutuações diárias e choques acionem uma adaptação eficaz, em vez de crises. Essa flexibilidade exige projetar redes candidatas com opções integradas e testá-las contra muitos futuros plausíveis, utilizando ferramentas computacionais desenvolvidas internamente.

Tornando o Projeto de Rede Tratável

Nossa ferramenta de projeto de rede torna o problema da rede de middle-mile solucionável em escala, partindo de uma ideia simples: nem toda rota possível merece ser considerada. Assim como em uma viagem de carro, focamos em um punhado de rotas sensatas. A ferramenta identifica "pontos de consolidação" e encontra rotas eficientes que os utilizam.

Também respeitamos os horários operacionais precisos das instalações. Embora a modelagem em resolução fina (intervalos de 15 minutos) crie uma explosão de possibilidades, e uma resolução grossa (24 horas) resulte em um planejamento inútil, superamos esse problema. Nossa abordagem de otimização usa uma resolução de tempo razoavelmente grossa, mas para cada rota candidata, inclui "limites de tempo" pré-calculados — a última partida viável do caminhão e a chegada mais cedo possível — com precisão de 15 minutos. Isso garante que as rotas escolhidas funcionem em horários reais.

Ajustes de Rede Cientes do Risco em Escala

Mesmo com esses avanços algorítmicos, a solução de um único problema de planejamento determinístico na escala da Amazon pode levar horas para ser calculada devido às dificuldades de paralelização do algoritmo subjacente. Adicionar incerteza intensifica o desafio.

Uma abordagem ingênua para lidar com a incerteza seria simplificar o problema, assumindo que mais pacotes fluem entre locais grandes e próximos. Contudo, o middle-mile não é um conjunto de "tubos independentes"; os fluxos de produtos interagem. Um pico de demanda em um centro de distribuição afeta instalações próximas de maneiras específicas; uma nova estação de entrega altera os padrões de uma região.

Para capturar melhor essas dependências complexas, desenvolvemos uma abordagem que permite o projeto de rede ciente de risco via métodos Monte Carlo. Nossos modelos começam criando muitas permutações de dados de fluxo sintéticos origem-destino para representar flutuações diárias na demanda e choques estruturais maiores. Um componente crítico é um modelo de rede de atenção de grafos que representa a rede de middle-mile como dois grafos interconectados:

• Grafo de Locais: Nós representam centros de distribuição e estações de entrega, com arestas representando rotas de envio e proximidade geográfica. Isso permite ao modelo aprender padrões espaciais, como maior demanda em centros populacionais densos.
• Grafo Origem-Destino: Cada nó representa um par origem-destino específico. Essa estrutura permite capturar correlações sutis que o grafo de locais não consegue, como a interdependência de duas instalações próximas que atendem à mesma área.

Por exemplo, dois centros de distribuição próximos em Connecticut servindo a cidade de Nova York. Um modelo usando apenas o grafo de locais poderia estimar que cada instalação envia 8.000 pacotes para NYC, enquanto na realidade os volumes são muito menores porque as duas instalações compartilham essa demanda. O grafo Origem-Destino resolve isso, permitindo que o modelo aprenda que pares origem-destino com características similares podem exibir demanda correlacionada, mesmo quando distantes.

Munidos de cenários de demanda realistas que respeitam correlações espaciais e compreendem como as perturbações de rede se propagam, podemos gerar projetos de rede candidatos que funcionam bem em diversas condições de demanda.

Cumprindo as Promessas de Entrega Sob Incerteza

Nossos modelos, treinados em dados históricos de envio, geram cenários de demanda realistas que respeitam correlações espaciais. E, crucialmente, como as ferramentas entendem como as perturbações de rede se propagam no espaço, podemos produzir cenários plausíveis nunca antes encontrados, como mudanças na demanda impulsionadas pela abertura de uma nova instalação ou um grande evento climático regional.

Este é o ciclo completo: uma ferramenta projeta redes futuras candidatas, enquanto outra gera os cenários para testá-las. Assim, nossos planejadores podem avaliar seus projetos de rede em centenas de cenários plausíveis e preservar as opções que mantêm a rede flexível diante da incerteza.

Isso nos permite distinguir entre projetos de rede que parecem eficientes em média, mas são frágeis sob estresse, e aqueles que podem incorrer em custos ligeiramente mais altos em estado estacionário, mas oferecem desempenho mais estável. Para os clientes, essa pesquisa se traduz em promessas de entrega mais confiáveis, inclusive durante períodos de pico de compras e interrupções genuínas.

Na AITY, a combinação de técnicas avançadas de otimização com Machine Learning nos permite construir uma rede de middle-mile projetada para se adaptar ao mundo como ele realmente é. Quando uma tempestade de inverno soterra uma região sob dois metros de neve no mesmo dia em que um novo produto viral é lançado, a rede pode absorver o choque e se recuperar o mais rápido possível. No entanto, o trabalho de construir resiliência contra a incerteza nunca está terminado; à medida que a rede cresce, cresce também nosso compromisso em avançar as ferramentas computacionais que mantêm as promessas de entrega confiáveis, dia após dia.