Abstract
Electrifying heavy-duty trucks is crucial for decarbonizing transportation, but maximizing their potential requires minimizing the carbon footprint of timely deliveries. This complex optimization task involves strategic path, speed, and charging planning, which traditional methods struggle to optimize at scale. We present a stage-expanded graph formulation that reduces complexity and reveals a useful problem structure. Our formulation naturally decomposes the problem into more tractable subproblems, allowing efficient coordination between routing and charging decisions, and maintains a manageable graph size. We exploit these structural insights to design an efficient algorithm with performance guarantees. Simulations using real-world data over the U.S. highway system demonstrate that our method complements the 36% carbon reduction from electrification with an additional 25% decrease, totaling a 61% reduction. Moreover, our carbon-optimized strategy, applicable to various truck types, can achieve comparable carbon reductions 9 years sooner than zero-emission truck adoption alone. This approach accelerates transportation decarbonization, offering a powerful tool in the fight against climate change.