- 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
- 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.
- 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
- 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.
- 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.
- 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
- What fundamentally distinguishes the proposed one-step diffusion policy from a stochastic GNN policy conditioned on random noise?
- Can the authors provide comparisons under matched wall-clock time or actual computational cost, including internal decoding operations?
- How well does LIFT generalize to independently generated instances with different spatial and demand distributions?
7 comments
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.
| Setting | LIFT gain (%) | Beyond training scale (%) | Better / Tie / Worse |
|---|---|---|---|
| Default | 3.78 | 5.04 | 14 / 1 / 0 |
| PPO-style, 50 steps | 3.90 | 5.26 | 15 / 0 / 0 |
| PPO-style, 8,000 steps | 5.34 | 7.01 | 15 / 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 size | Over ALNS | Over GENIS | Over Random-Edit | Better / Not significant / Worse |
|---|---|---|---|---|
| C100_D3 | 2.46% | 2.16% | 4.82% | 23 / 3 / 1 |
| C200_D5 | 4.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 ().
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.
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.
| Method | LIFT gain (%) | LIFT better (out of 15) | Evaluations within () |
|---|---|---|---|
| LIFT | – | – | 8.00 |
| ALNS | 2.49 | 14 | 102 |
| GENIS | 4.18 | 15 | 3.03 |
| VNS | 4.59 | 15 | 5.41 |
| LKH-3 | 5.06 | 15 | 133 |
| MLG | 9.50 | 15 | 0.001 |
| AFL | 10.05 | 15 | 93.6 |
| GenSCO | 13.25 | 15 | 4.14 |
| ACO | 41.14 | 15 | 19.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 ( seconds; mean (standard deviation) over 10 seeds). Lower is better.
| Configuration | LIFT | ALNS | GENIS | VNS |
|---|---|---|---|---|
| C50_D4_K4 | 47.76 (0.00) | 47.83 (0.16) | 47.86 (0.10) | 47.82 (0.20) |
| C50_D4_K2 | 70.90 (0.53) | 72.00 (0.83) | 72.15 (1.58) | 71.98 (1.14) |
| C75_D5_K3 | 76.03 (0.46) | 77.03 (0.49) | 77.28 (0.79) | 77.38 (0.46) |
| C80_D2_K5 | 239.56 (0.29) | 243.57 (0.95) | 244.40 (0.66) | 245.71 (0.77) |
| C100_D2_K8 | 147.89 (0.89) | 149.66 (1.75) | 151.12 (1.25) | 151.12 (0.91) |
| C100_D2_K5 | 175.03 (1.44) | 181.14 (0.68) | 184.13 (1.30) | 184.05 (1.48) |
| C100_D3_K6 | 105.34 (0.59) | 115.61 (0.55) | 117.48 (0.73) | 117.95 (0.79) |
| C100_D4_K4 | 129.06 (1.00) | 130.95 (1.19) | 132.02 (1.38) | 132.01 (1.31) |
| C160_D4_K5 | 465.35 (0.73) | 473.67 (1.93) | 481.04 (4.25) | 483.18 (2.35) |
| C240_D6_K5 | 709.55 (3.26) | 706.49 (1.73) | 724.01 (5.75) | 725.41 (6.19) |
| C249_D2_K14 | 971.73 (2.79) | 992.17 (3.46) | 1031.13 (6.29) | 1031.82 (9.67) |
| C249_D3_K12 | 713.32 (3.62) | 751.01 (1.19) | 772.40 (3.77) | 779.35 (5.32) |
| C249_D4_K8 | 708.18 (3.28) | 743.16 (1.95) | 756.98 (3.92) | 773.69 (8.98) |
| C249_D5_K6 | 749.72 (2.05) | 769.11 (3.04) | 794.61 (9.82) | 799.86 (5.41) |
| C360_D9_K5 | 1028.57 (4.28) | 1052.12 (2.23) | 1103.56 (8.04) | 1119.31 (11.31) |
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 t, LIFT defines a noise prior m(⋅∣st) over ADD/DEL edits based on the current schedule st. It then samples a noisy edit 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 at that instructs the decoder D to produce a feasible successor schedule st+1.
The noise prior depends on the current schedule st, 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 st. 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:
Table R1. Average reduction in total arrival time achieved by LIFT over each variant.
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.