Neural CVRP

This project represents my research internship at HEC Montréal: a systematic evaluation of when machine learning helps the Capacitated Vehicle Routing Problem, culminating in a detailed write-up of structural negative results. The work is a systematic map of why machine learning fails to move the needle on CVRP quality at bounded sizes, backed by a high-performance classical parallel solver in Rust.

Study A: Learned CVRP (NCO)

I ran a broad sweep of neural combinatorial optimization (NCO) models, including attention encoder-decoders (POMO, LEHD), GFlowNets (with SubTB RL), D3PM diffusion, normalizing flows, and AlphaZero-style searches. The core finding is that constructive RL needs a strong prior; at n = 50, they all underperform the warm-started LEHD/POMO baseline.

One of the key ideas I evaluated was using a differentiable-split decomposition: trying to train a network to output a giant TSP tour and letting a softened Prins Split layer handle the vehicle capacity cuts. The goal was to backpropagate through the split recurrence (using a -τ · logsumexp smoothing) to optimize the giant-tour ordering. However, we found this is structurally blocked:

• The smoothed Split is differentiable in the cut placements (j), which the exact dynamic program already places optimally.
• The policy controls the giant tour ordering (σ), but the ordering enters the cost function only through a discrete gather (tour.long()), blocking the gradient (∂cost/∂σ).
• Continuous permutation relaxations (like Sinkhorn or Gumbel Straight-Through) that unblock it collapse to degenerate uniform permutations during training.

Study B: ML-Augmented Search

Study B asked the reverse question: starting from a SOTA classical iterated local search (ILS) engine, can we inject machine-learning steering (like GNN route rebuild-scorers, demand-aware co-assignments, or neural column pricing) into the hot loop?

Inside a SOTA engine, the learnable signal is too weak. Near-optimal CVRP solutions are massively degenerate: two equally good solutions share only about 41% of their same-route pairs, so any consensus signal is noise. The residual gap behaves as an “assignment lottery” over degenerate local minima. A neural network paying per-call GPU latency on every local search step is simply the wrong tool.

The Classical Rust Solver

Because the neural variants plateaued, the primary artifact that shipped was a high-performance classical ILS engine built in Rust. It uses LKH for initial tours, Prins split for vehicle capacity partitioning, granular local search over nearest neighbors, SISR ruin-and-recreate, SREX crossover, and simulated annealing.

The main performance lever is a best-of-K ruin oracle: at each perturbation step, it runs K destructions in parallel across K CPU cores, re-optimizes, and keeps the lowest post-search cost.

On the full 99-instance Set-X benchmark, gap to best-known (lower is better):

• @10 s (multi-core): 0.664% against PyVRP’s 1.367% (single-core engine: 0.755%)
• @60 s (multi-core): 0.362% against PyVRP’s 0.511% (single-core engine: 0.497%)
• @120 s (multi-core): 0.302% against PyVRP’s 0.433% (single-core engine: 0.429%)

It beats PyVRP (the HGS implementation) at every budget. Single-threaded it’s tighter: FILO is the one to catch at a 10-second budget, and AILS-II is the converged state of the art, which I didn’t beat.

MHStudy

Alongside this, I’m working through a slower, stricter project: reproducing the classical CVRP canon from scratch. I’m implementing thirteen metaheuristics (Clarke-Wright in 1964 through Prins’ memetic GA in 2004) from the original papers alone in zero-dependency Rust. I run them against a separate Python validator that independently checks feasibility and cost to make sure there’s no code bias.

The point is to measure the algorithms with everything else held constant (same language, data structures, and tuning effort) so a win is actually the algorithm and not just a better implementation. The first one is done and validated: Clarke-Wright, landing a 6.62% mean gap to best-known across 119 benchmark instances.

Code is kept private (research IP). Happy to talk through the approach.