NVIDIAResearch
EARLI

Reinforcement learning for initializing genetic algorithms in vehicle routing

Delivery fleets solve similar routing problems every day, yet solvers start each one from scratch. EARLI (Evolutionary Algorithm with Reinforcement Learning Initialization) trains a reinforcement learning agent on previous problems and uses its solutions to initialize a genetic algorithm. It routes 500 locations within one second, 10x faster than current solvers at the same solution quality.

Ido Greenberg, Piotr Sielski, Hugo Linsenmaier, Rajesh Gandham, Shie Mannor, Alex Fender, Gal Chechik, Eli Meirom
NVIDIA
Communications AI & Computing, 2026
EARLI in under two minutes.

Abstract

Vehicle routing problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in combinatorial optimization. Solving VRP in real-time at large scale has become critical in numerous applications, from growing markets like last-mile delivery to emerging use-cases like interactive logistics planning. Such applications involve solving similar VRP instances repeatedly, yet current state-of-the-art solvers treat each instance on its own without leveraging previous examples. We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions, which are then further optimized by a genetic algorithm. This framework, Evolutionary Algorithm with Reinforcement Learning Initialization (EARLI), consistently outperforms current state-of-the-art solvers under limited time budgets. For example, EARLI handles vehicle routing with 500 locations within one second, 10x faster than current solvers for the same solution quality, enabling real-time and interactive routing at scale. EARLI can generalize to new data, as demonstrated on real e-commerce delivery data of a previously unseen city.

Method

The best routing solvers today are genetic algorithms: they start from a population of random solutions and improve it step by step, from scratch for every new problem. EARLI adds learning from previous problems. A reinforcement learning agent is trained offline on past problem instances. Given a new problem, it builds a batch of complete solutions in under a second, and these solutions become the initial population of the genetic algorithm, which keeps improving them.

EARLI diagram: fast RL inference produces an initial solution pool, which initializes the genetic algorithm's optimization loop of evaluation, selection, mutation and recombination.
The agent's solutions initialize the genetic algorithm's population.

Results

On real e-commerce delivery data from São Paulo with 500 customers, EARLI reaches within one second the solution quality that the solver alone needs about ten seconds to reach.

Cost gap against total runtime on Sao Paulo data with 500 customers: EARLI's curve is well below cuOpt with default, greedy and QBL initialization at short runtimes.
São Paulo, 500 customers: cost gap against total runtime (lower is better). EARLI is the cuOpt solver initialized by the agent; t0 is the agent's own runtime.
Cost gap against total runtime when the agent is trained on Sao Paulo and tested on Rio de Janeiro: EARLI keeps its advantage.
A new city: the agent is trained on São Paulo and tested on Rio de Janeiro.
Cost gap against runtime for cuOpt, HGS, LKH3 and PyVRP with default initialization and with EARLI, on Sao Paulo and on synthetic data with 500 customers.
Four solvers, with their default initialization (dashed) and with EARLI (solid).
Two maps of the same 100-customer problem in Rio de Janeiro after a one-second budget: cuOpt alone with cost 67309, and cuOpt with EARLI with cost 65258.
The same problem in Rio de Janeiro (100 customers) after a one-second budget, without and with EARLI. Arrows are straight for display; costs are road driving times. Map data © OpenStreetMap contributors.

BibTeX

@article{greenberg2026earli,
  title   = {Reinforcement learning for initializing genetic algorithms in vehicle routing},
  author  = {Greenberg, Ido and Sielski, Piotr and Linsenmaier, Hugo and Gandham, Rajesh and Mannor, Shie and Fender, Alex and Chechik, Gal and Meirom, Eli},
  journal = {Communications AI \& Computing},
  volume  = {1},
  number  = {1},
  pages   = {17},
  year    = {2026},
  doi     = {10.1038/s44488-026-00019-7}
}