Follow the Sun and Go with the Wind: Carbon Footprint Optimized Timely E-Truck Transportation

Junyan Su, QiuLin Lin, Minghua Chen
City University of Hong Kong
ACM e-Energy 2023
DOI PDF arXiv

Highlights:

  • Best Paper Award at ACM e-Energy 2023
  • We study an important yet challenging problem, namely the carbon footprint optimization problem for e-trucks.
  • We provide a novel problem formulation, which incurs low model complexity and reveals a useful problem structure.
  • We develop an efficient algorithm with performance guarantee.
  • Key idea: The problem is easy when there is no charging, it is also easy when there is only charging. Our idea is to separate the combined challenging problem into those two easy subproblems and combine their solutions.
  • Carbon-optimized solutions save up to 28% carbon footprint compared to baseline alternatives.

Abstract

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.

An illustration of carbon-optimized and energy-optimized solutions from Dallas, TX to Carmel, IN. In the figure, the shaded area represents the period of charging process. The carbon-optimized solution saves 60% carbon as compared to a fastest path and saves 35% carbon as compared to the energy-optimized solution.

Slides:

BibTeX

@inproceedings{su2023follow,
    author = {Su, Junyan and Lin, Qiulin and Chen, Minghua},
    title = {Follow the Sun and Go with the Wind: Carbon Footprint Optimized Timely E-Truck Transportation},
    year = {2023},
    booktitle = {Proceedings of the 14th ACM International Conference on Future Energy Systems},
    pages = {159–171},
    numpages = {13},
    location = {Orlando, FL, USA},
    series = {e-Energy '23}
}