Publication
We study the problem of minimizing fuel consumption of a heavy-duty truck traveling across the national highway network subject to a hard deadline. We focus on a real-world setting that traversing a road segment is subject to variable speed ranges due to dynamic traffic conditions. The consideration of dynamic traffic conditions not only differentiates our work from existing ones but also allows us to leverage opportunistic driving to improve fuel efficiency. The idea is for the truck to strategically wait (e.g., at highway rest areas) for benign traffic conditions, so as to traverse subsequent road segments at favorable speeds for saving fuel. We observe that traffic conditions and thus speed ranges are mostly stationary within certain duration of the day, and we term them as phases. We formulate the fuel consumption minimization problem under phased speed ranges, considering path planning, speed planning, and opportunistic driving. We prove that the problem is NP-hard, and develop a dual-subgradient algorithm for large-/national-scale instances. We characterize conditions under which the algorithm generates an optimal solution. We carry out simulations based on real-world traces over the US highway system. The results show that our scheme saves up to fuel than a shortest-path based alternative, of which opportunistic driving contributes . Meanwhile, opportunistic driving also reduces driving time by as compared to only optimizing path planning and speed planning. As such, it offers a desirable design option to simultaneously reduce fuel consumption and hours of driving. Last but not least, our results highlight a perhaps surprising observation that dynamic traffic conditions can be exploited to achieve fuel savings even larger than those under stationary traffic conditions.