Opportunity
Heavy-duty trucks are a critical component of the freight economy, responsible for over 72% of domestic tonnage shipped in the United States. However, they are also a major source of CO₂ emissions, contributing approximately 25% of the transportation sector's emissions despite constituting only 4% of the vehicle population. Electrifying heavy-duty trucks (e-trucks) presents a promising path to decarbonization, offering benefits like zero tailpipe emissions and higher energy efficiency. Nevertheless, a significant challenge remains: while e-trucks produce no direct emissions during operation, the electricity used for charging incurs a carbon footprint based on its generation source (e.g., coal, natural gas, renewables). This footprint varies significantly across locations and times due to the intermittent nature of renewable energy sources. Existing route and logistics planning methods for trucks primarily focus on minimizing travel time, energy consumption, or cost, but they fail to jointly optimize path selection, speed profiles, and intermediary charging schedules with the explicit goal of minimizing the total carbon footprint. This gap is critical because suboptimal planning can negate the environmental benefits of electrification. Furthermore, planning must satisfy practical constraints like hard delivery deadlines and battery state-of-charge (SoC) limits to prevent depletion, making the problem combinatorially complex and NP-hard. There is a pressing need for an integrated optimization technique that can navigate the spatial-temporal diversity of grid carbon intensity to truly minimize the environmental impact of e-truck freight transportation.
Technology
This patent discloses a novel computer-implemented method for the joint Carbon Footprint Optimization (CFO) of an electric truck's journey. The core innovation is a "stage-expanded graph" formulation that models the trip from origin to destination, incorporating decisions for route planning, speed planning on each road segment, and intermediary charging station selection and scheduling, all under a hard deadline and battery SoC constraints. The stage-expanded graph creates multiple copies (stages) of the transportation network nodes, where each stage represents how many times the vehicle has been charged so far. This structure elegantly embeds crucial information—arrival time and arrival SoC at each potential charging point—which is essential for accurately evaluating the time-varying carbon footprint of electricity consumption at different locations. The method then formulates the CFO problem as finding an optimal path on this expanded graph. To solve this complex, non-convex, and NP-hard problem efficiently, the invention employs a dual-subgradient algorithm. This algorithm leverages Lagrangian relaxation to decompose the main problem into smaller, manageable subproblems: one for optimizing speed on each road segment (a convex problem) and another for optimizing charging parameters (time, duration, SoC level) at each station (a low-dimensional non-convex problem solved via branch-and-bound). The outer problem of selecting the optimal path and charging stations is transformed into a shortest path problem on an auxiliary graph, solvable in polynomial time. This approach provides a computationally tractable solution with favorable theoretical guarantees, including convergence and a bounded optimality gap, enabling real-world application over large-scale national highway networks.
Advantages
- Holistic Carbon Minimization: Directly minimizes the total carbon footprint of an e-truck's journey, not just energy use or time, by exploiting spatial-temporal variations in grid carbon intensity.
- Integrated Optimization: Simultaneously co-optimizes three key decision spaces—route, speed, and charging plan—which are typically addressed separately or suboptimally.
- Computational Efficiency: The stage-expanded graph formulation and dual-based algorithm overcome the NP-hard complexity, offering polynomial-time iterations and scalability to large, real-world road networks.
- Theoretical Guarantees: The algorithm provides convergence guarantees and a posteriori bounds on optimality loss, ensuring solution quality.
- Practical Feasibility: Incorporates real-world constraints like hard deadlines, battery SoC limits (with a practical "conservative ratio" to simplify coupling), and nonlinear battery charging characteristics.
- Significant Environmental Benefit: Demonstrated to reduce carbon footprint by up to 28% compared to fastest-path strategies and by approximately 56% compared to internal combustion engine (ICE) trucks.
Applications
- E-Truck Fleet Management and Logistics: Providing optimal routing and charging instructions for freight companies operating electric heavy-duty trucks.
- On-Board Navigation Systems: Integration into advanced vehicle navigation systems for real-time, carbon-optimized trip planning for electric commercial vehicles.
- Freight Platform Optimization: Used by digital freight matching platforms (e.g., Uber Freight) to offer low-carbon shipping options and calculate eco-friendly routes for contracted jobs.
- Grid-Aware Charging Infrastructure Planning: Informing the placement and operation of charging stations by highlighting locations and times that maximize the use of low-carbon electricity.
- Policy and Incentive Design: Providing a tool for policymakers to model and incentivize carbon-optimal freight routing to meet decarbonization targets.
- Extension to Other Electric Vehicles: The methodology can be adapted for routing and scheduling of other large electric vehicles, such as buses or delivery vans.
