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

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

Abstract

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 a lot to the development of this field, these approaches either are limited in problem size or need manual intervening in choosing parameters. To solve these difficulties, many studies have considered the 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.

Introduction

The Vehicle Routing Problem (VRP) is a fundamental challenge in logistics and supply chain management. It involves determining the optimal set of routes for a fleet of vehicles to deliver goods to a specific set of customers while minimizing costs, typically distance or time. As an NP-hard problem, the complexity of VRP grows exponentially with the number of nodes, making exact solutions computationally prohibitive for large-scale applications.

Traditionally, researchers have relied on exact algorithms for small instances and hand-crafted heuristics for larger ones. However, these methods often require significant domain expertise and manual parameter tuning. Recently, Learning-Based Optimization (LBO) has emerged as a promising alternative, leveraging neural networks to automatically learn routing strategies from data.

Taxonomy of VRP Algorithms

To understand where LBO fits, it is helpful to categorize the broad landscape of VRP solvers. Algorithms are generally divided into exact methods, which guarantee optimality but lack scalability, and approximate solutions, which offer practical performance for larger problems.

Taxonomy of VRP solution algorithms, highlighting the position of Learning-Based Optimization.

LBO algorithms represent a subset of approximate solutions that utilize machine learning—often reinforcement learning—to either construct solutions from scratch or iteratively improve existing ones. As shown in the taxonomy, LBO approaches are further divided into end-to-end and step-by-step methodologies.

Learning-Based Optimization Frameworks

The research landscape for LBO is primarily split into two paradigms:

  1. End-to-End (E2E) Approaches: These models (e.g., Pointer Networks, Transformers) map problem instances directly to solutions. They are highly efficient during inference but can be sensitive to changes in data distribution.
  2. Step-by-Step (SbS) Approaches: These models learn to iteratively refine solutions, acting as operators within a larger search framework. They tend to be more robust and scalable than pure E2E models.
Publication trends for End-to-End (E2E) and Step-by-Step (SbS) approaches from 2010 to 2021.

As shown in the trend analysis, there has been a significant surge in LBO research since 2017, with E2E approaches currently seeing the highest volume of publications in recent years.

Experimental Study and Key Insights

The authors benchmarked four representative algorithms: the Attention Model (AM) and ASWTAM (E2E), and L2I and Rewriter (SbS). Testing across standard, distribution-shifted, and large-scale datasets revealed several critical insights:

  • Generalization Performance: E2E models perform exceptionally well on data that matches their training distribution (e.g., uniform distribution) but struggle when faced with clustered or non-uniform data (e.g., Gamma distribution).
  • Robustness and Scalability: SbS approaches, particularly L2I, demonstrated superior robustness. By learning improvement heuristics rather than full construction, they generalize better to larger problem sizes than those seen during training.
  • Efficiency Trade-offs: While training LBO models is computationally expensive, their online inference speed is remarkable. For 100-node problems, LBO solvers can provide high-quality solutions in under a second, significantly faster than traditional meta-heuristics like Tabu Search.

Conclusion and Future Directions

LBO algorithms offer a powerful new toolkit for solving complex routing problems. However, challenges remain regarding data dependency and handling high-dimensional constraints (like narrow time windows). Future research is likely to focus on hybrid approaches—learning-assisted heuristics—that combine the robustness of traditional search with the adaptive intelligence of neural networks. Decomposing massive problems into smaller sub-problems for LBO solvers also remains a key area for scaling these methods to real-world industrial levels.

Summary updated

Abstract

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 a lot to the development of this field, these approaches either are limited in problem size or need manual intervening in choosing parameters. To solve these difficulties, many studies have considered the 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 Vehicle Routing Problem}},
  journal = {IEEE CAA J. Autom. Sinica},
  year = {2022},
  url = {https://openreview.net/forum?id=k6IIXZSbOw},
}
Figure