Asymmetric Dual-Resource Replenishment Scheduling for Plant Protection UAVs on Fixed Routes: An Event-Graph Dynamic Programming Approach

We formulate fixed-route replenishment scheduling for plant protection unmanned aerial vehicles (UAVs), jointly selecting replenishment timing, operation type, and station to minimize additional replenishment time. Resource resets invalidate the monotone-depletion premise of standard resource-constrained shortest-path methods; the two resources deplete asymmetrically (endurance throughout, pesticide only when spraying), and because joint or serial replenishments share a detour while the pesticide-type consistency constraint forces refills at type switches, the battery- and pesticide-side decisions cannot be separated. We develop event-graph dynamic programming (EGDP), which discretizes replenishment timings into event points and encodes the five replenishment types as arcs, reducing the joint decision to a shortest path solved by label-setting search with dominance and redundancy pruning. On 20 instances with four fields, EGDP’s total working times matched those of a same-grid mixed-integer linear programming (MILP) model within 10−6 min in 19 cases; in the remaining case, the MILP failed to prove optimality and was 0.07% worse, while EGDP was about 3069 times faster. Across 100 instances spanning five scales, EGDP reduced additional replenishment time by 10.9% relative to a greedy baseline; on 20 instances with six fields, the 0.5 min grid produced a mean deviation of 0.72% from the finest 0.05 min grid, with a runtime of 0.66 s, supporting pre-flight planning.