acceptodds
Under review as a conference paper at ICLR 2027

LIFTing UAV Schedules: Diffusion Policies for Iterative Improvement

Abstract

Unmanned aerial vehicle (UAV) scheduling is a challenging sequential decision problem with tightly coupled operational constraints. Even small local edits can propagate through payload, energy, and timing dependencies, making high-quality schedules difficult to obtain through one-shot generation. We instead cast it as a sequential refinement process and propose LIFT, a refinement-aligned one-step diffusion policy for Learning schedule improvement via Imitation and PPO Fine-Tuning. LIFT predicts structured edits on a schedule-dependent candidate graph, decodes them into feasible successor schedules, and optimizes them for long-horizon improvement. Training follows a refinement-aligned two-stage design: it first learns edit-level behavior from expert improvement trajectories, and then applies PPO fine-tuning through a one-step denoiser with tractable conditional action log-probabilities. Trained only on small-scale instances, LIFT achieves the lowest mean total arrival time across all evaluated benchmark configurations and generalizes to substantially larger problems without retraining. Together, these results reposition diffusion in combinatorial optimization: from a one-shot solution generator to a reinforcement learning policy for sequential solution refinement.

Primary area:
optimization
Keywords:
UAV Scheduling, Diffusion Policy, Imitation Learning, PPO Fine-Tuning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1cNyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses load-dependent UAV scheduling through sequential improvement of feasible schedules. LIFT constructs a schedule-dependent candidate graph and samples ordered ADD/DEL edge lists using a graph-based, one-step noise-conditioned policy. A feasibility-preserving decoder translates these preferences into customer removals and reinsertions. Training combines imitation learning on GENIS improvement trajectories with PPO fine-tuning, enabled by tractable conditional Plackett-Luce log-probabilities for ordered edits. At inference, LIFT employs multi-branch search with Tabu memory and shake operations. Across 15 benchmark configurations with 50–360 customers, the method reports the best mean total customer arrival time among eight baselines. The paper also provides ablation studies, runtime comparisons, and evaluations beyond the training scale.

Critical strengths
  1. A practical and coherent refinement framework. The combination of structured edge preferences, constraint-aware decoding, and tractable conditional action likelihoods provides a useful framework for training an edit-level policy with PPO while maintaining feasible schedules.
  2. Extensive empirical evaluation with encouraging results. The paper reports consistent improvements across all 15 benchmark configurations and includes ablations on training stages, expert choice, and search components.
Critical weaknesses
  1. The noisy edit masks are sampled independently of the expert edits, without an explicit forward diffusion process. This makes the distinction between LIFT and a noise-conditioned stochastic policy unclear.
  2. The decoder and handcrafted search mechanisms play substantial roles in optimization, while Random-Edit remains competitive on several instances. The specific contribution of the learned policy is therefore not fully established.
  3. The synthetic training instances are generated from benchmark-derived templates. Generalization to genuinely different spatial layouts, demand distributions, and scheduling settings remains insufficiently demonstrated. 4.Potentially unfair computational comparison. The evaluation budget counts high-level schedule evaluations but does not fully account for internal decoding and feasibility checks.
Questions for authors
  1. What fundamentally distinguishes the proposed one-step diffusion policy from a stochastic GNN policy conditioned on random noise?
  2. Can the authors provide comparisons under matched wall-clock time or actual computational cost, including internal decoding operations?
  3. How well does LIFT generalize to independently generated instances with different spatial and demand distributions?
7 comments
AuthorsOpenReview ↗

Response to Reviewer 1cNy (1/3)

We thank the reviewer for recognizing the refinement framework and its tractable conditional likelihoods. We have uploaded a revised paper that includes all new experiments with their results and analyses; every change is highlighted in blue. Unless stated otherwise, results are means over 10 seeds on the 15 benchmark configurations, and each gain is relative to the compared method.

W1 & Q1: What fundamentally distinguishes LIFT's one-step diffusion policy from a stochastic GNN conditioned on random noise?

Unlike a GNN that uses random noise as an additional input to predict edit scores, LIFT learns to transform noisy schedule edits into clean improvement edits through a single denoising step. This is the basis of its one-step discrete diffusion policy. We explain how this mechanism supports iterative schedule improvement and provide new experimental evidence demonstrating its advantages.

1. Diffusion mechanism. Diffusion models learn to generate clean data from a noise prior through denoising [1]. LIFT follows this principle by learning a one-step transformation from noisy schedule edits to clean improvement edits. Specifically, at refinement step tt, LIFT defines a noise prior m(⋅∣st)m(\cdot\mid s_t) over ADD/DEL edits based on the current schedule sts_t. It then samples a noisy edit a~u\tilde a_u from this prior. The generation process is

\underbrace{\tilde a_u\sim m(\cdot\mid s_t)}_{\text{noisy edit}} \xrightarrow{\text{one-step denoising}} \underbrace{\left\\{p_\theta(x_0^{(e)}=1\mid s_t,\tilde a_u,u)\right\\}_{e\in E^{\mathrm{cand}}}}_{\text{clean-edit probabilities}} \xrightarrow{\text{Plackett–Luce}} a_t \xrightarrow{\mathcal D(s_t,a_t)} s_{t+1}.

The GNN-based denoiser predicts which candidate edges should be added or removed. Plackett–Luce sampling converts these predictions into an edit action ata_t that instructs the decoder D\mathcal D to produce a feasible successor schedule st+1s_{t+1}.

The noise prior depends on the current schedule sts_t, instead of an expert improvement edit. Unlike standard multi-step diffusion, LIFT learns to generate clean improvement edits directly from this noise prior in one step. The goal is to produce an edit that improves the current schedule, rather than reconstruct the schedule itself.

