Source-linked AI summary
Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems
Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
TL;DR
Vehicle routing requires effective construction heuristics, but single-policy methods can produce insufficiently diverse solutions. The paper introduces MDAM with customized beam search and Embedding Glimpse, and reports superiority to state-of-the-art deep learning methods across six routing problems.
Problem
Existing construction policies generate insufficiently diverse solutions, limiting the chance of finding good solutions among multiple possible optima.
Method
MDAM trains multiple diverse construction policies, uses separate decoder beams, and adds Embedding Glimpse to provide more informative embeddings.
Results
The method significantly outperforms state-of-the-art deep learning methods on six routing problems and produces solutions close to traditional optimized solvers in reasonable time.
Takeaways & Limitations
Multi-decoder diversity and Embedding Glimpse improve learned routing construction policies, while customized search preserves diversity during solution generation.
Abstract
from arXiv · showhide
We present a novel deep reinforcement learning method to learn construction heuristics for vehicle routing problems. In specific, we propose a Multi-Decoder Attention Model (MDAM) to train multiple diverse policies, which effectively increases the chance of finding good solutions compared with existing methods that train only one policy. A customized beam search strategy is designed to fully exploit the diversity of MDAM. In addition, we propose an Embedding Glimpse layer in MDAM based on the recursive nature of construction, which can improve the quality of each policy by providing more informative embeddings. Extensive experiments on six different routing problems show that our method significantly outperforms the state-of-the-art deep learning based models.
1 Introduction
Routing problems are computationally difficult, motivating learned construction heuristics. The paper addresses limited solution diversity and embedding quality with multiple decoders, customized search, and Embedding Glimpse.
- Motivation: Routing problems are NP-hard, while exact methods have exponential worst-case complexity despite optimality guarantees.Approximate heuristics therefore provide an alternative to exact optimization for these problems.
- Motivation: Deep learning methods learn construction heuristics by repeatedly adding nodes through encoder-decoder models.The encoder produces node embeddings, and the decoder predicts valid next-node probabilities.
- Limitations: Existing methods train one policy, so sampling or beam search may generate insufficiently diverse solutions.Reduced diversity leaves fewer opportunities to find better solutions when multiple optima exist.
- Proposed method: MDAM trains multiple attention decoders with unshared parameters, while customized beam search maintains separate beams to preserve their distinct patterns.A KL-divergence loss further encourages dissimilar node-selection distributions among decoders.
- Proposed method: Embedding Glimpse removes visited nodes from the top encoder attention layer, providing more informative embeddings for subsequent node selection.The design exploits the recursive construction process to improve each policy’s solution quality.
- Results: Experiments on six routing problems significantly outperform state-of-the-art deep reinforcement learning methods and approach or exceed traditional heuristics and solvers in short inference time.The authors frame the contribution as stronger learned heuristics rather than general superiority over highly optimized solvers.
2 Related Works
Related work includes encoder-decoder, graph-based, and rewriting approaches for combinatorial optimization. These methods differ in supervision, scalability, graph representation, and parallelizability.
- Encoder-decoder methods: Pointer Network uses LSTM encoder-decoder models, while REINFORCE removes the need for optimal labels and supports larger TSP instances.The supervised approach is limited to small scales because obtaining optimal-solution labels is expensive.
- Graph-based methods: Deep Q-Learning with Structure2Vec addresses several combinatorial problems but performs unsatisfactorily on TSP because its fully connected graph structure is uninformative.The same representation is more useful for problems where graph connectivity carries crucial information.
- Rewriting and improvement methods: NeuRewriter can outperform sampling results but uses sequential rewriting operations, making it naturally non-parallelizable for an instance.Other work learns local-move types and searches greedily for the best move of the selected type.
3 Model
MDAM combines multiple unshared attention decoders, diversity-preserving beam search, and an Embedding Glimpse layer to improve learned routing construction heuristics.
- Multi-Decoder Attention Model: MDAM trains multiple attention decoders with unshared parameters to produce diverse construction trajectories.A KL-divergence regularizer encourages the decoders to output dissimilar node-selection distributions.
- Multi-Decoder Attention Model: MDAM uses a Transformer encoder with self-attention blocks, skip connections, batch normalization, and feed-forward projections to embed routing nodes.The decoders use these embeddings to assign probabilities to valid next nodes during construction.
- Customized Beam Search: Customized beam search maintains a separate beam for each decoder, preserving diversity while selecting among candidate solutions.Each decoder searches independently, with its solutions sharing a consistent construction pattern.
- Embedding Glimpse Layer: The Embedding Glimpse layer masks visited nodes in the top attention layer to approximate re-embedding only unvisited nodes.Lower attention layers remain fixed, while part of the layer can be precomputed once.
- Training: Training combines REINFORCE losses from decoder trajectories with a KL-divergence term applied at the first construction step.The greedy result from the best previous-epoch model supplies the baseline for the tour-length objective.
4 Experiments
Experiments on six routing problems evaluate MDAM against learning-based and traditional baselines, while ablations and decoder analyses examine its components and diversity. MDAM improves solution quality across tested settings, with efficiency that remains competitive with deep-learning methods.
- Experimental Setup: Experiments cover six routing problems, including TSP and CVRP instances with 20, 50, and 100 nodes.Instances use two-dimensional Euclidean distances, with CVRP vehicle capacities fixed by problem size.
- Comparative Study: MDAM is compared with strong deep-learning models on 10,000 test instances sampled from the training distributions.Concorde supplies optimal TSP benchmarks, while LKH3 supplies CVRP benchmark solutions.
- Efficiency: MDAM computation time is accepted relative to deep-learning methods, though specialized solvers can be faster on some problems.The paper reports MDAM as generally faster than traditional algorithms when solution quality is comparable.
- Ablation Study: Both the Multi-Decoder structure and Embedding Glimpse consistently improve greedy-policy quality across TSP and CVRP instance sets.The Multi-Decoder structure adds inference time, whereas Embedding Glimpse provides smaller gains with little additional computation overhead.
- Analysis of MDAM: All decoders perform similarly on CVRP20, with no decoder consistently dominant or non-contributing in greedy decoding or beam search.Winning counts exceed solely winning counts, indicating that multiple decoders often find the best solution.
5 Conclusions and Future Work
The paper presents a reinforcement-learning model for learning routing construction heuristics through multiple decoders, customized beam search, and an Embedding Glimpse layer. It reports stronger performance than state-of-the-art deep-learning methods across six routing problems and identifies more flexible decoder collaboration as future work.
- Conclusions: MDAM learns distinct construction patterns with multiple decoders and exploits them through a customized beam-search scheme.An Embedding Glimpse layer provides the decoders with more informative embeddings.
- Conclusions: MDAM outperforms state-of-the-art deep-learning methods on six routing problems and produces solutions close to highly optimized traditional solvers within reasonable time.
- Future Work: Future work will allow flexible decoder counts and enable decoders to collaborate on joint decisions rather than acting individually.
More details on the Comparative Study
Across routing variants, MDAM generally outperforms learning and optimization baselines, while its relative advantage varies by problem size and uncertainty. The comparisons cover SDVRP, OP, PCTSP, and SPCTSP.
- SDVRP: On SDVRP, MDAM significantly outperforms RL and AM with greedy decoding, and also beats their beam-search or sampling versions across problem sizes.The comparison includes RL beam search and AM sampling.
- OP: For OP, MDAM gives the best solutions at n=50 but falls slightly short of Compass at n=100.Gurobi cannot find optimal solutions for 50- and 100-node instances within the stated computational setting.
- PCTSP: Learning-based methods produce solutions comparable to optimization baselines in much shorter time, while MDAM outperforms AM on every PCTSP instance size.The passage contrasts solution quality and runtime relative to the listed solvers.
- SPCTSP: For SPCTSP, MDAM surpasses both REOPT variants by relatively large margins, indicating advantages for construction heuristics under prize uncertainty.The baselines are REOPT all and REOPT half.
More Analysis of MDAM
Additional analyses examine merging, decoder count, temperature-tuned baselines, and generalization to larger CVRPs. They consistently support exploiting decoder diversity, while MDAM remains stronger than the tuned AM baseline in the reported comparisons.
- Effectiveness of the merging technique: Merging significantly boosts five-decoder beam-search performance by eliminating inferior partial solutions.The comparison uses beam size B=50 and evaluates optimality gaps.
- Impact of number of decoders in beam search: With beam size B=50, results consistently improve as the number of decoders increases from 1 to 3 to 5.The analysis suggests further gains may be possible with more than five decoders.
- Comparing to AM with different temperature: Temperature tuning improves AM sampling with 1,280 solutions, but MDAM beam search with B=30 or B=50 still wins by large margins.The comparison uses various softmax temperatures and identifies smaller temperatures as preferable for larger CVRPs.
- Generalization Ability: MDAM trained on 100-node CVRPs generalizes better than AM on directly tested CVRP150 and CVRP200 instances.Both greedy decoding and beam-search comparisons are reported, including AM sampling with 1,280 solutions.