Efficient Package Delivery Task Assignment for Truck and High Capacity Drone

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.