2. Alignment with iterative improvement. In standard diffusion training, clean data are corrupted with noise, and the model learns to recover the original data. LIFT instead learns to generate improvement edits conditioned on the current schedule sts_t. During imitation pretraining, expert improvement edits provide supervision; during PPO fine-tuning, rewards from the resulting schedules guide the generation of more effective edits. Since expert edits are unavailable during PPO fine-tuning and inference, LIFT samples noisy edits from the same schedule-conditioned noise prior during imitation pretraining, PPO fine-tuning, and inference. This reward-based fine-tuning process is consistent with DDPO and DPPO [2,3], while LIFT's one-step denoising and Plackett–Luce sampling provide tractable conditional action log-probabilities for PPO.

3. New controlled experiments. To determine whether LIFT's gains come from its structured edit noise or simply from introducing randomness, we evaluate three variants that retain the same model architecture, training procedure, decoder, and inference search:

  • LIFT-NoDiff: Removes the random noise input while retaining stochastic action sampling.
  • LIFT-Gaussian: Replaces LIFT's structured edit noise with Gaussian noise throughout training and inference.
  • LIFT-Forward: Generates noisy edits by corrupting expert edits during imitation pretraining, while using LIFT's original noise prior during PPO fine-tuning and inference.

Table R1. Average reduction in total arrival time achieved by LIFT over each variant.

VariantOverall gainBeyond training scaleBetter / Tie / Worse
LIFT-NoDiff3.82%5.19%14 / 1 / 0
LIFT-Gaussian2.09%3.25%14 / 1 / 0
LIFT-Forward0.15%0.20%14 / 1 / 0

References

[1] Austin et al. Structured Denoising Diffusion Models in Discrete State-Spaces, NeurIPS 2021.

[2] Black et al. Training Diffusion Models with Reinforcement Learning, ICLR 2024.

[3] Ren et al. Diffusion Policy Policy Optimization, ICLR 2025.

AuthorsOpenReview ↗

Response to Reviewer 1cNy (2/3)

W1 & Q1 (continued)

First, structured edit noise is more effective than generic random noise. Using Gaussian noise improves performance over LIFT-NoDiff by 1.78%, showing that random noise is useful. More importantly, LIFT further outperforms LIFT-Gaussian by 2.09% overall and 3.25% beyond the training scale, achieving better results on 14 of the 15 configurations and tying on the remaining one. These results show that LIFT benefits not only from random noise, but also from representing noise as potential schedule edits.

Second, conventional forward diffusion offers no additional benefit. LIFT-Forward achieves nearly identical performance to LIFT, with only a 0.15% average difference. This shows that explicitly corrupting expert edits during pretraining is unnecessary for achieving comparable performance. LIFT instead uses the same noise prior during imitation pretraining, PPO fine-tuning, and inference.

In summary, LIFT learns to generate improvement edits from structured noise through a one-step denoising process. The new experiments demonstrate the advantage of structured edit noise over generic random noise, while showing that conventional forward diffusion is not necessary for effective iterative improvement.

W2: What is the specific contribution of the learned policy?

The learned policy determines which customers to relocate (DEL) and where to reinsert them (ADD), while the decoder ensures feasibility. To isolate its contribution, we compare LIFT with Random-Edit, which replaces the learned edit scores with random scores while keeping the decoder and search mechanisms unchanged. LIFT achieves a 3.78% average improvement, outperforming Random-Edit on 14 of the 15 configurations.

We further compare both methods without multi-branch search or shake, using one action per step and accepting every successor, as in PPO training.

SettingLIFT gain (%)Beyond training scale (%)Better / Tie / Worse
Default3.785.0414 / 1 / 0
PPO-style, 50 steps3.905.2615 / 0 / 0
PPO-style, 8,000 steps5.347.0115 / 0 / 0

Without multi-branch search and shake, LIFT still outperforms Random-Edit on all 15 configurations, with an average gain of up to 5.34%. This confirms that the learned policy contributes substantially to solution quality, rather than relying solely on the decoder and search mechanisms.

W3 & Q3: How well does LIFT generalize to independently generated instances with different spatial and demand distributions?

We conducted new experiments on 18 independently generated instances using the public generator of Uchoa et al. [1]. Unlike our original training instances, these instances were generated independently of the benchmarks. They cover three spatial layouts (random, clustered, and mixed), three demand distributions (wide, light, and skewed), and two problem sizes (100 and 200 customers). The larger instances exceed LIFT's training scale, and some use more drones per depot than any original benchmark (up to 20 versus 14). LIFT is evaluated without retraining.

Table R2. Average improvement of LIFT over competing methods in total arrival time.

Instance sizeOver ALNSOver GENISOver Random-EditBetter / Not significant / Worse
C100_D32.46%2.16%4.82%23 / 3 / 1
C200_D54.15%3.62%7.10%27 / 0 / 0

The last column counts the comparisons against ALNS, GENIS, and Random-Edit (27 per problem size). Significance is assessed using Wilcoxon rank-sum tests with Holm correction across all 54 comparisons (α=0.05\alpha=0.05).

LIFT achieves the lowest mean total arrival time on 16 of the 18 instances and significantly outperforms Random-Edit on all 18. On the larger C200 instances, LIFT significantly outperforms all three competing methods in every comparison, with gains of 4.15% over ALNS, 3.62% over GENIS, and 7.10% over Random-Edit.

These results demonstrate that LIFT generalizes to new spatial layouts, demand distributions, and larger problem instances without retraining. Its larger gains on C200 further support its ability to handle problems beyond the training scale. Complete results are provided in Table 15 of the revised paper.

References

[1] Uchoa et al. New Benchmark Instances for the Capacitated Vehicle Routing Problem, European Journal of Operational Research 2017.

