Learning to Route Electric Trucks Under Operational Uncertainty

1. Definição do Problema: O Problema de Roteamento de Frotas de Caminhões Elétricos (eTFRP)

O artigo aborda o Problema de Roteamento de Frotas de Caminhões Elétricos (eTFRP), uma extensão complexa do clássico Problema de Roteamento de Veículos (VRP) adaptada para caminhões elétricos de grande porte. Diferentemente dos problemas de roteamento padrão, o eTFRP envolve um desafio acoplado de logística e gestão de energia caracterizado por:

• Infraestrutura de Carregamento Compartilhada: Múltiplos caminhões competem por portos de carregamento limitados em estações com capacidade finita, levando a atrasos endógenos de fila.
• Incerteza Operacional: Tempos de viagem, consumo de energia e durações de descarga são estocásticos (modelados como distribuições gaussianas truncadas), influenciados por congestionamento de tráfego e condições climáticas.
• Dinâmicas de Carregamento Realistas: O problema incorpora o comportamento não linear de carregamento rápido em corrente contínua (CCCV – Corrente Constante–Tensão Constante), onde a potência de carregamento diminui à medida que o Estado de Carga (SoC) da bateria aumenta, em vez de assumir um carregamento linear.
• Acoplamento em Nível de Frota: As decisões são interdependentes; a viabilidade da rota de um caminhão depende do comportamento de outros caminhões na frota (por exemplo, se uma estação está congestionada por outros).

O objetivo é minimizar o tempo total esperado para toda a frota completar todas as entregas, incluindo tempos de viagem, carregamento, espera e descarga, garantindo simultaneamente a viabilidade energética (evitando o esgotamento da bateria).

2. Metodologia

Os autores propõem um framework baseado em aprendizado utilizando Aprendizado por Reforço (RL) para resolver o eTFRP. Os componentes centrais são:

A. Formulação do Problema

O problema é modelado como um Processo de Decisão Semi-Markoviano (SMDP) Orientado a Eventos.

• Espaço de Estados: As decisões são tomadas apenas quando um caminhão entra em um estado "Aguardando Ação" (por exemplo, após chegar a um nó). O estado é representado como um grafo heterogêneo contendo três tipos de nós: Caminhões, Pontos de Entrega e Estações de Carregamento.
• Espaço de Ações: O espaço de ações é variável e dependente do estado. Inclui navegar para uma entrega ou carregador, ou selecionar uma duração de carregamento. Para garantir a viabilidade operacional, uma máscara de ação baseada em regras é aplicada para restringir a política apenas a ações admissíveis (por exemplo, impedindo a navegação para um destino se a energia da bateria for insuficiente).
• Função de Recompensa: Uma recompensa baseada no tempo é utilizada para minimizar o tempo operacional total, com penalidades por falha (esgotamento da bateria) e bônus por entregas concluídas.

B. Arquitetura GraphPPO

Os autores introduzem o GraphPPO, um algoritmo de Otimização de Política Proximal (PPO) baseado em Redes Neurais de Grafos (GNN).

• Codificador de Estado: Utiliza um Codificador de Grafo Heterogêneo com camadas de Hetero-Interação para processar o grafo de estado do sistema. Isso permite que o modelo capture interações entre caminhões, infraestrutura e entregas, mantendo-se invariante ao número de entidades (escalabilidade).
• Codificador de Ações: O conjunto de ações viáveis também é codificado como um grafo. A rede ator pontua esses nós de ação, condicionada ao embedding do estado global, para produzir uma distribuição de probabilidade sobre as ações viáveis.
• Treinamento: O modelo é treinado usando o algoritmo PPO com Estimação de Vantagem Generalizada (GAE), otimizando um objetivo substituto truncado para garantir atualizações de política estáveis.

C. Ambiente de Simulação

Um ambiente de simulação orientado a eventos personalizado (construído sobre Gymnasium) foi desenvolvido para suportar o treinamento e a comparação. Ele simula:

• Viagem e consumo de energia estocásticos.
• Curvas de carregamento CCCV não lineares.
• Filas de Primeiro a Chegar, Primeiro a Ser Atendido (FCFS) nas estações de carregamento.
• Dados de rede viária do mundo real da Califórnia.

