Drone on-demand delivery routing problem considering order splitting and battery swapping

Abstract

The use of drone delivery has catalyzed technological innovation within the logistics industry. This delivery mode can reduce on-demand delivery times by up to 50 %, while also significantly lowering labor costs and mitigating safety hazards associated with traffic congestion. In response to the characteristics of payload and mileage limitations in the participation of drones in on-demand delivery, a mathematical model for optimizing drone on-demand delivery paths with minimization of drone delivery cost, energy cost, and time penalty cost is established based on considering order splitting and battery swapping for drones. A dynamic optimization framework based on the rolling horizon method is designed to solve this problem. This framework primarily consists of two components: dynamic order collection and dynamic order scheduling. The order collection employs the rolling horizon method to establish three distinct strategies for dynamically collecting orders, which subsequently serve as the basis for dynamic scheduling. Order scheduling encompasses both order allocation and drone path planning. For order allocation, we utilize a method that combines k-means++ clustering with an allocation rule that takes into account the current status of drones. Based on the current allocation results, we apply an adaptive large neighborhood search algorithm to optimize drone paths, ultimately determining the order scheduling plan. By conducting numerical simulation experiments with different scales of cases, the applicability of the clustering strategies and dynamic order collection strategies proposed in this paper has been verified. At the same time, the effectiveness of the model and algorithm proposed in this paper has also been validated.