AuthorsOpenReview ↗

Response to Reviewer 1cNy (3/3)

W4 & Q2: Comparisons under matched wall-clock time or actual computational cost?

We agree that the original budget of 8,000 schedule evaluations does not fully reflect computational cost, since different methods perform different amounts of work within each evaluation. We therefore conducted new comparisons under matched wall-clock time, which accounts for all computation, including decoding, feasibility checks, and neural network inference.

For each configuration, we use LIFT's average runtime over 10 runs as the time limit for all methods, allowing the baselines to run without evaluation limits. We then compare the best solutions found within the same time limit.

Table R3. Results under matched wall-clock time. LIFT gain indicates the average reduction in total arrival time relative to each baseline.

MethodLIFT gain (%)LIFT better (out of 15)Evaluations within TT (10310^3)
LIFT––8.00
ALNS2.4914102
GENIS4.18153.03
VNS4.59155.41
LKH-35.0615133
MLG9.50150.001
AFL10.051593.6
GenSCO13.25154.14
ACO41.141519.4

LIFT still achieves the lowest mean total arrival time on 14 of the 15 configurations, outperforming ALNS, the closest competitor, by 2.49% on average. The only exception is C240_D6_K5, where ALNS performs 0.43% better. LIFT also outperforms every other baseline on all 15 configurations.

LIFT achieves better solution quality with fewer internal computations than ALNS, performing 71.5 million versus 93.3 million route-level feasibility and cost checks on average, and 8,000 versus 102,000 schedule evaluations.

These results confirm that LIFT's advantage persists under equal computational time, even when all internal operations are taken into account. Detailed results for the three closest competing methods are provided in Table R4.

Table R4. Total arrival time under matched wall-clock time (10210^2 seconds; mean (standard deviation) over 10 seeds). Lower is better.

ConfigurationLIFTALNSGENISVNS
C50_D4_K447.76 (0.00)47.83 (0.16)47.86 (0.10)47.82 (0.20)
C50_D4_K270.90 (0.53)72.00 (0.83)72.15 (1.58)71.98 (1.14)
C75_D5_K376.03 (0.46)77.03 (0.49)77.28 (0.79)77.38 (0.46)
C80_D2_K5239.56 (0.29)243.57 (0.95)244.40 (0.66)245.71 (0.77)
C100_D2_K8147.89 (0.89)149.66 (1.75)151.12 (1.25)151.12 (0.91)
C100_D2_K5175.03 (1.44)181.14 (0.68)184.13 (1.30)184.05 (1.48)
C100_D3_K6105.34 (0.59)115.61 (0.55)117.48 (0.73)117.95 (0.79)
C100_D4_K4129.06 (1.00)130.95 (1.19)132.02 (1.38)132.01 (1.31)
C160_D4_K5465.35 (0.73)473.67 (1.93)481.04 (4.25)483.18 (2.35)
C240_D6_K5709.55 (3.26)706.49 (1.73)724.01 (5.75)725.41 (6.19)
C249_D2_K14971.73 (2.79)992.17 (3.46)1031.13 (6.29)1031.82 (9.67)
C249_D3_K12713.32 (3.62)751.01 (1.19)772.40 (3.77)779.35 (5.32)
C249_D4_K8708.18 (3.28)743.16 (1.95)756.98 (3.92)773.69 (8.98)
C249_D5_K6749.72 (2.05)769.11 (3.04)794.61 (9.82)799.86 (5.41)
C360_D9_K51028.57 (4.28)1052.12 (2.23)1103.56 (8.04)1119.31 (11.31)
Reviewer_M9WQOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes LIFT, which formulates load-dependent UAV scheduling as an iterative refinement problem based on local structural edits rather than one-shot complete-solution generation. Its core idea is to transform diffusion from a complete-solution generator into an iterative edit policy that continuously improves the current schedule by predicting structured ADD/DEL edits, trained through a combination of imitation learning and PPO.

Overall, introducing diffusion into iterative schedule refinement is an interesting direction, and the experimental evaluation and ablation studies are relatively comprehensive. However, the proposed “one-step diffusion” differs substantially from a standard diffusion process, and the final performance relies heavily on classical search machinery. Therefore, it remains unclear whether the main improvements stem from the diffusion policy itself or from the overall combination of a stochastically conditioned GNN, imitation learning/PPO, and local search mechanisms.

Critical strengths
  • LIFT directly predicts structured ADD/DEL edits on the current schedule instead of regenerating a complete solution, which is well aligned with iterative schedule refinement.

  • The experimental evaluation is relatively comprehensive, with baseline comparisons, multiple problem scales, and extensive ablations covering the main training and search components.

