# Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms

arXiv: https://arxiv.org/abs/2504.06126 · HTML: https://mlsanity.com/paper/2504.06126/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 64 references that are in the map.
- First posted on arXiv 8 Apr 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 25 of 25)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer](https://mlsanity.com/paper/2110.02544/) (2021)
- [Symbolic Regression via Neural-Guided Genetic Programming Population Seeding](https://mlsanity.com/paper/2111.00053/) (2021)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [Discovering Evolution Strategies via Meta-Black-Box Optimization](https://mlsanity.com/paper/2211.11260/) (2022)
- [Equivariant Deep Weight Space Alignment](https://mlsanity.com/paper/2310.13397/) (2023)
- [Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization](https://mlsanity.com/paper/2304.03995/) (2023)
- [Blind Geometric Distortion Correction on Images Through Deep Learning](https://mlsanity.com/paper/1909.03459/) (2019)
- [Bridging Evolutionary Algorithms and Reinforcement Learning: A Comprehensive Survey on Hybrid Algorithms](https://mlsanity.com/paper/2401.11963/) (2024)
- [Reinforcement Learning Driven Heuristic Optimization](https://mlsanity.com/paper/1906.06639/) (2019)
- [Hybridization of evolutionary algorithm and deep reinforcement learning for multi-objective orienteering optimization](https://mlsanity.com/paper/2206.10464/) (2022)
- [A Comprehensive Overview of Fish-Eye Camera Distortion Correction Methods](https://mlsanity.com/paper/2401.00442/) (2023)

## Built on by (most cited first, 2 of 2)

- [Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization](https://mlsanity.com/paper/2506.09404/) (2025)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)

## Abstract (arXiv)

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. In many applications, one has to repeatedly solve VRP instances drawn from the same distribution, 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 across various 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 we demonstrate on real e-commerce delivery data of a previously unseen city. By combining reinforcement learning and genetic algorithms, our hybrid framework takes a step forward to closer interdisciplinary collaboration between AI and optimization communities towards real-time optimization in diverse domains.