An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem

Bingjie Li, Guohua Wu, Yongming He, Mingfeng Fan, Witold Pedrycz

The Vehicle Routing Problem (VRP) is a cornerstone of logistics, impacting everything from your morning grocery delivery to global supply chains. Because it is NP-hard, finding the "perfect" route for a fleet of vehicles becomes exponentially difficult as the number of stops increases. Traditionally, we’ve relied on slow exact solvers or "hand-crafted" heuristics designed by experts.

A recent paper by Li et al., titled "Overview and Experimental Study of Learning-based Optimization Algorithms for the Vehicle Routing Problem," explores a third way: Learning-based Optimization (LBO). Instead of hard-coding rules, can we train neural networks to "learn" how to route?

TL;DR

This paper provides a comprehensive taxonomy of learning-based optimization (LBO) for the VRP, categorizing methods into "end-to-end" and "step-by-step" approaches. Through rigorous benchmarking of four representative algorithms against traditional solvers, the authors demonstrate that while LBOs offer incredible inference speed and strong generalization, their performance is heavily influenced by the underlying data distribution and problem scale.

What Problem Does This Paper Address?

The VRP asks: What is the set of optimal routes for a fleet of vehicles to deliver to a specific set of customers?

The challenge is twofold:

  1. Complexity: Exact algorithms (like Branch-and-Bound) provide optimal solutions but are too slow for large-scale, real-time applications.
  2. Manual Effort: Heuristics (like Tabu Search or Ant Colony Optimization) are faster but require tedious parameter tuning and expert domain knowledge to design effective search rules for every new VRP variant.

The authors investigate whether LBO can bridge this gap by automatically extracting optimization strategies from data, moving the heavy computational burden from "online" solving to "offline" training.

Methods

The paper divides the LBO landscape into two primary frameworks:

  • End-to-End (E2E) Approaches: These models act like a "black box" that takes problem features (coordinates, demands) and outputs a complete solution in one go. They often use architectures like Pointer Networks or Transformers and are typically trained via Reinforcement Learning (RL) to minimize total route length.
  • Step-by-Step (SbS) Approaches: These models learn to iteratively improve an initial (often poor) solution. They might learn "rewrite" rules or act as "destroy and repair" operators within a Large Neighborhood Search (LNS) framework.

The authors specifically benchmarked:

  • AM (Attention Model): A classic E2E transformer-based model.
  • ASWTAM: An improved E2E model that uses step-wise embedding updates.
  • L2I (Learning to Improve): An SbS model that selects from multiple heuristics to iteratively refine routes.
  • Rewriter: An SbS model that learns local rewriting rules (like 2-opt).

Datasets

The study utilized three distinct test sets to evaluate different aspects of performance:

  1. Set 1 (Standard): 300 instances with 20, 50, and 100 nodes, following a uniform distribution (matching the training data).
  2. Set 2 (Distribution Shift): 300 instances where node locations follow a Gamma distribution, testing how well models generalize to non-uniform, clustered data.
  3. Set 3 (Scalability): Nine classic benchmarks from Uchoa et al. (2017), with nodes ranging from 100 to 200, to test how models trained on small problems handle larger ones.

Key Insights and Ideas

  • The Generalization Gap: E2E models are "brittle." While they are lightning-fast, their performance drops significantly when the test data distribution (e.g., Gamma) differs from the training data (Uniform).
  • Iterative is Robust: Step-by-step (SbS) approaches, particularly L2I, showed much better scalability and robustness. By learning how to improve rather than just construct, they can handle larger and more complex benchmarks more effectively.
  • Offline Training vs. Online Inference: The "aha moment" for LBO is the trade-off. While training a model might take hours or days, it can solve a new VRP instance in milliseconds—orders of magnitude faster than traditional meta-heuristics like Ant Colony Optimization.
  • Dynamic Embeddings Matter: The ASWTAM results suggest that updating the "context" of the problem as the route is built (dynamic embeddings) significantly improves construction quality over static models.

Key Results

  • Quality: On standard uniform sets, L2I achieved results nearly as good as the exact solver (Gurobi) and outperformed traditional heuristics like OR-Tools in many cases.
  • Speed: For a 100-node problem, LBO models typically solved instances in under 1 second, whereas meta-heuristics like Tabu Search took over 100 seconds to reach comparable quality.
  • Scalability: L2I maintained a gap of less than 0.1% from the optimal on several large-scale benchmarks, proving that LBO isn't just for "toy" problems.

Limitations and Future Work

The authors identify several hurdles for the field:

  1. Data Dependency: Models are still too sensitive to the distribution of the training data.
  2. Complexity Ceiling: Solving VRPs with hundreds of constraints (time windows, heterogeneous fleets, etc.) remains difficult for pure E2E models.
  3. The Need for Decomposition: For truly massive problems (1000+ nodes), the authors suggest a "divide and conquer" approach—decomposing the large problem into sub-problems that LBO models can handle.
  4. Hybridization: The most promising path forward appears to be "Learning-assisted Heuristics"—using neural networks to guide traditional, robust search algorithms.

Summary updated

Abstract

The vehicle routing problem (VRP) is a typical discrete combinatorial optimization problem, and many models and algorithms have been proposed to solve the VRP and its variants. Although existing approaches have contributed significantly to the development of this field, these approaches either are limited in problem size or need manual intervention in choosing parameters. To solve these difficulties, many studies have considered learning-based optimization (LBO) algorithms to solve the VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches. We performed a statistical analysis of the reviewed articles from various aspects and designed three experiments to evaluate the performance of four representative LBO algorithms. Finally, we conclude the applicable types of problems for different LBO algorithms and suggest directions in which researchers can improve LBO algorithms.
BibTeX
@article{li2022overview,
  author = {Bingjie Li and Guohua Wu and Yongming He and Mingfeng Fan and Witold Pedrycz},
  title = {{An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem}},
  journal = {IEEE CAA J. Autom. Sinica},
  year = {2022},
  url = {https://openreview.net/forum?id=k6IIXZSbOw},
}
Figure