Critical weaknesses
  1. This paper explicitly states that the noisy edit mask is not obtained by corrupting the clean expert edit. Instead, a sparse binary edit mask is generated by uniformly sampling candidate edges, while the timestep uu is only used as an additional conditioning variable. The authors also state that they do not simulate a multi-step forward diffusion chain. This means there is no explicit forward process q(xu∣x0)q(x_u \mid x_0) connecting the clean expert edit to the noisy input, which is normally central to a diffusion formulation. Algorithmically, the model can therefore also be interpreted as a stochastic edge-scoring network conditioned on a random sparse mask and a timestep embedding. The current LIFT-NoDiff ablation does not fully resolve this issue. LIFT-NoDiff fixes the noisy-edit input to zero and uses the same timestep for every sample, while retaining the same network, PPO training, action sampling, decoder, and search procedure. Full LIFT improves over this variant, but this result only shows that the additional stochastic conditioning is useful; it does not by itself establish that the gain specifically comes from a diffusion mechanism.

  2. The paper motivates PPO through long-horizon credit assignment and explicitly argues that an edit with a small or negative immediate reward can still be useful if it enables larger future improvements. During PPO rollouts, non-improving successors are indeed accepted so that such multi-step trajectories can be learned. However, the inference procedure behaves differently: a successor is accepted only if it immediately improves the current objective, while non-improving moves are rejected. Exploration at inference is instead handled through branch diversity and shake/restart. Thus, the training procedure allows the policy to learn non-monotonic trajectories that the actual inference policy cannot execute. The experiments show that PPO improves performance, but they do not clearly establish that this improvement comes from the claimed long-horizon credit-assignment mechanism rather than from better local action scoring.

  3. The final inference pipeline contains several strong non-neural search components. The decoder ranks customers using DEL support, enumerates candidate subsets, keeps low-cost feasible insertion positions, uses ADD support for reinsertion, and returns the feasible schedule with the lowest objective. The outer search further uses multiple branches, different temperatures, Tabu memory, and shake/restart with classical neighborhood operators such as relocate, 2-opt, or-opt, and cross-exchange. The paper's own ablations show that these components contribute gains of similar magnitude to the learned diffusion component: removing ADD-guided insertion, Tabu, or shake each causes a noticeable performance drop, while Random-Edit combined with the same decoder and search pipeline remains competitive with GENIS on some instances. The current results strongly support the effectiveness of the complete hybrid refinement system, but they do not cleanly isolate how much of the final gain should specifically be attributed to the proposed diffusion policy.

Questions for authors

See weakness.

7 comments
AuthorsOpenReview ↗

Response to Reviewer M9WQ (1/3)

We thank the reviewer for the detailed assessment and for seeing diffusion in iterative schedule refinement as an interesting direction. We have uploaded a revised paper that includes all new experiments with their results and analyses; every change is highlighted in blue. All results below are means over 10 seeds on the 15 benchmark configurations.

W1: Separating the diffusion mechanism from q(xu∣x0)q(x_u\mid x_0) and stochastic conditioning

LIFT is a one-step discrete diffusion policy that learns to generate clean improvement edits from noise through a single denoising step.

1. Diffusion mechanism. Diffusion models learn to generate clean data from a noise prior through denoising [1,2]. LIFT follows this principle for schedule improvement. Given the current schedule sts_t, it samples a noisy edit a~u\tilde a_u from a noise prior m(⋅∣st)m(\cdot\mid s_t) over random ADD/DEL edits based on the current schedule. The generation process is

\xrightarrow{\text{one-step denoising}} \underbrace{p_\theta(x_0\mid s_t,\tilde a_u,u)}_{\text{clean-edit prediction}} \xrightarrow{\text{action sampling}} a_t \xrightarrow{\mathcal D(s_t,a_t)} s_{t+1}.$$ The GNN predicts clean improvement edits from the noisy input, and the decoder $\mathcal D$ produces a feasible successor schedule. **The noise prior depends on the current schedule, not on a particular expert edit.** Unlike conventional multi-step diffusion, LIFT learns this noise-to-clean-edit generation directly in one step, without explicitly constructing intermediate forward or reverse diffusion steps. **2. Why explicit forward corruption is unnecessary.** In standard diffusion training, $q(x_u\mid x_0)$ generates noisy inputs by corrupting clean data, and the model learns to recover the original data. **LIFT instead learns to generate edits that improve the current schedule $s_t$**, rather than reconstructing $s_t$. During imitation pretraining, expert improvement edits provide supervision; during PPO fine-tuning, rewards from the resulting schedules guide the generation of more effective edits. Since expert edits are unavailable during PPO fine-tuning and inference, LIFT samples noisy edits from the same schedule-conditioned noise prior during **imitation pretraining, PPO fine-tuning, and inference**. Reward-based fine-tuning of diffusion policies is also established in DDPO and DPPO [3,4]. LIFT's one-step design further provides tractable conditional action log-probabilities for PPO. **3. New controlled experiments.** To determine whether LIFT's gains come from structured edit noise or simply from introducing randomness, we evaluate three variants that retain the same model architecture, training procedure, decoder, and inference search: - **LIFT-NoDiff:** Removes the random noise input while retaining stochastic action sampling. - **LIFT-Gaussian:** Replaces LIFT's structured edit noise with Gaussian noise throughout training and inference. - **LIFT-Forward:** Generates noisy edits by corrupting expert edits during imitation pretraining, while using LIFT's original noise prior during PPO fine-tuning and inference. **Table R1.** Average reduction in total arrival time achieved by LIFT over each variant. | Variant | Overall gain | Beyond training scale | Better / Tie / Worse | | :--- | ---: | ---: | :---: | | LIFT-NoDiff | 3.82% | 5.19% | 14 / 1 / 0 | | LIFT-Gaussian | 2.09% | 3.25% | 14 / 1 / 0 | | LIFT-Forward | 0.15% | 0.20% | 14 / 1 / 0 | **First, structured edit noise is more effective than generic random noise.** Gaussian noise improves over LIFT-NoDiff by 1.78%, showing that introducing random noise is beneficial. More importantly, LIFT outperforms LIFT-Gaussian by **2.09% overall and 3.25% beyond the training scale**, achieving better results on 14 of the 15 configurations and tying on the remaining one. On all 14 configurations, the performance differences exceed the larger standard deviation. These results show that LIFT benefits not merely from random noise, but also from representing noise as potential schedule edits. **Second, explicit forward corruption provides no measurable additional benefit.** LIFT-Forward performs comparably to LIFT, with only a 0.15% average difference and all per-configuration differences within one standard deviation. Thus, directly learning from the noise prior achieves comparable performance without introducing expert-dependent noisy inputs during pretraining. **References** [1] Ho et al. Denoising Diffusion Probabilistic Models, NeurIPS 2020. [2] Austin et al. Structured Denoising Diffusion Models in Discrete State-Spaces, NeurIPS 2021. [3] Black et al. Training Diffusion Models with Reinforcement Learning, ICLR 2024. [4] Ren et al. Diffusion Policy Policy Optimization, ICLR 2025.
AuthorsOpenReview ↗

