v3.2 · Hybrid-DDQN · Solomon + Homberger

NAMI Plateau-Aware Deep RL Routing Engine

Combining Deep Reinforcement Learning with Adaptive Large Neighborhood Search to solve Vehicle Routing Problems with Time Windows in milliseconds.

Open Dispatch Portal View Codebase →

Live search · R1 cluster 100 × 100

Epoch 48

Cost 1284.2

Plateau 0%

Search Dynamics

Plateau-Aware Escape Pipeline

01 / DECODER s_0 = Greedy(D)

Constructive Decoder

Initial solution generated via greedy route construction and DDQN-guided insertion heuristic initialization.

def decode(inst):
  routes = init_greedy(inst)
  for c in inst.unassigned:
    insert_tw(routes, c)
  return routes

02 / PLATEAU DETECTOR Patience >= limit

Stagnation Detection

Tracks the search trajectory in real time, detecting local minima plateaus when improvement patience thresholds are violated.

def stagnant(hist, limit):
  p = patience(hist)
  if p >= limit:
    trigger_escape()
    return True
  return False

03 / NEURAL CONTROLLER a_t = argmax Q(s_t, a)

DDQN Guided Repair

Double Deep Q-Network selects optimal combinations of destroy and repair operators to successfully break search basin stagnation.

def select_op(state, q):
  vals = q.predict(state)
  a = argmax_expl(vals)
  return operators[a]

04 / OPTIMUM f_best ~ f_BKS

Optima Convergence

Performs local search optimization and Set Partitioning formulation to recombine elite routes into the final feasible route plan.

def finalize(pool):
  sol = set_partition(pool)
  return verify(sol)

62 Solomon + Homberger instances tested

10 independent seeds (cold-starts)

p < 0.05 in 5 of 6 scale comparisons

1.5x–4x compute overhead vs ALNS-Base

Engine Architecture

Engineered for Hard Constraints

DQN

DDQN Plateau Controller

Prioritized Experience Replay (PER) with beta-annealing
Welford reward normalization for stable training
Dynamically shifts search mode upon stagnation

ALNS

Adaptive Search Engine

8 destroy and 5 insertion operators
Thompson-bandit operator selection policy
Granular local search heuristics

LAC

Learned Acceptance Criterion (LAC)

Neural network solution acceptance classifier
Replaces traditional simulated annealing schedule
Adapts to current trajectory characteristics

MILP

Set-Partitioning MILP Recombinator

Sub-route extraction during search trajectory
Global recombination via mixed-integer equations
Guarantees optimal layout of elite sub-routes

Scientific Validation

Solomon & Homberger Benchmark Results

Instance / Family	Scale	BKS (NV / TD)	NAMI Hybrid (NV / TD)	ALNS Baseline (NV / TD)	Wilcoxon p-value
100-Customer Instances (Solomon Benchmarks)
RC101 (Solomon)	100 Clients	14 / 1622.9	15 / --^†	15 / --^†	--
200-Customer Instances (Gehring-Homberger Benchmarks)
c1_2_1 (Homberger)	200 Clients	20 / 2684.5	20 / 2702.4 -3.42%	20 / 2798.1	--
400-Customer Instances (Gehring-Homberger Benchmarks)
c2_4_1 (Homberger)	400 Clients	10 / 1929.3	12.20 / --^†	13.00 / --^†	p = 0.0078*
r2_4_1 (Homberger)	400 Clients	4 / 2764.0	8.10 / --^†	8.80 / --^†	p = 0.0156*
rc2_4_1 (Homberger)	400 Clients	10 / 2483.4	12.50 / --^†	12.80 / --^†	p = 0.3750
Summary: NAMI Hybrid-DDQN matches BKS vehicle floors at 100/200 scale and achieves statistically significant (p < 0.05) vehicle reductions at 400 scale.

† Travel Distance (TD) comparisons are excluded when vehicle counts (NV) are not matched, as extra vehicle capacity artificially distorts travel distance.

Note: Standalone solver results are generated under strict independent cold-start conditions starting from build_greedy in a cleared directory, without multi-stage warm-starts.

* Statistically significant difference between NAMI Hybrid and ALNS Baseline (Wilcoxon signed-rank test p < 0.05).

CITE

Plateau-Aware Deep RL for Combinatorial Search

Our thesis work analyzes DQN-guided escape operators under severe local stagnation states, outperforming traditional static ALNS variants in 7 of 8 benchmark scenarios.

Developer Quickstart

Run the engine locally

Workspace: VRPTW-Research-Optimization

# Pull and run the pre-built container from DockerHub
docker run -p 8000:8000 -p 5050:80 thundercock/vrptw-nami:latest

# Clone and install dependencies with uv
git clone https://github.com/Thundercok/VRPTW-Research-Optimization.git
cd VRPTW-Research-Optimization
uv venv .venv --python 3.12 && source .venv/bin/activate
uv pip install -r requirements.txt
python main.py

# Run multi-scale Solomon benchmark suite sweep
./run_all_benchmarks.sh --instances RC101-RC108 --epochs 50