Energy-efficient routing for IoT-enabled multi-truck multi-drone pickup and delivery systems

In the context of Internet of Things (IoT), this paper investigates the task assignment problem in which multiple trucks cooperate with multiple drones to provide package pickup and delivery services to multiple dispersed customers. Each truck, constrained to travel between a set of fixed street/truck stopping points, can carry multiple drones where each one is capable of simultaneously picking up and delivering multiple packages within its loading capacity to provide last-mile package service. The objective is to enhance energy efficiency within this IoT-based delivery ecosystem by minimizing the total travel distance of multiple trucks and drones to serve all customers, which is a variant of the NP-hard vehicle routing problem. Key contributions are twofold. First, to evaluate the quality of an assignment solution from an energy efficiency perspective, a lower bound on the minimum total distance required to serve all the customers is constructed using graph theory. Second, a three-stage task assignment algorithm is proposed, which first uses the Prim clustering strategy to allocate a truck stopping point to serve each customer, then uses the Clarke and Wright algorithm and the minimum marginal cost algorithm to construct the initial routes of the trucks and drones, and finally utilizes an iterative improvement strategy to refine the routes. Numerical simulations show that the designed task assignment algorithm performs well, reducing the total travel distance by 4.36 % on average and 29.57 % in the best case, compared with the popular hybrid Clarke and Wright heuristic algorithm.