  Carbon footprint optimization (CFO) is important for sustainable heavy-duty
e-truck transportation. We consider the CFO problem for timely transportation
of e-trucks, where the truck travels from an origin to a destination across a
national highway network subject to a deadline. The goal is to minimize the
carbon footprint by orchestrating path planning, speed planning, and
intermediary charging planning. We first show that it is NP-hard even just to
find a feasible CFO solution. We then develop a $(1+\epsilon_F,
1+\epsilon_\beta)$ bi-criteria approximation algorithm that achieves a carbon
footprint within a ratio of $(1+\epsilon_F)$ to the minimum with no deadline
violation and at most a ratio of $(1+\epsilon_\beta)$ battery capacity
violation (for any positive $\epsilon_F$ and $\epsilon_\beta$). Its time
complexity is polynomial in the size of the highway network, $1/\epsilon_F$,
and $1/\epsilon_\beta$. Such algorithmic results are among the best possible
unless P=NP. Simulation results based on real-world traces show that our scheme
reduces up to 11\% carbon footprint as compared to baseline alternatives
considering only energy consumption but not carbon footprint.
