Minimizing Emission and Carbon Footprint for Timely Heavy-Duty Truck Transportation

Abstract

Heavy-duty trucks are essential for our economy, underpinning our economic activity and daily life. Meanwhile, they are also major contributors to emissions, including Carbon Dioxide (CO2) and Nitrogen Oxides (NOx). In this thesis, we study how to reduce the emissions of the heavy-duty trucking industry via optimizing timely truck transportation -- a critical operation module. This involves strategic path, speed, and charging planning, which is complex due to tight delivery schedules and combinatorial challenges. In particular, we study the problem of (i) minimizing the emissions for conventional internal combustion engine (ICE) trucks and (ii) minimizing the carbon footprint for electric trucks (E-Trucks). Both problems are NP-hard and challenging to solve.

We first consider the problem of minimizing the emission of an ICE truck transporting freight between two locations subject to a hard deadline constraint. The truck is equipped with a multi-speed transmission and a modern combustion engine that intelligently switches among multiple fuel injection strategies. Our objective is to minimize emissions by optimizing both path and speed planning for trucks. This emission minimization problem, while pervasive in practice, is challenging due to (i) non-convex and discontinuous emission rate functions from fuel injection and gear changes, and (ii) the hard deadline constraint. We identify special structures of the emission rate functions and develop an efficient algorithm to solve the emission minimization problem on the scale of national highway systems. Our extensive simulations on the U.S. highway system show that our solution reduces up to 46% NOx emissions compared to the commonly adopted fastest path approach.

We then proceed to study the problem for E-Trucks. The problem aims to minimize the carbon footprint of an E-Truck traveling from an origin to a destination subject to a hard deadline by optimizing path planning, speed planning, and intermediary charging planning. Such a carbon footprint optimization (CFO) problem is essential for carbon-friendly E-Truck operations. However, it is notoriously challenging to solve due to (i) the hard deadline constraint, (ii) positive battery state-of-charge constraints, (iii) non-convex carbon footprint objective, and (iv) enormous geographical and temporal charging options with diverse carbon intensity. We show that it is NP-hard even just to find a feasible solution. We develop a (1+ε_F,1+ε_b) bi-criteria approximation algorithm that achieves a carbon footprint within a ratio of (1+ε_F) to the minimum with no deadline violation and at most a ratio of (1+ε_b) battery capacity violation (for any positive ε_F and ε_b). Its time complexity is polynomial in the size of the highway network, 1/ε_F, and 1/ ε_b. While achieving highly preferred theoretical performance guarantees, the proposed approximation algorithm still suffers from a high computational burden. We then introduce a novel stage-expanded graph formulation that incurs low complexity and reveals a useful problem structure. We exploit the structural insights to design another efficient algorithm that is applicable to the national-scale highway network. 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 significantly accelerates transportation decarbonization, offering a powerful tool in the fight against climate change.

Overall, we provide efficient methods for minimizing the emissions of ICE trucks and the carbon footprint of E-Trucks in timely transportation tasks. We believe implementing our methods will significantly advance the trucking industry towards greater environmental sustainability.

Date of Award	15 Sept 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minghua CHEN (Supervisor)