Response to Reviewer M9WQ (2/3)

W1 (continued)

In summary, LIFT learns to generate improvement edits from structured noise through a one-step denoising process. The new experiments demonstrate that structured edit noise is more effective than generic Gaussian noise, while explicit forward-corruption pretraining is unnecessary for the observed performance.

Table R2. Detailed results in total arrival time (10210^2 seconds; mean (standard deviation) over 10 seeds). Lower is better.

ConfigurationLIFT-NoDiffLIFT-GaussianLIFT-ForwardLIFT
C50_D4_K447.76 (0.00)47.76 (0.00)47.76 (0.00)47.76 (0.00)
C50_D4_K273.61 (0.38)73.13 (1.10)71.37 (0.67)70.90 (0.53)
C75_D5_K377.26 (0.40)76.93 (0.24)76.06 (0.28)76.03 (0.46)
C80_D2_K5243.36 (0.21)242.27 (0.35)239.73 (0.03)239.56 (0.29)
C100_D2_K8149.60 (0.57)149.46 (0.85)147.93 (0.16)147.89 (0.89)
C100_D2_K5182.23 (1.49)177.66 (1.70)175.19 (1.10)175.03 (1.44)
C100_D3_K6116.56 (0.72)107.09 (0.73)105.40 (0.61)105.34 (0.59)
C100_D4_K4132.25 (0.60)130.64 (1.51)129.09 (0.12)129.06 (1.00)
C160_D4_K5475.46 (1.79)470.48 (1.18)465.54 (0.80)465.35 (0.73)
C240_D6_K5713.24 (1.20)717.34 (0.86)709.76 (0.88)709.55 (3.26)
C249_D2_K141033.08 (3.81)1010.74 (6.02)974.36 (12.26)971.73 (2.79)
C249_D3_K12773.19 (1.30)742.81 (2.26)714.82 (2.95)713.32 (3.62)
C249_D4_K8755.28 (2.33)735.47 (2.56)709.95 (6.79)708.18 (3.28)
C249_D5_K6796.43 (4.06)776.27 (5.71)751.15 (4.10)749.72 (2.05)
C360_D9_K51080.99 (4.41)1065.32 (6.83)1031.15 (5.97)1028.57 (4.28)

W2: Does the difference between PPO training and inference undermine the benefits of PPO?

The different acceptance rules serve different purposes. PPO training accepts non-improving moves to learn how current decisions affect future rewards. At inference, LIFT accepts only improving moves in order to find high-quality schedules quickly, using parallel search and shake operations to explore alternative solutions. We conducted two additional experiments to examine whether this difference undermines the benefits of PPO.

1. Does PPO learn beyond immediate improvements? We introduce LIFT-Myopic, which uses the same pretrained policy and PPO fine-tuning but sets the discount factor γ=0\gamma=0, so learning considers only immediate rewards. LIFT-Myopic improves over LIFT (imitation only) by just 0.26% on average and performs worse on 8 of the 15 configurations. In contrast, full LIFT (γ=0.99\gamma=0.99) achieves a 3.99% improvement, outperforming imitation on 14 configurations. This demonstrates that learning from future rewards is important to PPO's effectiveness.

2. Do PPO's benefits persist when inference accepts non-improving moves? We evaluate LIFT under the same conditions as PPO training: one branch, one action per step, all successors accepted, and no shake. We test 50 steps (the training episode length) and 8,000 steps (the default evaluation budget). Within the first 50 steps, 31.6% of successors produce no immediate improvement, and 5.2% worsen the current schedule. Nevertheless, LIFT still outperforms imitation by 2.65% after 50 steps and 4.04% after 8,000 steps.

Table R3. Improvement over LIFT (imitation only) in total arrival time (%). Both methods use the same inference settings in each comparison.

ConfigurationDefault, γ=0\gamma=0Default, γ=0.99\gamma=0.99PPO-style, 50 stepsPPO-style, 8,000 steps
C50_D4_K40.000.001.050.00
C50_D4_K2−2.350.941.65−0.35
C75_D5_K31.222.38−0.301.84
C80_D2_K5−0.041.561.472.79
C100_D2_K8−0.131.591.692.32
C100_D2_K50.474.662.125.01
C100_D3_K6−0.189.534.377.75
C100_D4_K41.002.211.523.44
C160_D4_K5−0.122.192.443.42
C240_D6_K50.180.781.552.63
C249_D2_K14−0.165.334.884.96
C249_D3_K120.437.516.659.06
C249_D4_K8−0.256.274.075.62
C249_D5_K6−0.616.002.674.76
C360_D9_K54.448.963.887.35
Mean0.263.992.654.04
Better / Tie / Worse6 / 1 / 814 / 1 / 014 / 0 / 113 / 1 / 1

These results show that PPO benefits from learning future rewards, and its performance gains persist under both inference procedures. In particular, LIFT improves over imitation by 3.99% under default inference and 4.04% under PPO-style inference. Thus, the use of different acceptance rules does not undermine the benefits of PPO fine-tuning.

AuthorsOpenReview ↗

Response to Reviewer M9WQ (3/3)

W3: What does the learned policy contribute beyond the decoder and search?

