Neural Combinatorial Optimization

Overview

This project explores neural combinatorial optimization for the Capacitated Vehicle Routing Problem (CVRP). The goal was to learn policies that could improve or perturb routing solutions generated by LKH, a strong Lin-Kernighan-Helsgaun heuristic solver, and then evaluate whether those learned policies could help during online search.

I treated LKH as both a teacher and a solver. First, I collected LKH improvement trajectories and trained a neural network to imitate before-and-after tour improvements. Then I integrated the trained model back into the LKH loop to test whether learned proposals could improve real solver behavior.

View the code on GitHub

---

Pipeline

The project followed a full data-to-evaluation pipeline:

• Generate CVRP instances using RL4CO tooling
• Run LKH to collect tour improvement trajectories
• Parse LKH tracking files into before/after pairs
• Convert tours into tensors, adjacency matrices, and connection-change labels
• Train a hierarchical CVRP policy to imitate LKH improvements
• Evaluate offline on held-out samples and online inside the LKH search loop

Framework used for routing policy training and environment interaction

---

Model

The imitation model was built around a hierarchical CVRP policy with attention-based node embeddings, route memory, and decoder logic for constructing improved tours. The training objective combined action prediction with supervision on which node connections changed between the source tour and the LKH-improved target tour.

Key implementation pieces included:

• TSPLIB/CVRP parsing and TensorDict conversion
• LKH before/after trajectory extraction
• A CVRP N2S encoder and advanced decoder
• Connection-change labels for local-search-style supervision
• Greedy and sampling decode modes for validation and experimentation

Encoder-decoder structure for mapping CVRP instances and current solutions into actions

---

Online Validation

After offline training, I connected the learned policy back to LKH through a neural-network callback path. The online validation loop compared pure LKH against LKH augmented with neural proposals.

Early experiments showed mixed but useful results. On one two-model setup, the neural-assisted solver beat the baseline on 3 of 8 inspected instances, while broader validation showed the model still lost more often than it won. That made the project useful as a research probe: the model learned recognizable LKH behavior, but matching or beating a mature heuristic consistently was harder than simply imitating its final move.

Comparison of baseline LKH against LKH with a two-model neural policy

Cost-gap and fallback-rate distributions from online validation

---

Learned Perturbations

The later direction shifted from asking the network to reconstruct entire improved tours toward learning controlled perturbations. I built an LKH-backed reinforcement learning environment where:

• LKH warms up to a current best tour
• The neural policy proposes a perturbation
• LKH repairs and improves from that proposal
• The reward is the cost improvement after LKH finishes

I also experimented with Neural Deconstruction Search: instead of outputting a full tour, the model chooses a small set of customers to remove, a greedy repair step reinserts them, and LKH searches from that neighborhood. This reduced the action complexity and made the learned perturbation more local.

Fallback behavior across online LKH trials

Reward and improvement curves from the learned perturbation experiments

---

Takeaways

This project gave me a much deeper understanding of how difficult it is to augment classical combinatorial solvers with neural policies. The most important lesson was that generating an entire CVRP tour is often too unconstrained; the more promising direction is to learn smaller perturbations and let a strong solver handle feasibility, repair, and local search.

Technologies used:

• Python, PyTorch, TensorDict
• RL4CO and TorchRL-style routing environments
• LKH 3.0.13 with neural callback integration
• CVRP data processing, imitation learning, and reinforcement learning