3. Principais Contribuições

1. Formulação Realista do Problema: O artigo formula o eTFRP como um SMDP orientado a eventos que modela explicitamente recursos de carregamento compartilhados, viagem/consumo de energia estocásticos e comportamento de carregamento não linear, indo além das abstrações simplificadas encontradas na literatura anterior.
2. RL Consciente de Viabilidade Baseado em Grafos: A introdução do GraphPPO, que combina GNNs com uma máscara de viabilidade de ação explícita. Isso garante que o agente de RL aprenda políticas que são operacionalmente válidas (por exemplo, respeitando restrições de bateria e capacidade da estação) sem depender de mecanismos de reparo post-hoc.
3. Comparação Abrangente: O desenvolvimento de um ambiente de simulação unificado permite a comparação direta entre a abordagem baseada em aprendizado, otimização matemática (MILP) e baselines metaheurísticas sob suposições estocásticas consistentes.
4. Escalabilidade e Generalização: O framework demonstra a capacidade de escalar de cenários de caminhão único para grandes frotas (até 100 caminhões) e mostra fortes capacidades de generalização zero-shot.

4. Resultados Experimentais

O estudo avaliou o GraphPPO contra Otimização Matemática (Mat. Opt.), uma Heurística, PPO genérico e MaskPPO (PPO com mascaramento de ação, mas sem estrutura de grafo) em vários tamanhos de frota (de 1 a 100 caminhões).

• Desempenho vs. Tamanho da Frota:

  • GraphPPO alcançou consistentemente desempenho quase ótimo (recompensa normalizada 0,987–1,005) em todos os tamanhos de frota, mantendo altas taxas de sucesso (por exemplo, 76,5% de sucesso para 50 caminhões vs. 0% para PPO genérico).
  • PPO Genérico falhou completamente em configurações maiores (0% de taxa de sucesso) devido à incapacidade de lidar com restrições complexas de viabilidade.
  • MaskPPO performou bem em configurações pequenas, mas degradou significativamente à medida que o tamanho da frota aumentava (a taxa de sucesso caiu para 2% para 100 caminhões), destacando a necessidade da representação de estado baseada em grafos para capturar o congestionamento em nível de frota.
  • Mat. Opt. forneceu uma base sólida, mas lutou com escalabilidade e tempo computacional em configurações grandes e estocásticas.

• Generalização Zero-Shot:

  • Uma política treinada apenas na configuração de 100 caminhões (100T3S) foi aplicada a configurações menores e maiores sem retreinamento.
  • A política generalizou efetivamente, frequentemente superando a base conservadora de Mat. Opt. em cenários grandes e congestionados (taxas de vitória >70% para 50–100 caminhões).

• eVRP de Caminhão Único:

  • Em uma configuração de caminhão único (1T20S), o GraphPPO alcançou recompensas quase ótimas (99,7% da Mat. Opt.) com uma redução massiva no tempo de computação (0,8 segundos vs. 233 segundos para Mat. Opt.).

• Insights Operacionais:

  • O GraphPPO utilizou as baterias com mais eficiência do que a heurística (SoC residual mais baixo) e gerenciou as filas de carregamento melhor do que o MaskPPO, resultando em menores tempos totais de espera.

5. Significado

Este artigo faz uma contribuição significativa para o campo da logística verde e gestão de frotas autônomas:

• Ponteando a Lacuna: Ele conecta com sucesso a otimalidade teórica da programação matemática com a escalabilidade dos métodos baseados em aprendizado.
• Gerenciamento de Incerteza: Demonstra que o RL pode gerenciar efetivamente incertezas complexas e acopladas (tráfego, energia, filas) que tornam heurísticas tradicionais e otimização estática ineficazes em tempo real.
• Implantação Prática: O framework proposto oferece uma solução prática para operações de frete elétrico do mundo real, capaz de tomar decisões de roteamento de alta qualidade e viáveis em tempo real (inferência subsegundo), mesmo para frotas grandes e congestionadas.
• Impacto Futuro: O trabalho estabelece as bases para integrar restrições da rede elétrica, preços dinâmicos e sistemas de reserva em logística baseada em aprendizado, avançando a descarbonização do transporte de carga.