Adaptive Policy Optimization for Battery-Constrained Drone Delivery Routing

This study addresses a drone delivery routing optimization problem with battery constraints, a variant of a vehicle routing problem (VRP), where drones deliver goods to multiple customer nodes while adhering to operational limitations such as battery and payload capacities. Our study proposes Adaptive-Policy Optimization with Multiple Optima (A-POMO), an enhanced framework based on POMO, which is a reinforcement-learning-based method for solving combinatorial optimization problems like VRP without relying on labeled data. A-POMO for battery-constrained drone delivery routing improves solution quality and computational efficiency through a constraint-guided probability distribution and an adaptive elite reward mechanism. Especially, A-POMO adjusts reward weights adaptively and employs a refined baseline for elite solutions to strike a balance between exploration and exploitation. Numerical experiments with 20, 50, and 100 customer nodes demonstrate that A-POMO achieves near-optimal solutions compared to MILP, with significant time efficiency for small-scale instances. It also outperforms the original POMO in large-scale instances for constraint-guided route optimization.