Energy-Efficient Timely Truck Transportation for Geographically-Dispersed Tasks

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)5148-5159
Number of pages12
Journal / PublicationIEEE Transactions on Intelligent Transportation Systems
Issue number12
Online published31 Oct 2019
Publication statusPublished - Dec 2020
Externally publishedYes


Title9th ACM International Conference on Future Energy Systems (ACM e-Energy 2018)
Period12 - 15 June 2018


We consider a common truck operation scenario, where a long-haul heavy-duty truck drives across a national highway system to fulfill multiple geographically-dispersed tasks in a specific order. The objective is to minimize the total fuel consumption subject to the pickup and delivery time window constraints of individual tasks, by jointly optimizing task execution times, path planning, and speed planning. The need to coordinate execution times for multiple tasks differentiates our study from existing ones on single task. We first prove that our problem is NP-hard. Moreover, it is uniquely challenging to solve our problem, as we further show that optimizing task execution times is a non-convex puzzle. We then exploit the problem structure to develop (i) a Fully-Polynomial-Time Approximation Scheme (FPTAS), and (ii) a fast and efficient heuristic algorithm, called SPEED (Sub-gradient-based Price-driven Energy-Efficient Delivery). We characterize sufficient conditions under which SPEED generates an optimal solution, and derive an optimality gap for SPEED when the conditions are not satisfied. We evaluate the practical performances of our solutions using real-world traces over the US national highway. We observe that our solutions can save up to 22% fuel as compared to the fastest-/shortest- path baselines, and up to 10% fuel than a conceivable alternative generalized from the state-of-the-art single-task algorithm. The fuel saving is robust to the number of tasks to be fulfilled. Simulations also show that our algorithms always obtain close-to-optimal solutions and meet time window constraints for all feasible problem instances. In comparison, the conceivable alternative fails to meet time window constraints for up to 45% of the instances.

Research Area(s)

  • Energy-efficient transportation, timely delivery, task execution times optimization, path planning, speed planning