Publications

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_β) 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_β) battery capacity violation (for any positive \epsilon_F and \epsilon_β). Its time complexity is polynomial in the size of the highway network, 1/\epsilon_F, and 1/\epsilon_β. 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.

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.

We implement a new version of E2Pilot, the first energy-efficient navigation system for long-haul timely truck transportation with fast response time and user-friendly interfaces. Given the origin, destination, and delivery time window, E2Pilot provides the path and speed instructions shown on the user interfaces for the truck drivers to transport freights on time with minimum fuel consumption. E2Pilot has two user interfaces: a publicly available website, and a GPS-like smartphone application that provides in-place driving instructions along with off-route detection and re-routing.

We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of \ln θ + 1 if N≤\ln θ + 1, where N is the number of inventories and θ represents the revenue function uncertainty; it attains a CR of 1/[1-e^-1/(\lnθ+1) ] in [\ln θ +1, \ln θ +2) otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.

We carry out a comparative study of energy consumption of the conventional internal combustion truck and the modern electric truck, traveling from origin to destination over the national highway subject to a hard deadline. We focus on understanding energy saving of the latter over the former and key contributing factors. Our study is unique in that (i) it is based on extensive simulations using real-world data over the U.S. highway system, and (ii) we factor in the power system energy-conversion efficiency when calculating the energy consumption of electric trucks for fair comparison. The results show that on average the electric truck save 10% energy as compared to the internal combustion truck, and this saving will improve as power systems incorporate more renewable generation. Furthermore, the energy saving mainly comes from the energy efficiency of electric motors, and other electric-truck features, e.g., regenerative breaking, only have minor contributions.