Learning to Route Electric Trucks Under Operational Uncertainty

1. Problem Definition: The Electric Truck Fleet Routing Problem (eTFRP)

The paper addresses the Electric Truck Fleet Routing Problem (eTFRP), a complex extension of the classic Vehicle Routing Problem (VRP) tailored for heavy-duty electric trucks. Unlike standard routing problems, eTFRP involves a coupled logistics and energy management challenge characterized by:

• Shared Charging Infrastructure: Multiple trucks compete for limited charging ports at stations with finite capacity, leading to endogenous queuing delays.
• Operational Uncertainty: Travel times, energy consumption, and unloading durations are stochastic (modeled as truncated Gaussian distributions), influenced by traffic congestion and weather.
• Realistic Charging Dynamics: The problem incorporates non-linear DC fast-charging behavior (Constant Current–Constant Voltage or CCCV), where charging power tapers as the battery State of Charge (SoC) increases, rather than assuming linear charging.
• Fleet-Level Coupling: Decisions are interdependent; a truck's route feasibility depends on the behavior of other trucks in the fleet (e.g., if a station is congested by others).

The objective is to minimize the expected total time for the entire fleet to complete all deliveries, including travel, charging, waiting, and unloading times, while ensuring energy feasibility (avoiding battery depletion).

2. Methodology

The authors propose a learning-based framework using Reinforcement Learning (RL) to solve the eTFRP. The core components are:

A. Problem Formulation

The problem is modeled as an Event-Driven Semi-Markov Decision Process (SMDP).

• State Space: Decisions are made only when a truck enters an "Action Pending" state (e.g., after arriving at a node). The state is represented as a heterogeneous graph containing three node types: Trucks, Delivery Points, and Charging Stations.
• Action Space: The action space is variable and state-dependent. It includes navigating to a delivery or charger, or selecting a charging duration. To ensure operational feasibility, a rule-based action mask is applied to restrict the policy to only admissible actions (e.g., preventing navigation to a destination if battery energy is insufficient).
• Reward Function: A time-based reward is used to minimize total operational time, with penalties for failure (battery depletion) and bonuses for completed deliveries.

B. GraphPPO Architecture

The authors introduce GraphPPO, a Graph Neural Network (GNN)-based Proximal Policy Optimization (PPO) algorithm.

• State Encoder: Uses a Heterogeneous Graph Encoder with Hetero-Interaction layers to process the system state graph. This allows the model to capture interactions between trucks, infrastructure, and deliveries while remaining invariant to the number of entities (scalability).
• Action Encoder: The feasible action set is also encoded as a graph. The actor network scores these action nodes, conditioned on the global state embedding, to produce a probability distribution over feasible actions.
• Training: The model is trained using the PPO algorithm with Generalized Advantage Estimation (GAE), optimizing a clipped surrogate objective to ensure stable policy updates.

C. Simulation Environment

A custom event-driven simulation environment (built on Gymnasium) was developed to support training and benchmarking. It simulates:

• Stochastic travel and energy consumption.
• Non-linear CCCV charging curves.
• First-Come-First-Served (FCFS) queuing at charging stations.
• Real-world road network data from California.

3. Key Contributions

1. Realistic Problem Formulation: The paper formulates eTFRP as an event-driven SMDP that explicitly models shared charging resources, stochastic travel/energy, and non-linear charging behavior, moving beyond simplified abstractions found in prior literature.
2. Graph-Based Feasibility-Aware RL: The introduction of GraphPPO, which combines GNNs with an explicit action feasibility mask. This ensures that the RL agent learns policies that are operationally valid (e.g., respecting battery constraints and station capacity) without relying on post-hoc repair mechanisms.
3. Comprehensive Benchmarking: The development of a unified simulation environment allows for direct comparison between the learning-based approach, mathematical optimization (MILP), and metaheuristic baselines under consistent stochastic assumptions.
4. Scalability and Generalization: The framework demonstrates the ability to scale from single-truck to large-fleet scenarios (up to 100 trucks) and shows strong zero-shot generalization capabilities.

4. Experimental Results

The study evaluated GraphPPO against Mathematical Optimization (Math. Opt.), a Heuristic, generic PPO, and MaskPPO (PPO with action masking but no graph structure) across various fleet sizes (1 to 100 trucks).

• Performance vs. Fleet Size:

  • GraphPPO consistently achieved near-optimal performance (normalized reward 0.987–1.005) across all fleet sizes, maintaining high success rates (e.g., 76.5% success for 50 trucks vs. 0% for generic PPO).
  • Generic PPO failed completely in larger settings (0% success rate) due to the inability to handle complex feasibility constraints.
  • MaskPPO performed well in small settings but degraded significantly as fleet size increased (success rate dropped to 2% for 100 trucks), highlighting the necessity of the graph-based state representation for capturing fleet-level congestion.
  • Math. Opt. provided a strong baseline but struggled with scalability and computational time in large, stochastic settings.

• Zero-Shot Generalization:

  • A policy trained only on the 100-truck setting (100T3S) was applied to smaller and larger configurations without retraining.
  • The policy generalized effectively, often outperforming the conservative Math. Opt. benchmark in large, congested scenarios (win rates >70% for 50–100 trucks).

• Single-Truck eVRP:

  • In a single-truck setting (1T20S), GraphPPO achieved near-optimal rewards (99.7% of Math. Opt.) with a massive reduction in computation time (0.8 seconds vs. 233 seconds for Math. Opt.).

• Operational Insights:

  • GraphPPO utilized batteries more efficiently than the heuristic (lower residual SoC) and managed charging queues better than MaskPPO, resulting in lower total waiting times.

5. Significance

This paper makes a significant contribution to the field of green logistics and autonomous fleet management:

• Bridging the Gap: It successfully bridges the gap between the theoretical optimality of mathematical programming and the scalability of learning-based methods.
• Handling Uncertainty: It demonstrates that RL can effectively manage complex, coupled uncertainties (traffic, energy, queuing) that render traditional heuristics and static optimization ineffective in real-time.
• Practical Deployment: The proposed framework offers a practical solution for real-world electric freight operations, capable of making high-quality, feasible routing decisions in real-time (sub-second inference) even for large, congested fleets.
• Future Impact: The work lays the groundwork for integrating grid constraints, dynamic pricing, and reservation systems into learning-based logistics, advancing the decarbonization of freight transportation.