TY - GEN
T1 - Energy-Efficient Timely Transportation of Long-Haul Heavy-Duty Trucks
AU - Deng, Lei
AU - Hajiesmaili, Mohammad H.
AU - Chen, Minghua
AU - Zeng, Haibo
PY - 2016/6
Y1 - 2016/6
N2 - We consider a timely transportation problem where a heavyduty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our 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 + ϵ with a network-size induced complexity of O(mn2/ϵ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.
AB - We consider a timely transportation problem where a heavyduty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our 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 + ϵ with a network-size induced complexity of O(mn2/ϵ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.
KW - Energy-efficient transportation
KW - Route planning
KW - Speed planning
KW - Timely delivery
UR - http://www.scopus.com/inward/record.url?scp=84979561902&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84979561902&origin=recordpage
U2 - 10.1145/2934328.2934338
DO - 10.1145/2934328.2934338
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781450343930
T3 - Proceedings of the International Conference on Future Energy Systems, e-Energy
SP - 96
EP - 107
BT - e-Energy '16: Proceedings of the Seventh International Conference on Future Energy Systems
PB - Association for Computing Machinery
T2 - 7th ACM International Conference on Future Energy Systems (ACM e-Energy 2016)
Y2 - 21 June 2016 through 24 June 2016
ER -