The learned policy determines which customers to relocate (DEL) and where to reinsert them (ADD), while the decoder ensures feasibility and the search procedure supports exploration. These components serve different purposes. In Table 11 (Appendix F.3), replacing learned ADD guidance with cost-only insertion worsens performance by 3.76%, demonstrating the value of the learned edit decisions.

To further isolate the learned policy's contribution, we compare LIFT with Random-Edit, which replaces the learned ADD/DEL scores with random scores while keeping the same decoder and search procedure. We also evaluate both methods under simpler inference settings, as in PPO rollouts: one branch, one action per step, all successors accepted, and no shake, while retaining Tabu memory.

As shown in Table R4, LIFT outperforms Random-Edit by 3.78% under default inference. Without multi-branch search and shake, its advantage increases to 5.34%, with better results on all 15 configurations and a 7.01% gain beyond the training scale.

These results demonstrate that the learned policy contributes substantially to solution quality, rather than relying on the decoder and search procedure alone.

Table R4. Improvement of LIFT over Random-Edit in total arrival time (%). Both methods use the same inference settings in each comparison.

ConfigurationDefault inferencePPO-style, 50 stepsPPO-style, 8,000 steps
C50_D4_K40.002.020.21
C50_D4_K22.101.693.75
C75_D5_K31.212.242.84
C80_D2_K51.532.352.87
C100_D2_K81.782.232.82
C100_D2_K54.843.755.61
C100_D3_K69.707.5310.88
C100_D4_K43.031.783.41
C160_D4_K52.283.345.63
C240_D6_K50.612.922.50
C249_D2_K145.447.277.25
C249_D3_K127.245.848.80
C249_D4_K86.334.418.82
C249_D5_K66.155.837.35
C360_D9_K54.495.297.34
Mean3.783.905.34
Within / beyond training scale2.94 / 5.042.99 / 5.264.23 / 7.01
Better / Tie / Worse14 / 1 / 015 / 0 / 015 / 0 / 0
Reviewer_tCYtOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

LIFT minimizes total customer arrival time in UAV scheduling under depot, route, payload, and battery constraints. It represents a feasible schedule as a graph and predicts ordered ADD/DEL edits on a schedule-dependent candidate graph. A decoder turns these edits into feasible successors. Training first imitates GENIS improvement trajectories, then uses PPO with a re-evaluable Plackett–Luce action likelihood. Inference adds four-branch search, Tabu memory, and shake restarts. LIFT achieves the lowest mean total arrival time on all 15 benchmark configurations, including six larger configurations outside its training-size range. Ablations, time-to-best measurements, alternative experts, and a nonlinear-energy stress test supplement the main comparison.

Critical strengths
  1. Learning edits to an existing feasible schedule fits the problem’s coupled load and energy constraints. The candidate graph and decoder define how a sampled action becomes a valid route change, while the explicit conditional likelihood makes the PPO update reproducible at the method level. (Sections 3.1–3.3; Equation 8; Appendices D.4–D.5.)

  2. The evaluation includes more than final objective values. LIFT leads on all 15 configurations and improves beyond the imitation expert, with controls for training stages, noise conditioning, and search components. LIFT-NoDiff and Random-Edit use the same decoder and search framework, so their comparison provides evidence beyond a difference in feasibility handling. (Section 4; Appendices F.2–F.6.)

Critical weaknesses
  1. The diffusion interpretation is not clearly separated from stochastic conditioning. Appendix D.3 samples the sparse noisy edit independently of the expert edit and chooses a timestep without simulating a multi-step corruption process. LIFT-NoDiff removes both mask and timestep variation, so it does not establish which part of denoising is necessary.
  2. The transfer and efficiency claims should remain tied to the evaluation design. Synthetic training data inherit benchmark geometry and demand templates, and the larger tests stay within the same family. The common 8,000-step budget counts completed candidate-producing operations despite different internal work. The time-to-best results help, but do not fully resolve solution quality at equal elapsed time. (Section 4.1; Appendices E.1 and F.2.)
Questions for authors
  1. What makes the learning objective specifically diffusion-based when the noisy mask is independent of the expert edit? A matched policy with random conditioning and no denoising interpretation would help isolate the contribution. (Section 3.2; Appendix D.3.)
  2. Does transfer persist with disjoint templates or shifted spatial and demand distributions? If these tests are unavailable, please restrict the generalization claim to the benchmark family evaluated. (Section 4.1; Appendix E.1.)
  3. PPO rollouts may accept non-improving successors, whereas inference accepts only improvements and adds Tabu and shake operations. How does this transition mismatch affect the claimed long-horizon PPO benefit? (Sections 3.4–3.5; Appendix D.6.)
  4. Can solution quality be compared at matched wall-clock cutoffs, especially against ALNS and faster alternatives? The equal evaluation budget and Table 6 time-to-best values answer related but different questions. (Section 4.1; Appendix F.2.)
  5. Were the Table 1 significance tests adjusted for the many pairwise comparisons? Please provide adjusted results or the unadjusted p-values with a clear account of multiplicity, particularly where absolute gaps are small. (Appendix F.1.)
6 comments
AuthorsOpenReview ↗

Response to Reviewer tCYt (1/3)

We thank the reviewer for the careful reading. We have uploaded a revised paper that includes all new experiments with their results and analyses; every change is highlighted in blue. Unless stated otherwise, results are means over 10 seeds on the 15 benchmark configurations.

W1 & Q1: What makes the learning objective specifically diffusion-based when the noisy mask is independent of the expert edit?

LIFT adopts a one-step diffusion policy that learns to generate clean improvement edits from noisy edits. Its imitation objective trains a denoiser to predict expert improvement edits from a noise prior, while PPO further optimizes the denoiser to maximize cumulative improvements in total arrival time. The independence of the noisy mask from the expert edit is consistent with the fully noised starting point of diffusion models, as explained below.

