Scaling Vehicle Routing via Learning and Decomposition

49 concepts49 papers1 proposal

When we plan a route for a single vehicle visiting a handful of destinations, the problem is straightforward. But as logistics networks scale to thousands of customers, multiple fleets, and real-world constraints like tight delivery windows or battery ranges, we run headfirst into a mathematical wall.

Vehicle Routing Problems (VRPs) and their variants are generalizations of the Traveling Salesman Problem, making them fundamentally NP-hard (Armstrong-Crews et al.). This means that finding an absolute optimal solution requires a search space that grows factorially or exponentially with the number of locations (Beltrame et al.; Li).

To make matters worse, modern logistics demands the integration of highly complex, non-linear constraints. Managing electric vehicle charging schedules (Nathwani et al.), allowing split loads across multiple trucks (Haddad et al.), coordinating multi-fleet airport ground handling (Zhou et al.), or optimizing city-scale ride-pooling (Shah et al.; Zhu et al.) causes traditional exact mathematical solvers to hit a technical ceiling (Kizilay et al.).

To bypass this combinatorial explosion, a powerful research direction has emerged: combining structural decomposition with machine learning to scale routing optimization to massive, real-world dimensions.


Decomposition: Shrinking the Search Space

The core intuition behind decomposition is simple: if a monolithic problem of size $N$ is too computationally expensive to solve because of its $O(N!)$ or $O(e^N)$ complexity, we can break it into smaller, independent subproblems. Solving ten problems of size 10 is orders of magnitude faster than solving one problem of size 100.

Researchers achieve this reduction through several distinct partitioning strategies:

  • Spatial and Customer-Based Partitioning: Instead of optimizing entire vehicle routes globally, algorithms can isolate clusters of customers. Bent et al. demonstrated this with a Customer-based Adaptive Decomposition (CAD) scheme, which breaks massive routing problems into localized subproblems, successfully avoiding the performance plateaus that plague standard global search heuristics.
  • Hierarchical Graph Partitioning: When dividing a massive graph into sub-graphs, errors can compound at the boundaries. To mitigate this, Pan et al. introduced a hierarchical framework (HLGP) that blends global and local partitioning policies, allowing neural solvers to successfully scale up to 10,000 nodes without losing structural robustness.
  • Fleet-Level Aggregation: Sometimes the explosion comes from tracking too many individual assets. In large-scale electric vehicle fleet planning, tracking every single battery charge state creates an intractable number of integer variables. Geng et al. bypassed this by grouping vehicles by type and managing energy constraints at the aggregate fleet level rather than the individual vehicle level, yielding a 2,000x computational speedup.

Amortizing Search with Learning-Based Solvers

Traditional Operations Research (OR) algorithms, such as metaheuristics or branch-and-bound solvers, start their search completely from scratch for every new problem instance. They spend massive amounts of computation evaluating millions of bad permutations.

Machine learning models, by contrast, can learn the underlying geometric and topological patterns of routing from historical data or simulation. Once trained, the model can generate high-quality routing decisions in a single forward pass, effectively amortizing the computational cost.

For instance, by framing decision-making as a sequence decoding task, foundation models like DigitalBrain (Wen et al.) can generalize across hundreds of different combinatorial optimization tasks. Similarly, Kong et al. leveraged Graph Neural Networks (GNNs) to natively process unordered customer locations and complex constraints for truck-drone delivery coordination. Rather than hand-crafting explicit mathematical rules for every edge case—which becomes incredibly complex when dealing with real-world variables like inventory limits—models can learn to discover high-quality routes directly by mimicking historical solutions (Canoy et al.).


The Hybrid Frontier: Learning to Improve

Pure machine learning models are incredibly fast, but they have a weakness: they are often imprecise and struggle to strictly guarantee hard constraints. Conversely, classical OR solvers are perfectly precise but prohibitively slow on large scales.

The modern frontier of routing optimization combines these two paradigms into a hybrid synergy. Machine learning is used to make macro-level decisions (such as partitioning the graph or initializing a solution), while classical algorithms handle the micro-level execution (such as local path refinement and constraint verification).

+-----------------------------------------------------------------------+
|                           MASSIVE VRP GRAPH                           |
+-----------------------------------------------------------------------+
                                    |
                                    v
+-----------------------------------------------------------------------+
|                   MACRO-LEVEL: NEURAL ALLOCATION                      |
|  - Graph Neural Networks / Deep Reinforcement Learning                |
|  - Clusters nodes, allocates tasks, or generates initial routes       |
+-----------------------------------------------------------------------+
                                    |
                                    v
+-----------------------------------------------------------------------+
|                   MICRO-LEVEL: CLASSICAL SOLVERS                      |
|  - Dynamic Programming / Exact Solvers / Local Search Heuristics      |
|  - Solves isolated subproblems and strictly enforces constraints      |
+-----------------------------------------------------------------------+
                                    |
                                    v
+-----------------------------------------------------------------------+
|                        OPTIMAL GLOBAL ROUTE                           |
+-----------------------------------------------------------------------+

This hybrid approach manifests in several powerful architectures:

  • Learn to Improve (L2I): Lu et al. pioneered an iterative framework where deep learning models act as a selection mechanism, learning how to guide and improve solutions generated by classical operations research algorithms.
  • Bilevel Neural-Classical Integration: For the Min-Max Multiple Traveling Salesman Problem, Guo et al. introduced the iMTSP framework. It uses a neural "allocation network" to assign specific cities to specific vehicles at the macro level, and then hands those isolated allocations off to a classic, highly optimized single-vehicle TSP solver to find the exact sequence.
  • Neural Initialization for Metaheuristics: Instead of starting genetic algorithms or tabu searches from random points, learning models can seed them with near-optimal starting configurations. Wu et al. paired a Transformer-based Deep Reinforcement Learning model with the NSGA-II genetic algorithm, using the neural network to generate high-quality initial solutions that dramatically accelerated the genetic algorithm's convergence time.

By shifting the burden of global spatial reasoning onto neural networks and leaving the precise constraint satisfaction to classical decoders (Kwon et al.), these hybrid methods allow logistics systems to scale to city-wide operations without succumbing to combinatorial explosion.

Key Foundational Work

Helicopter Routing for Maintaining Remote Sites in Alaska using a Genetic Algorithm (2005) — contributed 2 concept elements to this direction.
Randomized Adaptive Spatial Decoupling for Large-Scale Vehicle Routing with Time Windows (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_explosion_in_routing_785a62cc,
  title = {combinatorial explosion in routing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-explosion-in-routing/rdr_785a62ccc79a484eaa3febd190c720e0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_combinatorial_explosion_in_routing_785a62cc_v1,
  title = {combinatorial explosion in routing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-explosion-in-routing/rdr_785a62ccc79a484eaa3febd190c720e0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake