PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer

Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, Jing Tang

arXiv:2110.02544v3cs.LGcs.AI

TL;DR

Existing Transformer positional encodings are poorly suited to VRP improvement because they fuse node and positional information and mishandle cyclic solutions. DACT separates these aspects, uses cyclic positional encoding and collaborative attention, and trains with reinforcement learning plus curriculum learning. Experiments report stronger improvement performance and generalization across problem sizes on synthetic and benchmark instances.

  • Problem

    Existing positional encodings fuse node and positional information and do not properly represent cyclic VRP solution sequences.

  • Method

    DACT learns separate node and positional embeddings, uses cross-aspect collaborative attention with cyclic positional encoding, and applies reinforcement learning with curriculum learning.

  • Results

    DACT outperforms existing Transformer-based improvement models and generalizes across different problem sizes on synthetic and benchmark instances.

  • Takeaways & Limitations

    DACT provides a routing improvement model that represents node and positional features separately while explicitly capturing solution circularity and symmetry.

  • Takeaways & Limitations

    DACT is currently more useful for learning improvement models than construction models.

Abstract

from arXiv · show

Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its positional encoding (PE) method is not suitable in representing VRP solutions. This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately, instead of fusing them together as done in existing ones, so as to avoid potential noises and incompatible correlations. Moreover, the positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions (i.e., cyclic sequences). We train DACT using Proximal Policy Optimization and design a curriculum learning strategy for better sample efficiency. We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively.

1 Introduction

VRPs are difficult NP-hard routing problems whose solutions are cyclic node sequences, making positional representation important for improvement models. DACT addresses limitations of conventional Transformer positional encoding by separating node and positional embeddings and modeling cyclic structure.

  • VRPs seek optimal routes for one or more vehicles serving customers, but remain challenging because of their NP-hard nature.
  • VRP solutions are node sequences, making Transformer architectures natural candidates for encoding them.
  • Absolute positional encoding can introduce mixed correlations and noise, while unified node-position representations may be unsuitable for routing tasks.
  • DACT learns separate node and positional embeddings, uses cross-aspect attention, and synthesizes action proposals from both aspects.
  • Cyclic positional encoding captures the circularity and symmetry of VRP solutions, while curriculum learning improves reinforcement-learning sample efficiency.

2 Related work

Transformer positional encodings represent sequence position, but existing methods fuse node and positional information and do not properly handle cyclic VRP inputs. DACT instead uses separated aspects to represent these features collaboratively.

  • Positional encoding (PE) in Transformer: Absolute positional encoding adds each position embedding to its corresponding word or node embedding before Transformer encoding.
  • Positional encoding (PE) in Transformer: Relative positional encoding augments attention with learnable parameters representing relative position differences.
  • Positional encoding (PE) in Transformer: TUPE separates projections for semantic and positional information to reduce mixed and noisy attention correlations.
  • Positional encoding (PE) in Transformer: Existing positional encodings are less effective for VRPs because they fuse node and positional information and cannot properly handle cyclic input sequences.
  • Deep models for VRP: Prior VRP solvers include RNN-, GNN-, and Transformer-based construction or improvement models, with Transformer methods including AM and POMO.

3 Problem formulation

The paper formulates VRP improvement as iterative reinforcement learning over complete solutions represented by node and positional features. At each step, the policy selects a node pair and applies a local operator to obtain the next state.

  • Problem formulation: A VRP instance contains N nodes with coordinate and problem-specific features, while a solution is an ordered node sequence with positional indices.
  • Problem formulation: The objective is to minimize total travel distance subject to problem-specific constraints.
  • Problem formulation: The policy iteratively improves a complete initial solution by selecting node pairs and applying 2-opt, insert, or swap operators.
  • Problem formulation: 2-opt reverses a segment, insert places one node after another, and swap exchanges the positions of two nodes.
  • Markov Decision Process: The action is a node pair, and the deterministic transition applies the selected operator while masking infeasible solutions.
  • Markov Decision Process: The policy samples node-pair actions at each time step during both training and inference.

4 Dual-aspect collaborative Transformer model