1. Learning objective and diffusion mechanism. In diffusion models, the denoiser learns to recover clean data from noisy inputs [1]. LIFT applies this principle to schedule edits. Given the current schedule sts_t, it samples a noisy edit a~u\tilde a_u from a schedule-conditioned prior m(⋅∣st)m(\cdot\mid s_t). The denoiser predicts the probability of each candidate edge belonging to the clean edit:

\qquad e\in E^{\mathrm{cand}}.$$ During imitation pretraining, expert improvement edits provide the clean targets. LIFT minimizes the two cross-entropy losses defined in Eq. (10): $$\mathcal L_{\mathrm{IL}}= \mathrm{CE}_{\mathrm{ADD}} + \mathrm{CE}_{\mathrm{DEL}}.$$ **This is a one-step denoising reconstruction objective:** the model receives a noisy edit and learns to predict the corresponding clean improvement edit. Cross-entropy itself is not unique to diffusion; its role here is to train the learned noise-to-clean-edit mapping. **2. Why is the noisy mask independent of the expert edit?** The key reason is that **LIFT is designed for iterative schedule improvement, rather than reconstructing a corrupted expert edit.** At each refinement step, LIFT starts from the current schedule $s_t$ and must generate an edit that leads to a better successor $s_{t+1}$. The desired edit is unknown when the policy makes its decision, so it cannot be used to construct the noisy input. Instead, LIFT samples a noisy edit from the **current schedule**, independently of the expert edit. During imitation pretraining, expert edits supervise the denoiser in learning to transform these noisy edits into improvement edits. During PPO fine-tuning, LIFT learns to generate edits that reduce total arrival time over successive refinement steps (Eq. (2)). This design also keeps the noisy-input distribution consistent across imitation pretraining, PPO fine-tuning, and inference. **3. New controlled experiments.** To determine whether LIFT's gains come from structured edit noise or simply from introducing randomness, we evaluate three variants that retain the same model architecture, training procedure, decoder, and inference search: - **LIFT-NoDiff:** Removes the random noise input while retaining stochastic action sampling. - **LIFT-Gaussian:** Replaces LIFT's structured edit noise with Gaussian noise throughout training and inference. - **LIFT-Forward:** Generates noisy edits by corrupting expert edits during imitation pretraining, while using LIFT's original noise prior during PPO fine-tuning and inference. **Table R1.** Average reduction in total arrival time achieved by LIFT over each variant. | Variant | Overall gain | Beyond training scale | Better / Tie / Worse | | :--- | ---: | ---: | :---: | | LIFT-NoDiff | 3.82% | 5.19% | 14 / 1 / 0 | | LIFT-Gaussian | 2.09% | 3.25% | 14 / 1 / 0 | | LIFT-Forward | 0.15% | 0.20% | 14 / 1 / 0 | **First, structured edit noise is more effective than generic random noise.** LIFT-Gaussian improves over LIFT-NoDiff by 1.78%, showing that introducing random noise is beneficial. More importantly, LIFT further outperforms LIFT-Gaussian by **2.09% overall and 3.25% beyond the training scale**, achieving better results on 14 of the 15 configurations and tying on the remaining one. All 14 differences exceed the larger standard deviation. Thus, LIFT's advantage cannot be explained by adding generic random noise to the GNN alone. **Second, explicit forward corruption provides no measurable additional benefit.** LIFT-Forward performs comparably to LIFT, with an average difference of 0.15% and all per-configuration differences within one standard deviation. This shows that explicitly corrupting expert edits during pretraining is unnecessary for achieving comparable performance. LIFT instead learns directly from the noise prior used during PPO fine-tuning and inference. **References** [1] Austin et al. Structured Denoising Diffusion Models in Discrete State-Spaces, NeurIPS 2021.
AuthorsOpenReview ↗

Response to Reviewer tCYt (2/3)

W2 & Q2: Does LIFT generalize to new spatial layouts and demand distributions?

Yes. We conducted new experiments on 18 independently generated instances using the public generator of Uchoa et al. [1], without following any original benchmarks. These instances cover three spatial layouts (random, clustered, and mixed), three demand distributions (wide, light, and skewed), and two problem sizes (100 and 200 customers). The larger instances exceed LIFT's training scale, and some configurations use more drones per depot than the original benchmarks (up to 20 versus 14). LIFT is evaluated without retraining.

Table R2. Average improvement of LIFT over competing methods in total arrival time.

Instance sizeOver ALNSOver GENISOver Random-EditBetter / Not significant / Worse
C100_D32.46%2.16%4.82%23 / 3 / 1
C200_D54.15%3.62%7.10%27 / 0 / 0

The last column summarizes 27 comparisons per problem size against ALNS, GENIS, and Random-Edit. Statistical significance is assessed using Wilcoxon rank-sum tests with Holm correction across all 54 comparisons (α=0.05\alpha=0.05).

LIFT achieves the lowest mean total arrival time on 16 of the 18 instances and significantly outperforms Random-Edit on all 18. On the larger C200 instances, LIFT significantly outperforms all three competitors in every comparison, with gains of 4.15% over ALNS, 3.62% over GENIS, and 7.10% over Random-Edit.

These results demonstrate that LIFT generalizes to independently generated instances with different spatial layouts and demand distributions, without retraining. Its larger gains on C200 further demonstrate its effectiveness beyond the training scale. Detailed results are provided in Table 15 of the revised paper.

Q3: Does the difference between PPO training and inference affect PPO's benefits?

The difference in acceptance rules does not undermine PPO's benefits. During training, LIFT accepts non-improving moves to learn their effects on future rewards. At inference, LIFT accepts improving moves and uses parallel search and shake to explore alternative solutions, in order to find good schedules quickly.

