Machine Learning & Deep Learning for the VRP

Machine learning (ML) — and in particular deep learning (DL) — has opened a new research direction for combinatorial optimization problems such as the VRP. Instead of relying on hand-crafted construction and improvement rules, these methods learn a solving policy from data. Given a training set of instances (with or without known good solutions), a model is trained either to build a route directly or to guide a search procedure, with the goal of generalizing to unseen instances. A methodological overview is given in [Bengio, Lodi & Prouvost 2021].

Neural construction (end-to-end)

The first wave of work framed the VRP as a sequence-to-sequence task: the model reads the customer coordinates and outputs a permutation that decodes into routes.

• Pointer networks. [Bello et al. 2017] combined pointer networks with reinforcement learning to tackle the TSP and the VRP, showing that a neural model could produce reasonable solutions without supervision.
• Reinforcement learning for the VRP. [Nazari et al. 2018] replaced the LSTM encoder of pointer networks with simple input embeddings, allowing the model to handle the dynamic elements of the VRP (e.g. changing remaining demand).
• Attention models. [Kool, van Hoof & Welling 2019] proposed a Transformer-style encoder–decoder with attention trained by REINFORCE with a greedy rollout baseline. This "Attention Model" became a reference architecture and closed much of the gap to classical heuristics on small instances.

Learning to improve

A second family keeps a classical search loop but replaces parts of it with learned components, combining the strengths of OR heuristics and ML.

• Neural Large Neighborhood Search. [Hottung & Tierney 2020] learn which parts of a solution to destroy and repair within an LNS framework for the CVRP.
• Learned improvement heuristics. Deep policies are trained to select the next move or operator (2-opt, relocate, swap), e.g. [Peng, Wang & Zhang 2019] using dynamic attention.
• Learning to configure/augment classic solvers. ML is also used to choose among heuristics, tune parameters, or predict good starting solutions that are then polished by an exact or metaheuristic method.

Deep reinforcement learning

Most neural construction and improvement methods are trained with reinforcement learning, where the negative solution cost acts as the reward. Typical algorithms are policy-gradient methods (REINFORCE) and actor–critic schemes. Challenges include the large action space, sparse rewards on hard instances, and generalization from small training graphs to larger or differently distributed ones. These approaches shine when solutions must be produced extremely fast once the model is trained.

Large language models

Large language models (LLMs) are the most recent addition. Their role for the VRP is still exploratory, but several promising uses have appeared:

• Modeling assistants. LLMs translate a natural-language description of a routing problem into a formal model or solver code (e.g. a MILP or a constraint program), lowering the barrier to using optimization tools.
• Heuristic/code generation. Inspired by approaches such as FunSearch, LLMs are used to evolve and refine heuristic code, discovering new construction or improvement rules that are then executed by a classical solver.
• Direct reasoning. Some studies prompt LLMs to solve small routing problems step by step; results are currently limited to toy instances and do not yet rival specialized algorithms.

Strengths and open challenges

• Strengths: very fast inference after training; can exploit patterns in instance distributions; easy to combine with classical search.
• Challenges: generalization to larger/different instances, feasibility guarantees for constrained variants, solution quality versus state-of-the-art metaheuristics, and training cost/data needs.

See the bibliography on ML for VRP for the key references, and the solution techniques overview for classical methods.