DACT represents node and positional features in separate embedding streams, collaborates across aspects, and uses cyclic positional encoding to model cyclic VRP solutions. Its encoder-decoder architecture is trained with PPO and curriculum learning for sample efficiency.

  • Dual-aspect solution representation: DACT learns separate node feature embeddings and positional feature embeddings rather than one unified VRP-solution representation.NFEs represent nodes, while PFEs represent positions.
  • Dual-aspect solution representation: Cyclic positional encoding initializes positional embeddings from cyclic Gray codes designed for cyclic sequences.The encoding preserves cyclic adjacency and symmetry through periodic, reflectional patterns with longer periods for higher digits.
  • The encoder: The encoder uses L = 3 stacked DAC encoders with independent feed-forward sub-layers and skip connections with layer normalization.Each DAC encoder retains relatively independent NFEs and PFEs while processing them through shared DAC-Att sub-layers.
  • The encoder: The DAC encoder computes self-attention separately for each aspect and shares cross-aspect correlations as referential attention.Aspect-specific correlations aim to reduce noise while allowing node and positional streams to collaborate.
  • The decoder: The decoder independently generates node-pair selection proposals from both aspects, aggregates them, and normalizes feasible actions into a final distribution.Multi-head compatibility supplies aspect-specific proposal matrices, while the aggregation network outputs pair likelihoods before masking and Softmax normalization.
  • Training: DACT is trained with proximal policy optimization and a curriculum-learning strategy intended to improve sample efficiency.The curriculum addresses the limited observation of high-quality states when training uses fewer steps than inference.

5 Experiments

Experiments evaluate DACT on TSP and CVRP against learning-based and conventional baselines, with ablations targeting dual-aspect representation, CPE, and curriculum learning. DACT achieves strong solution quality, generalization, and training efficiency, while remaining highly competitive in inference time.

  • Experimental setup: DACT is evaluated on TSP and CVRP at N = 20, 50 and 100 using 2-opt after preliminary comparisons with swap and insert.Instances are randomly generated on the fly, and 2-opt performs best for both problems.
  • Comparison studies: DACT with 4 augments achieves a 0.09% gap on TSP100, the lowest objective values and gaps among purely learning-based models.This configuration outstrips POMO with 8 augments, although serial data augmentation increases inference time.
  • Comparison studies: DACT with T=5k achieves better CVRP objective values than NeuRewriter and consistently outperforms Wu et al. across cases.The supplied result passage reports these comparisons without providing the complete case-by-case values.
  • Comparison studies: DACT produces significantly lower average gaps than POMO with 8 augments on TSPLIB and CVRPLIB benchmark datasets.The result indicates stronger benchmark generalization despite DACT's longer inference time.
  • Ablation studies: DACT with fewer parameters consistently outperforms the single-aspect SA-T model on TSP50 and TSP100.SA-T uses CPE, multi-head attention, and curriculum learning for a fair comparison.
  • Ablation studies: CPE improves generalization across problem sizes, while curriculum learning significantly improves sample efficiency and reduces training variance.CPE enables DACT to outperform DACT-PE and OR-Tools on TSP100; the curriculum-learning result averages five runs with 90% confidence intervals.

6 Conclusions and future work

The paper concludes that DACT combines separate node and positional embeddings with CPE and curriculum learning to improve routing improvement models. It identifies extension to construction models and faster inference as future directions.

  • Conclusions: DACT separates node and positional embeddings and uses CPE to capture circularity and symmetry in VRP solutions.The model also uses curriculum learning to improve reinforcement-learning training efficiency.
  • Conclusions: Experiments on synthetic and benchmark datasets support DACT's effectiveness in inference and generalization.
  • Future work: A stated limitation is that DACT is currently more useful for learning improvement models than construction models.Future work includes extending DACT to construction models and speeding inference through diverse rollouts or model compression.

A Issues in existing Transformer-based model for VRP

The existing Transformer formulation fuses node and positional information, creating mixed correlations that may introduce noisy biases in VRP improvement models. The paper motivates separated representations and analyzes CPE frequencies for cyclic and adjacency properties.

  • Mixed correlations: Adding node and positional embeddings creates four attention terms: node-to-node, position-to-position, node-to-position, and position-to-node.These terms share projection matrices despite representing different information types.
  • Mixed correlations: Mixed correlations use Query and Key projections from different embedding types, producing node-to-position and position-to-node interactions.The paper defines correlation as the dot product between Query and Key in self-attention.
  • Mixed correlations: The cross-aspect correlations show random patterns across node pairs, including strong associations with nodes near the solution's end.The paper states that these patterns may yield biased attention and affect learned-heuristic accuracy and performance.
  • Cyclic positional encoding: CPE increases wavelength along vector dimensions and fixes the last half of wavelengths to N to preserve cyclic and adjacency similarity properties.For different problem sizes, generating frequencies from the target size often works better for small size differences, while reusing pretrained frequencies can work better for larger differences.

