A two-stage stochastic optimization model for synchronized two-echelon routing problems

Resumo Técnico: Um Modelo de Otimização Estocástica de Dois Estágios para Problemas de Roteamento Sincronizado de Dois Echelons

Definição do Problema
Este estudo aborda a complexidade da incerteza na logística urbana, focando especificamente em sistemas de Transporte Integrado Baseado em Água e Terra (IWLT). O problema central é o Problema de Roteamento de Veículos de Múltiplas Viagens com Sincronização de Satélite de Dois Echelons (2E-MVRP-SS). Neste sistema, Veículos de Carga Elétricos Leves (LEFVs) operam no primeiro echelon (ruas) para coletar mercadorias dos clientes e transferi-las para embarcações (segundo echelon) em nós satélites. O sistema opera sem opções de armazenamento nos satélites, exigindo uma sincronização espaço-temporal rigorosa entre os LEFVs e as embarcações.

O principal desafio abordado é a propagação de atrasos causados por tempos de espera (lead times) incertos de transbordo nos satélites. Essas incertezas, decorrentes de fatores regionais como congestionamentos de tráfego ou variações operacionais, podem interromper operações sincronizadas, levando ao atraso no atendimento ao cliente, aumento dos custos operacionais e redução da confiabilidade. O estudo visa especificamente cenários de logística reversa (ex: coleta de resíduos, devoluções) onde o serviço oportuno é crítico para minimizar custos de inventário e inconvenientes ao cliente.

Metodologia
Os autores propõem uma estrutura de otimização estocástica de dois estágios com um problema de recurso de números inteiros mistos para gerenciar essas incertezas.

1. Formulação de Dois Estágios:

   • Primeiro Estágio (Problema Mestre): As decisões são tomadas em relação às rotas dos LEFVs e à atribuição de tarefas de transferência aos satélites antes da ocorrência dos atrasos. Este estágio prioriza tempos de serviço confiáveis para as coletas. O modelo assume que os LEFVs visitam o satélite mais próximo como uma aproximação inicial.
   • Segundo Estágio (Recurso/Subproblema): Uma vez que cenários específicos de atraso são realizados, ações corretivas são tomadas. Isso envolve a realocação de operações de transbordo para diferentes satélites e o re-roteamento das embarcações para mitigar o impacto dos atrasos. Os cronogramas dos LEFVs para o serviço ao cliente permanecem fixos para honrar os tempos prometidos, mas a logística de nível de água é reotimizada.

2. Abordagem Algorítmica:

   • Para lidar com a não convexidade da função de custo do segundo estágio e a natureza de números inteiros mistos do problema, os autores utilizam um método L-shaped adaptado com cortes de Benders combinatórios.
   • O algoritmo itera entre um problema mestre relaxado e subproblemas para cada cenário.
   • Cortes de viabilidade garantem que as decisões do primeiro estágio permitam soluções viáveis no segundo estágio.
   • Cortes de otimalidade aproximam o custo esperado do segundo estágio.
   • Uma abordagem de amostragem baseada em cenários é usada para representar incertezas regionais. Os atrasos nos satélites são modelados como variáveis com distribuição normal, discretizadas em um conjunto finito de cenários ($N$) para garantir a tratabilidade computacional enquanto mantêm a estabilidade.

3. Configuração Experimental:

   • O modelo foi testado em pequenas instâncias de rede (10 nós de coleta, 4 satélites) derivadas de instâncias modificadas de Solomon VRPTW.
   • Dois designs de sistema foram comparados: 2E-Flexible (as embarcações atuam como depósitos móveis, sincronizados com os LEFVs) e 2E-Stationary (locais fixos para as embarcações).
   • O desempenho foi avaliado contra uma linha de base determinística (sem atrasos) e uma abordagem estocástica de dois estágios.

Principais Contribuições

• Modelagem Inovadora de Sincronização: Este é o primeiro estudo a abordar os impactos dos atrasos nos satélites na sincronização de veículos em um sistema de dois echelons com capacidade de armazenamento nula, um cenário que exige alta coordenação espaço-temporal.
• Estrutura de Recurso Estocástico: O artigo propõe um modelo de programação estocástica de dois estágios com recurso de números inteiros mistos especificamente para o 2E-MVRP-SS. Ele utiliza cortes de Benders combinatórios dentro de um método de enumeração para lidar com a não convexidade do segundo estágio.
• Análise Comparativa de Flexibilidade: O estudo fornece uma comparação quantitativa entre sistemas de transporte flexíveis (embarcações móveis) e sistemas estacionários sob incerteza, demonstrando o valor da flexibilidade na mitigação da propagação de atrasos.

Resultos

• Redução de Custos: O modelo de programação estocástica proposto reduziu os custos totais esperados em 37% em todas as instâncias em comparação com uma abordagem determinística que assume ausência de atrasos.
• Estabilidade de Cenários: A abordagem de geração de cenários demonstrou estabilidade; a variância dos cenários dentro da amostra diminuiu conforme o número de cenários aumentava, estabilizando-se em torno de 30 cenários.
• Impacto da Topologia da Rede:
  • Para redes de demanda Agrupadas (C), o sistema integrado manteve a eficiência com um aumento de custo mínimo (próximo a 0%) sob incerteza.
  • Para redes Aleatórias (R), a abordagem estocástica alcançou as maiores economias em comparação com estratégias determinísticas, reduzindo os custos esperados em até 43% em instâncias específicas ao localizar melhor os locais de coleta sensíveis a atrasos.
• Desempenho do Sistema (Flexível vs. Estacionário):
  • O sistema 2E-Flexible superou significativamente o sistema 2E-Stationary em termos de confiabilidade e participação modal.
  • Sob incerteza, o sistema estacionário experimentou um aumento acentuado nos tempos de viagem nas ruas e no atraso (ex: o atraso aumentou para 26 unidades de tempo em instâncias RC), enquanto o sistema flexível manteve o atraso baixo (9 unidades de tempo) e manteve uma participação modal mais equilibrada entre rodovia e água.
  • O sistema flexível mitigou efetivamente o risco de aumento nos custos de viagem nas ruas, demonstrando que relocar unidades de armazenamento (ou, neste caso, pontos de transbordo) não pode igualar o desempenho de serviços de navegação flexíveis em termos de congestionamento e confiabilidade.

Significância e Alegações
O artigo afirma que incorporar a incerteza no planejamento offline é essencial para a confiabilidade e o custo-benefício da logística urbana multimodal, particularmente em contextos onde a competição pelo espaço urbano limita as opções de armazenamento. O estudo demonstra que sistemas flexíveis, onde as embarcações atuam como depósitos móveis sincronizados com os LEFVs, oferecem resistência superior contra atrasos de transbordo em comparação com sistemas de localização fixa.

Os autores concluem que, embora o modelo proposto seja computacionalmente intensivo, os ganhos observados em pequenas instâncias sugerem que a otimização estocástica pode melhorar significativamente a confiabilidade do serviço e reduzir a participação modal "verde" (uso de rodovias) na logística urbana. Eles observam que trabalhos futuros podem utilizar a estrutura de enumeração e precificação proposta para desenvolver heurísticas para problemas de grande escala, mas o estudo atual foca na validação da estrutura teórica e dos benefícios da flexibilidade em redes pequenas e solucionáveis.