UAV Charging Station Planning and Route Optimization Considering Stochastic Delivery Demand

Unmanned Aerial Vehicle (UAV) cluster is increasingly used in the field of logistics. However, the efficiency of drone delivery is greatly affected by the limited cruising range. Optimal planning charging infrastructure is necessary to expand the service range of drone delivery. In this paper, a comprehensive formulation for optimal siting and sizing of UAV charging stations is built, which is a scenario-based optimization model to minimize the investment cost and task time considering the randomness of delivery demands. The scheme of routing, task allocation, and recharging scheduling is optimized to improve the operational efficiency of the UAV swarm. The spatial topology of drone delivery is constructed, which renders the proposed formulation suitable for complex scenarios with multiple tasks and charging stations. An algorithm combining variable neighborhood search (VNS) with mixed integer linear programming (MILP) is proposed to solve the proposed model with high efficiency. Finally, the effectiveness and robustness of the proposed solution algorithm are demonstrated by simulation results. For the large-scale case that GUROBI solver fails to solve after running for 168 h, the proposed algorithm converges to the optimum in only 18.7% of the runtime required by genetic algorithm (GA), while achieving a 2.3% lower cost than GA.