1. Do PPO's benefits persist under the training acceptance rule? We evaluate LIFT under the same settings as PPO training: one branch, one action per step, all successors accepted, and no shake. As shown in Table R3, PPO improves performance by 3.99% under default inference and 4.04% under PPO-style inference with 8,000 steps, compared with LIFT before PPO fine-tuning. The improvement also reaches 2.65% after 50 steps, matching the training episode length. Non-improving moves do occur: during the first 50 steps, 31.6% of successors have zero immediate reward and 5.2% have negative reward.

Table R3. Improvement from PPO fine-tuning under different inference settings.

Inference settingAverage gain (%)Better / Tie / Worse
Default inference3.9914 / 1 / 0
PPO-style, 50 steps2.6514 / 0 / 1
PPO-style, 8,000 steps4.0413 / 1 / 1

2. Does PPO benefit from learning future rewards? We introduce LIFT-Myopic, which uses the same pretrained policy and PPO fine-tuning but sets the discount factor γ=0\gamma=0, so learning considers immediate rewards only. As shown in Table R4, LIFT-Myopic improves performance by 0.26%, compared with 3.99% for LIFT with γ=0.99\gamma=0.99. This confirms the importance of learning from future rewards.

Table R4. Effect of the discount factor on PPO gains under default inference.

MethodAverage gain (%)Better / Tie / Worse
LIFT-Myopic (γ=0\gamma=0)0.266 / 1 / 8
LIFT (γ=0.99\gamma=0.99)3.9914 / 1 / 0

Together, these results demonstrate that learning from future rewards is important to PPO's effectiveness, and its performance gains remain consistent under different inference settings. The difference between training and inference acceptance rules therefore does not undermine the benefits of PPO fine-tuning.

References

[1] Uchoa et al. New Benchmark Instances for the Capacitated Vehicle Routing Problem, European Journal of Operational Research 2017.

AuthorsOpenReview ↗

Response to Reviewer tCYt (3/3)

W2 & Q4: Does LIFT still outperform the baselines under equal runtime?

Yes. We conducted additional experiments with matched wall-clock time. For each configuration, we use LIFT's average runtime over 10 runs as the time limit TT for all methods. LIFT uses its default budget of 8,000 schedule evaluations, while the baselines run without evaluation limits. We compare the best solutions found within the same time limit.

As shown in Table R5, LIFT outperforms ALNS by 2.49% on average and achieves better results on 14 of the 15 configurations. The exception is C240_D6_K5, where ALNS performs 0.43% better. LIFT also outperforms every other baseline on all 15 configurations, including the faster alternatives MLG, AFL, and ACO, with average improvements of 9.50%, 10.05%, and 41.14%, respectively.

Table R5. Performance comparison under equal wall-clock time. Gains represent reductions in total arrival time achieved by LIFT.

MethodLIFT gain (%)LIFT lower mean (of 15)Evaluations by TT (10310^3)
LIFT––8.00
ALNS2.4914102
GENIS4.18153.03
VNS4.59155.41
LKH-35.0615133
MLG9.50150.001
AFL10.051593.6
GenSCO13.25154.14
ACO41.141519.4

These results confirm that LIFT's advantage persists under equal runtime, rather than depending on a larger computational budget. Detailed comparisons with ALNS and the faster alternatives are provided in Table R6.

Table R6. Per-configuration results under equal wall-clock time. Total arrival time in 10210^2 seconds (mean over 10 runs; MLG is deterministic). Lower is better.

ConfigurationTT (s)LIFTALNSMLGAFLACO
C50_D4_K458647.7647.8348.4548.9164.37
C50_D4_K279270.9072.0078.7175.0490.02
C75_D5_K3137576.0377.0381.7878.85107.76
C80_D2_K51316239.56243.57263.50243.95387.48
C100_D2_K81877147.89149.66168.95177.02255.48
C100_D2_K52096175.03181.14192.81229.36291.13
C100_D3_K61754105.34115.61122.20120.41197.10
C100_D4_K41874129.06130.95142.56149.56219.14
C160_D4_K53420465.35473.67522.08488.59883.82
C240_D6_K55486709.55706.49781.80738.821406.45
C249_D2_K145829971.73992.171065.251174.481624.41
C249_D3_K125549713.32751.01795.24863.431335.35
C249_D4_K85723708.18743.16782.91780.801332.29
C249_D5_K65991749.72769.11837.41836.131475.88
C360_D9_K584741028.571052.121154.321118.782193.49

Q5: Do the significance results remain valid after correcting for multiple comparisons?

Yes. We applied the Holm correction to the Wilcoxon rank-sum tests reported in Table 1. The 105 pairwise comparisons against the seven stochastic baselines were corrected together, using exact two-sided tests at a significance level of 0.05.

As shown in Table R7, LIFT remains significantly better in 102 of the 105 comparisons. The remaining three comparisons are not statistically significant after correction, although LIFT still achieves lower mean total arrival time in each case.

Table R7. Statistical results after Holm correction.

ConfigurationBaselineLIFT gain (%)pppHolmp_{\mathrm{Holm}}
C50_D4_K2GENIS1.730.0430.087
C240_D6_K5GENIS0.490.0430.087
C50_D4_K4ALNS0.330.0190.056
Remaining 102 comparisonsSeven stochastic baselines≥ 0.21≤ 0.009≤ 0.036
All 15 configurationsMLG≥ 1.420.0020.029

For deterministic MLG, we separately applied exact one-sample Wilcoxon signed-rank tests, with Holm correction across the 15 configurations. LIFT remains significantly better on all 15.

Thus, the main statistical conclusions of Table 1 remain supported after correcting for multiple comparisons.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.