PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation

Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, Yeow Meng Chee

arXiv:2210.07686v2cs.LGcs.AI

TL;DR

Neural VRP models commonly train and test on the same distribution, while real-world instances may follow varied or unknown distributions. AMDKD distills multiple distribution-specific teachers into an adaptive, lightweight student, and reports competitive generalization to unseen instances with reduced inference resources.

  • Problem

    Neural VRP models trained and tested on the same distribution often achieve low solution quality on out-of-distribution instances, despite real-world distributions being varied or unknown.

    Source: §1 · pp. 1–2

  • Method

    AMDKD trains a shared student from multiple teachers trained on exemplar distributions and adaptively directs learning toward distributions the student finds difficult.

    Source: §1 · p. 2

  • Results

    AMDKD reports competitive generalization to unseen out-of-distribution instances, including random and benchmark cases, while consuming fewer inference resources.

    Source: §6 · p. 10

  • Takeaways & Limitations

    The results support lightweight generalist models for VRPs across unseen distributions within the evaluated scope.

    Source: §6 · p. 10

    Comparisons of runtime between traditional solvers and deep models may be difficult to make fairly because implementations and computing devices differ.

    Source: §5.3 · p. 9

Abstract

from arXiv · show

Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out-of-distribution instances, which are either randomly synthesized or adopted from benchmark datasets (i.e., TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.

1 Introduction

Neural VRP models often train and test on the same distribution, leaving their performance on other distributions limited. The paper proposes distilling knowledge from distribution-specific teachers into an adaptive, lightweight student.

1 Introduction

  • Deep VRP models often perform poorly on out-of-distribution instances, a concern for real-world cases with varied or unknown distributions.Prior generalization approaches use data augmentation from a specified distribution or require manually defined major and minor instances.Source: §1 · p. 2
  • The paper frames knowledge distillation as a way to transfer policies learned across distributions into one model for improved cross-distribution generalization.This contrasts with prior approaches based on data augmentation or distributionally robust optimization.Source: §1 · p. 2
  • AMDKD trains a shared student from multiple teachers trained on exemplar distributions, adaptively focusing on distributions where the student is struggling.The approach is applied to AM and POMO and aims to produce a lightweight generalist model.Source: §1 · p. 2
  • AMDKD performs favorably against backbone models and other generalization methods, especially on CVRPLIB, while using fewer inference resources; coupling it with EAS achieves new state-of-the-art performance.The contribution summary also reports analyses of the proposed designs.Source: §1 · p. 2

2 Related work

Related work covers neural construction and improvement methods for VRPs, then reviews approaches to cross-distribution generalization. The paper positions its approach against augmentation and robustness methods with limitations in scope or setup.

Neural construction models

  • Neural construction methods build tours sequentially, with AM and POMO among the representative architectures and EAS extending POMO for inference-time search.Other approaches use graph neural networks to learn graph-structured instance features.Source: §2 · p. 2

Neural improvement models

  • Neural improvement methods use learned policies to iteratively refine solutions, but generally require much longer inference time than construction methods for higher solution quality.Examples include learned rewriting, large-neighborhood search, and control of 2-opt operations.Source: §2 · pp. 2–3

Cross-distribution generalization

  • Cross-distribution approaches include instance augmentation and distributionally robust optimization, but prior methods may be limited to TSP or require manually defined major and minor instances.The paper also identifies generalization across problem sizes as future work.Source: §2 · p. 3

3 Preliminaries and notations

The preliminaries introduce the VRP objective, its variants and distributions, neural tour construction, and teacher–student knowledge distillation.

3.1 VRPs and their distributions

  • VRPs are modeled on a complete graph, with the objective of finding a feasible tour of minimum total edge cost; the paper focuses on TSP and CVRP.CVRP adds a depot, vehicle capacity, and customer demands, and permits multiple depot-returning subtours.Source: §3.1 · p. 3
  • VRP instances can follow diverse, potentially unknown coordinate distributions, and the paper distinguishes training distributions from unseen test distributions.The figure includes Uniform, Cluster, and Mixed as training distributions, with Expansion, Implosion, Explosion, Grid, and benchmark datasets for testing.Source: §3.1 · p. 3, Figure 1 · p. 4

3.2 Tour construction by deep models

  • Neural construction models sequentially build a tour by selecting unvisited nodes, with the final reward defined as the negative tour length.For TSP the construction has n steps; CVRP may require more because the depot can be revisited.Source: §3.2 · pp. 3–4

3.3 Knowledge distillation

  • Knowledge distillation transfers knowledge from complex teacher models to a smaller student, training it with a weighted combination of distillation and task losses.The distillation loss compares teacher and student outputs over training data using a statistical distance.Source: §3.3 · p. 4

4 Methodology

AMDKD distills knowledge from teachers trained on exemplar distributions into a shared student, with adaptive distribution selection and joint task/KD training. The student can be smaller than its teachers, trading solution quality against computational cost.

4.1 Overall structure and teacher (pre)-training

  • AMDKD trains a shared student by selecting an exemplar distribution and its teacher each epoch, then using student-generated trajectories for on-policy distillation.The student is trained with both task loss and teacher-derived knowledge-distillation loss.Source: §4.1 · p. 5, §4.2 · p. 6
  • Teachers are trained on Uniform, Cluster, and Mixed distributions, while the student is expected to generalize to unseen distributions such as Expansion, Implosion, Explosion, and Grid.The exemplar distributions can be replaced, and the scheme is assessed with AM and POMO backbones.Source: §4.1 · p. 5

4.2 Adaptive multi-distribution student training

  • Reducing student embedding dimensions from 128 to 64 cuts parameters by 61.8% with AM and 59.2% with POMO, while larger students usually perform better.Reducing encoder layers was also considered, but results were below expectation.Source: §4.2 · p. 6
  • Distribution-selection probabilities start equal and are later adapted to student performance on fixed validation sets for each exemplar distribution.Selection likelihood is proportional to the exponent of the student's gaps to LKH; stabilized probabilities may allow validation to stop early.Source: §4.2 · p. 6
  • The student jointly optimizes task loss and KL-divergence knowledge-distillation loss, with the task-loss weight set to α=0.5.The teacher evaluates the student-generated tour to provide the probability information used by the distillation loss.Source: §4.2 · p. 6
  • AMDKD can be paired with efficient active search at inference, and the resulting AMDKD+EAS is reported to achieve new state-of-the-art performance.The paper reports that off-policy teacher-generated tours perform worse than its on-policy approach.Source: §4.2 · p. 6

5 Experiments

Experiments evaluate AMDKD on TSP and CVRP, comparing lightweight students with teachers and other generalization methods across unseen distributions and benchmark datasets. Ablations and architecture variants examine the roles of the adaptive strategy, losses, exemplar distributions, and student size.

5 Experiments

  • Experiments use AM and POMO backbones, three exemplar distributions, and four unseen distributions, with test sets of 10,000 instances per distribution.The study covers TSP and CVRP at 20, 50, and 100 nodes; default student embeddings are reduced from 128 to 64 dimensions.Source: §5 · p. 7

5.1 Effectiveness analysis of AMDKD

  • AMDKD students improve overall performance across TSP and CVRP sizes while reducing parameters by 61.8% for AM and 59.2% for POMO.AMDKD-AM significantly outperforms its three teachers; AMDKD-POMO also boosts overall performance despite POMO's stronger baseline generalization.Source: §5.1 · pp. 7–8

5.2 Generalization analysis of AMDKD

  • AMDKD achieves competitive generalization on unseen in-distribution and out-of-distribution instances, favorably comparing with baselines across TSP and CVRP; AMDKD+EAS also surpasses LKH3 on CVRP-100 with shorter time.On TSPLIB and CVRPLIB, AMDKD variants generally outperform compared baselines, with AMDKD+EAS achieving the smallest gaps among them.Source: Table 2 · p. 8, §5.2 · p. 9, Table 3 · p. 9
  • AMDKD-AM (64) and AMDKD-POMO (64) have significantly faster inference than LCP and DACT while achieving similar or lower gaps.The authors caution that runtime comparisons between traditional solvers and deep models may be difficult to make fairly because implementations and computing devices differ.Source: §5.2 · p. 9, §5.3 · p. 9
  • On selected TSPLIB and CVRPLIB instances with 100≤n≤200, AMDKD generally outperforms compared methods, while AMDKD+EAS achieves the smallest gaps.AMDKD-POMO is an exception to the general pattern against POMO# (128) on TSPLIB, but performs significantly better on harder CVRPLIB instances.Source: §5.2 · p. 9, Table 3 · p. 9

5.3 Further analysis of AMDKD

  • Ablations indicate that the adaptive strategy enhances learning effectiveness, both losses contribute prominently to gradient updates, and an off-policy variant impairs distillation.The ablation study uses CVRP-50 and TSP-50.Source: §5.3 · p. 9, Table 4 · p. 10
  • For CVRP-50, AMDKD-POMO (128) has a 0.81% average optimality gap versus 0.90% for AMDKD-POMO (64), at higher training, parameter, and inference costs.The 128-dimensional model takes 12 versus 7 days to train, has 1.20 M versus 0.49 M parameters, and takes 1.3 versus 1.1 minutes to infer.Source: §5.3 · pp. 9–10, Figure 3 · p. 10
  • With Expansion, Implosion, Explosion, and Grid as exemplars, AMDKD-POMO* outperforms POMO trained separately on those distributions overall.This result supports AMDKD's effectiveness with a different set of exemplar distributions.Source: §5.3 · p. 10, Table 5 · p. 10

6 Conclusions and future work

AMDKD transfers policies from exemplar distributions into one student through adaptive, turn-based teacher use, yielding competitive generalization on unseen instances with lower inference resources. The appendix details the coordinate distributions used to generate instances.

6 Conclusions and future work

  • AMDKD transfers policies learned from exemplar distributions into a single student, but its boost is not guaranteed to be significant across every unseen distribution and backbone.Future work includes larger problem sizes, other backbone models, online distillation, validation-dataset quality, and interpretability.Source: §6 · p. 10

A Details of the considered distributions

  • The paper generates training and testing VRP instances using Uniform, Cluster, and Mixed node-coordinate distributions following and TSPLIB, plus Expansion, Implosion, Explosion, and Grid following.Source: A Details of the considered… · p. 14
  • Mixed instances combine Uniform nodes with nodes from one Cluster, while Cluster instances use three Gaussian clusters with standard deviation 0.07.Expansion moves nodes near a sampled line farther away, then normalizes coordinates to [0, 1]^2.Source: A Details of the considered… · p. 14
  • Implosion contracts nodes inside a radius-0.3 circle toward a smaller circle, while Explosion moves them outside a radius-0.3 circle before normalization.Grid rearranges nodes inside a placed square of width and height 0.3 into a quadratic grid.Source: A Details of the considered… · p. 14

B Details of compared baselines

The compared baselines include exact and heuristic solvers, neural construction and improvement methods, and hybrid approaches. Distribution-mixture augmentation helps some construction methods, but does not consistently improve generalization; the authors offer possible reasons AMDKD may do better.

B Details of compared baselines

  • LCP, HAC, and DACT were retrained using mixed instances from the three exemplar distributions, following their original settings where applicable.The cited table is identified as evaluating distribution-mixture effects, but the supplied passage does not give its cell values.Source: B Details of compared baselines · p. 15, Table 6 · p. 15
  • The baseline suite includes Gurobi for optimal TSP solutions and LKH for near-optimal CVRP solutions, alongside neural LCP, HAC, and DACT.LCP is a seeder-reviser method, HAC fine-tunes AM on generated instances, and DACT guides local search.Source: B Details of compared baselines · p. 15

Effects of distribution mixture augmentation

  • Mixture augmentation improves POMO and AM generalization on TSP-100 and CVRP-100, but does not consistently help DACT or LCP.DACT# performs worse than uniform-trained DACT on CVRP-100, while LCP (U) slightly outperforms LCP# on TSP-100.Source: B Details of compared baselines · pp. 15–16

Why AMDKD could be better than distribution mixture augmentation?

  • AMDKD usually generalizes better than mixture-trained models, though the authors describe their explanations as possible intuitions rather than settled findings.They suggest adaptive teacher selection can focus on harder distributions, while one-distribution-per-epoch training may reduce mixed-data instability and reward-range differences.Source: B Details of compared baselines · p. 16

C.1 Effects of multiple teacher co-training.

On CVRP-50 across seven test distributions, AMDKD-POMO outperforms a version that uses multiple teachers simultaneously. The authors attribute the difference to non-specialized teachers interfering with distillation.

C.1 Effects of multiple teacher co-training.

  • AMDKD-POMO significantly outperforms its simultaneous multi-teacher version on overall CVRP-50 gaps across seven test distributions.The comparison uses a Wilcoxon test; Figure 4 marks the difference as significant at p-value = 0.02 < 0.05.Source: Figure 4 · p. 16, §C.1 · p. 16

C.2 Effects of validation datasets.

Changing validation-set size produces no statistically significant performance difference at the tested sizes, while per-epoch evaluation adds a small reported training cost. The appendix also describes choices for adaptive-selection timing, steps per epoch, and total epochs.

C.2 Effects of validation datasets.

  • Validation sets of 1,000, 2,000, or 500 examples show no statistically significant performance differences in the reported comparisons.The authors report that V = 1,000 evaluation takes about 1% of training time per epoch for AMDKD-AM on CVRP-100; teacher-selection likelihood eventually stabilizes, allowing evaluation to stop around 3,000 epochs in that example.Source: §C.2 · pp. 16–17, Figure 5 · p. 17, Figure 6 · p. 17

C.3 Effects of different hyper-parameters.

  • AMDKD-AM starts adaptive teacher selection around epoch 500, whereas AMDKD-POMO starts at epoch 1; the AMDKD-AM comparison shows no significant difference between those settings.Figure 8 compares E′ = 500 with E′ = 1 on CVRP-50.Source: §C.3 · pp. 17–18, Figure 8 · p. 18
  • The steps per epoch parameter T controls how long the student learns from a selected teacher before it may switch; the paper uses T = 20 for POMO and reduces AM's original value to 250.The authors describe the reduction for AM as an empirical trade-off.Source: §C.3 · p. 18
  • Total training epochs follow backbone settings but vary by problem size and task, with the paper attributing longer runs to potentially greater task hardness.Figure 9 plots AMDKD-POMO CVRP training curves by epoch against average gaps on three exemplar distributions.Source: §C.3 · p. 18, Figure 9 · p. 18

C.4 Stability studies of AMDKD.

Across unseen in-distribution and out-of-distribution distributions, AMDKD-AM significantly outperforms AM#; both show very small fluctuations across random seeds.

C.4 Stability studies of AMDKD.

  • p < 0.001: AMDKD-AM significantly outperforms AM# on every unseen in-distribution and out-of-distribution distribution.The comparison is based on a Wilcoxon test.Source: §C.4 · p. 18
  • < 0.001: AMDKD-AM and AM# each show fluctuations below 0.001 across 10 CVRP-50 runs with different random seeds.The paper uses CVRP-50 as the stability example.Source: §C.4 · p. 18, Figure 10 · p. 18
  • Greedy decoding makes AMDKD-POMO and POMO# results expected to be stable with almost no fluctuation.Source: §C.4 · p. 18

D Detailed results on benchmark datasets

On TSPLIB and CVRPLIB benchmark instances, AMDKD outperforms the listed baselines and reaches neural-method state-of-the-art performance; the paper also reports open-source assets and MIT licensing for its code and data.

D Detailed results on benchmark datasets

E Used assets and licenses

D Detailed results on benchmark datasets

Related papers

Loading 2210.07686v2…