  We study the carbon footprint optimization (CFO) of a heavy-duty e-truck
traveling from an origin to a destination across a national highway network
subject to a hard deadline, by optimizing path planning, speed planning, and
intermediary charging planning. Such a 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. Indeed, we show that the CFO problem is NP-hard. As a key
contribution, we show that under practical settings it is equivalent to finding
a generalized restricted shortest path on a stage-expanded graph, which extends
the original transportation graph to model charging options. Compared to
alternative approaches, our formulation incurs low model complexity and reveals
a problem structure useful for algorithm design. We exploit the insights to
develop an efficient dual-subgradient algorithm that always converges. As
another major contribution, we prove that (i) each iteration only incurs
polynomial-time complexity, albeit it requires solving an integer charging
planning problem optimally, and (ii) the algorithm generates optimal results if
a condition is met and solutions with bounded optimality loss otherwise.
Extensive simulations based on real-world traces show that our scheme reduces
up to 28% carbon footprint compared to baseline alternatives. The results also
demonstrate that e-truck reduces 56% carbon footprint than internal combustion
engine trucks.
