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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Energy-Efficient Timely Truck Transportation for Geographically-Dispersed Tasks


    Contributors:
    Liu, Qingyu (author) / Zeng, Haibo (author) / Chen, Minghua (author)


    Publication date :

    2020-12-01


    Size :

    2207463 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Energy-Efficient Timely Transportation of Long-Haul Heavy-Duty Trucks

    Deng, Lei / Hajiesmaili, Mohammad H. / Chen, Minghua et al. | IEEE | 2018




    Measuring dissimilarity of geographically dispersed space–time paths

    Vanhulsel, Marlies / Beckx, Carolien / Janssens, Davy et al. | Online Contents | 2010


    Measuring dissimilarity of geographically dispersed space–time paths

    Vanhulsel, Marlies / Beckx, Carolien / Janssens, Davy et al. | Online Contents | 2010