The US trucking industry collected $726.4 billion in gross freight revenues in 2015. This impressive number corresponds to 2.3x of the Hong Kong GDP and would rank 19 worldwide if measured against countries. Meanwhile, hauling 70.1% of all freight tonnage in the US, heavy-duty trucks consume 17.6% of energy in transportation sector (including trucks, airplanes, pipelines, and railways). This alerting observation, together with that fuel cost is the largest operating cost (34%) of truck owners/operators, makes it crucial to reduce fuel consumption for cost-effective and environment-friendly heavy-duty truck operation.
In this work, we consider a key yet under-explored problem in heavy-duty truck operation: timely transportation, where a heavy-duty truck travels between two locations across the national highway system subject to a hard deadline constraint. The objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-Complete; thus exact solution is computational prohibited unless P=NP. We then design a fully polynomial time approximation scheme (FPTAS) that attains an approximation ratio of 1+ epsilon with a network-size induced complexity of O(mn^2/epsilon^2), where m and n are the numbers of nodes and edges, respectively. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a fast heuristic solution with O(m+ n log n) complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of the practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared to a fastest path (resp. shortest path) algorithm adapted from common practice.
Overall, we believe that de-carbonizing heavy-duty truck operation is important for the sustainable development of the trucking industry. Our work serves as a call for participation.
This is a joint work with Lei Deng and Mohammad Hajiesmaili in CUHK and Haibo Zeng in Virginia Tech.
Minghua Chen received his B.Eng. and M.S. degrees from the Department of Electronic Engineering at Tsinghua University in 1999 and 2001, respectively. He received his Ph.D. degree from the Department of Electrical Engineering and Computer Sciences at University of California at Berkeley in 2006. He spent one year visiting Microsoft Research Redmond as a Postdoc Researcher. He joined the Department of Information Engineering, the Chinese University of Hong Kong, in 2007, where he currently is an Associate Professor. He is also currently an Adjunct Associate Professor in Tsinghua University, Institute of Interdisciplinary Information Sciences. He received the Eli Jury award from UC Berkeley in 2007 (presented to a graduate student or recent alumnus for outstanding achievement in the area of Systems, Communications, Control, or Signal Processing) and The Chinese University of Hong Kong Young Researcher Award in 2013. He also received several best paper awards, including the IEEE ICME Best Paper Award in 2009, the IEEE Transactions on Multimedia Prize Paper Award in 2009, and the ACM Multimedia Best Paper Award in 2012. He serves as a TPC Co-Chair of ACM e-Energy 2016 and a General Co-Chair of ACM e-Energy 2017. He is currently an Associate Editor of the IEEE/ACM Transactions on Networking. His recent research interests include energy systems (e.g., smart power grids and energy-efficient data centers), energy-efficient transportation, distributed optimization, multimedia networking, wireless networking, network coding, and delay-constrained network information flow.