C Training algorithm

DACT is trained with an actor-critic PPO procedure that uses curriculum-initialized states, while TSP and CVRP states encode problem-specific solution features. CVRP training additionally handles variable-length routes through dummy depots, and inference stability is evaluated across repeated runs.

  • PPO training: DACT training adapts actor-critic PPO, using a value-function baseline to reduce objective variance.The value function processes concatenated node and positional embeddings before pooling and feed-forward prediction.
  • PPO training: Each training batch is generated on the fly, initialized with curriculum learning, and optimized through n-step return estimates and clipped PPO updates.The procedure updates policy and value networks over repeated mini-batch epochs with learning-rate decay.
  • Problem representations: TSP states use node coordinates, whereas CVRP states use coordinates, neighboring distances, and route-demand features.The CVRP node representation contains seven dimensions, including coordinates, adjacent distances, and cumulative route demands.
  • Problem representations: CVRP solutions can have different lengths because vehicles may return to the depot multiple times and form different numbers of sub-routes.This variability complicates parallel batch training.
  • Problem representations: Multiple dummy depots equalize CVRP solution lengths and allow the policy to learn the number and lengths of sub-routes.The experiments use 10 dummy depots for CVRP20 and 20 for CVRP50 and CVRP100.
  • Stability analysis: Figure 9 evaluates DACT without augmentation over 10 independent runs of 10,000 TSP100 and CVRP100 instances.The corresponding box plots compare objective values across inference step limits.

E More discussion on the experiments

The experiments specify inference, generalization, optimization, discounting, and gradient-clipping settings for three TSP and CVRP problem sizes.

  • Experimental settings: Inference uses T_r = 250, while benchmark generalization uses T_r = 10 for TSPLIB and 20 for CVRPLIB.The gradient norm is clipped by size-specific limits, and γ = 0.999 is used for both problems.

E.2 Training

Training uses on-the-fly batches, PPO with problem-specific rollout settings, and decaying Adam learning rates for the policy and value networks.

  • Training configuration: Training runs for 200 epochs with 20 batches per epoch and batch size 600, reduced to 512 for CVRP100 because of GPU memory limits.The PPO settings are n = 4 and T_train = 200 for TSP, versus n = 5 and T_train = 250 for CVRP.
  • Training configuration: PPO performs K = 3 mini-batch updates with clipping threshold ε = 0.1 and Adam learning rates 10^-4 for π_θ and 3×10^-5 for v_φ.Both learning rates decay by β = 0.985 per epoch.

E.3 Stability analysis of our DACT

The stability analysis examines objective-value variation across repeated inference runs on TSP100 and CVRP100 under multiple step limits.

  • Stability results: The box-plot ranges remain within 0.005 across all tested cases, indicating limited variation across runs and inference step limits.The evaluation uses 10 independent runs on 10,000 testing instances for each problem.

E.4 Generalization on benchmark datasets

DACT is evaluated for generalization on TSPLIB and CVRPLIB instances that differ from the synthetic training distributions. Across these benchmarks, it outperforms Transformer-based and other neural baselines, with longer inference and augmentation further improving solution quality.

  • Benchmark setup: DACT is tested on TSPLIB and CVRPLIB instances with sizes between 50 and 200, or 100 and 200 for CVRPLIB.The benchmark instances may have clustered customer locations, corner depot locations, and other distributions unlike training instances.
  • TSPLIB: With T=10k and four augments, DACT achieves the lowest overall average gap on TSPLIB and the best performance on most instances.It first surpasses OR-Tools and Wu et al. at T=10k, then further reduces gaps with four augments.
  • CVRPLIB: On CVRPLIB, DACT (T=5k) outperforms Wu et al., OR-Tools, AM-sampling, and POMO×8 augment on every instance by gap.With T=10k and six augments, DACT further reduces the overall average gap to the lowest value.
  • Overall comparison: The results establish DACT as the new state-of-the-art generalization performer among existing Transformer-based models on TSPLIB and CVRPLIB.The paper contrasts DACT’s benchmark generalization with POMO×8 augment’s stronger synthetic-instance performance but weaker benchmark generalization.
Loading 2110.02544v3…