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.
Authors
- Yu Cheng Wu (ORCID: https://orcid.org/0000-0002-9319-9498)
- Mengji Shi (ORCID: https://orcid.org/0000-0003-1360-9846)
- Zhiqiang Li (ORCID: https://orcid.org/0009-0001-0877-2000)
- Shuting Xu (ORCID: https://orcid.org/0009-0008-3533-4576)
- Henghui Liu
Institutions
- University of Electronic Science and Technology of China (CN)
- Beijing Forestry University (CN)
Publication Details
- Journal
- Symmetry
- Published
- 2026-11-12
- DOI
- https://doi.org/10.3390/sym18111896
- Primary Topic
- Vehicle Routing Optimization Methods
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China
- Fundamental Research Funds for the Central Universities