This paper investigates the task assignment problem for one truck and one drone to deliver packages to a group of customer locations. The truck, carrying a large number of packages, can only travel between a group of prescribed street-stopping/parking locations to replenish the drone with both packages and batteries. The drone can carry multiple packages simultaneously to serve customers sequentially within its limited operation range. The objective is to reduce the amount of time it takes the drone to deliver the necessary package to the last customer while taking into account its operation range and loading capacity. First, the package delivery task assignment problem is shown to be an NP-hard problem, which guides us to design heuristic task assignment algorithms. Secondly, based on graph theory, a lower bound on the minimum time for the drone to serve the last customer is achieved to approximately evaluate the performance of a task assignment algorithm. Third, several decoupled heuristic algorithms are designed to sequentially plan the routes for the drone and the truck. Two coupled heuristic algorithms, namely the improved nearest inserting algorithm and the improved minimum marginal-cost algorithm, are proposed to simultaneously plan the routes for the drone and the truck. Numerical simulations demonstrate that the improved minimum marginal-cost algorithm reduces the total service time by 14.93% and 14.06% on average compared with the existing decoupled two-phase algorithm TPA and the coupled greedy algorithm, respectively. In the best case, it reduces the total service time by 41.71% and 40.11% compared with the TPA and the coupled greedy algorithm, respectively.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Efficient Package Delivery Task Assignment for Truck and High Capacity Drone


    Contributors:
    Bai, Xiaoshan (author) / Ye, Youqiang (author) / Zhang, Bo (author) / Ge, Shuzhi Sam (author)

    Published in:

    Publication date :

    2023-11-01


    Size :

    3514389 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Synchronized Truck and Drone Routing in Package Delivery Logistics

    Das, Dyutimoy Nirupam / Sewani, Rohan / Wang, Junwei et al. | IEEE | 2021


    Drone to drone communication and task assignment

    MANOUCHEHRI ALI REZA / CHUNDURY UDAYA / TRUONG VY | European Patent Office | 2024

    Free access

    Energy-Aware Task Allocation for Drone Package Delivery

    Samiei, Arezoo / Arif, Md Arifin / Karpinski, Trevor et al. | AIAA | 2022


    Energy-Aware Task Allocation for Drone Package Delivery

    Samiei, Arezoo / Arif, Arifin / Karpinski, Trevor et al. | TIBKAT | 2022


    Package for drone delivery

    PRAGER ANDRE / SOPPER CLARK / LISKE KYLE A | European Patent Office | 2018

    Free access