VRP optimization kernel that runs anywhere

Every VRP solver makes you choose

The VRP solver landscape forces a trade-off. You get solution quality (HGS, LKH-3) but can't deploy it. You get deployment flexibility (VROOM) but sacrifice constraint depth. You get constraint richness (PTV, Ortec) but pay six figures and get locked into a JRE monolith. You get a familiar API (OR-Tools) but the solver chokes beyond 500 requests and ships a 50MB binary.

Surge refuses the trade-off.

An optimization kernel for vehicle routing

Surge solves the family of Vehicle Routing Problems: VRPTW, PDPTW, DARP, and rich VRP with arbitrary combinations of constraints. It uses an Adaptive Large Neighborhood Search (ALNS) metaheuristic built on the Arbor framework, with simulated annealing acceptance, population-based parallel search, and HGS-style infeasible-space exploration.

  Problem JSON                                         Solution JSON
       │                                                     ▲
       ▼                                                     │
  ┌─────────┐    ┌──────────┐    ┌──────────┐    ┌──────────────┐
  │ sg_api  │───▶│ sg_solve │───▶│ Arbor    │───▶│ sg_solution  │
  │ (parse) │    │ (phases) │    │ (ALNS)   │    │ (extract)    │
  └─────────┘    └──────────┘    └──────────┘    └──────────────┘
                      │               │
                      ▼               ▼
                ┌──────────┐   ┌───────────┐
                │ Construct│   │ Destroy   │  random, worst,
                │ (greedy  │   │ + Repair  │  Shaw, route,
                │  insert) │   │ operators │  regret-k, greedy
                └──────────┘   └───────────┘
                                     │
                      ┌──────────────┼──────────────┐
                      ▼              ▼              ▼
                ┌──────────┐  ┌──────────┐  ┌──────────┐
                │Feasibility│  │   Cost   │  │  Local   │
                │  (timing, │  │ (lexicog │  │  Search  │
                │  capacity,│  │  multi-  │  │ (2-opt*, │
                │  pairing) │  │  obj)    │  │  or-opt, │
                └──────────┘  └──────────┘  │  cross)  │
                                            └──────────┘

Problem classes

• VRPTW — Capacitated VRP with time windows (Solomon benchmarks)
• PDPTW — Pickup and delivery with time windows (Li & Lim benchmarks)
• DARP — Dial-a-ride with max ride time constraints
• Rich VRP — Arbitrary constraint combinations: compartments, breaks, setup times, multi-trip, stacking, precedence, locking

Solve phases

• Construction — Greedy insertion builds initial feasible solution
• Phase 1 (Vehicle minimization) — ALNS with infeasible-space exploration, targets unassigned count then vehicle count
• Phase 1.5 (Crunch) — Aggressive vehicle removal with extended repair attempts
• Phase 2 (Distance polish) — ALNS focusing on total distance with fixed vehicle count
• Postprocess — Intra-route local search (2-opt*, or-opt, cross-exchange)

Competitive with best known solutions

All results: population mode (3 generations, auto threads), scale-aware iteration caps, deterministic seed (42). Scale-tuned ALNS (S22), instance-adaptive construction (S24), generation SA reheat (S25). Compared against published Best Known Solutions.

Solomon VRPTW (56 instances, 100 customers each)

Li & Lim PDPTW (56 instances, 100 requests each)

Gehring-Homberger VRPTW (60 instances, 200 customers each)

Population mode, 60s time limit, MEDIUM_TUNE (S22), deterministic seed 42.

Gehring-Homberger VRPTW (60 instances, 400 customers each)

Population mode, 120s time limit, LARGE_TUNE (S22) + SA reheat 2.0× (S25), deterministic seed 42.

Scaling Summary

Performance

25+ constraint types, all composable

Every constraint is independently testable and freely composable. Adding a new constraint to ALNS requires one feasibility check and one cost component — not rewriting the solver. Compare with HGS, where each new constraint touches 5+ subsystems (Split, crossover, move evaluation, penalties, route updates).

Re-optimization & Warm Start

• Warm start — provide initial solution, solver improves from there
• Request locking (FROZEN) — request stays on designated vehicle, position preserved
• Request locking (COMMITTED) — request must be served, but vehicle/position flexible
• Plan/ETA validation — validate fixed routes, compute ETAs, report constraint violations

Kernel-level comparison

Surge is a VRP optimization kernel, not a logistics platform. Comparing against platforms (PTV, HERE) on platform features (real-time traffic, driver apps) is a category error — those are application-layer concerns handled by other OTTO modules. This compares solvers as optimization kernels.

Grade summary

Feature-by-feature constraint comparison

Y = Production quality P = Partial / limited N = Not supported ? = Opaque / undocumented

Time & Scheduling

Capacity & Loading

Vehicle, PD, Breaks, Sequencing

Deployment & Integration

Domain-native, not framework ceremony

~80 C functions, all following the same pattern: sg_<noun>_set_<property>(ctx, id, value). No inheritance hierarchies, no builder patterns, no callback dimensions. You think in vehicles, requests, tasks, and depots — not solver internals.

// Add a constrained vehicle
uint32_t v = sg_add_vehicle(ctx);
sg_vehicle_set_depots(ctx, v, depot, depot);
sg_vehicle_set_max_duration(ctx, v, 28800);

# Dimension + callback + slack ceremony
routing.AddDimension(
    transit_cb, 30, 28800, True, 'Time')
time_dim = routing.GetDimensionOrDie('Time')
time_dim.CumulVar(
    manager.NodeToIndex(loc)
).SetRange(tw_start, tw_end)

JSON API

The same solver is accessible via a JSON API — POST a problem, get a solution. The transport-agnostic sg_api_handle() function works identically over HTTP, WASM, Unix sockets, or direct C calls.

$ curl -X POST http://localhost:8085/api/v1/solve \
    -H "Content-Type: application/json" \
    -d '{
    "vehicles": [{"id": 0, "depot_start": 0, "depot_end": 0,
                  "capacity": [20], "shift": [0, 1000]}],
    "depots": [{"id": 0, "x": 40.0, "y": 50.0, "tw": [0, 1000]}],
    "tasks": [
        {"id": 0, "x": 45.0, "y": 55.0, "tw": [0, 500], "service": 10, "demand": [5]},
        {"id": 1, "x": 42.0, "y": 58.0, "tw": [0, 500], "service": 10, "demand": [3]}
    ],
    "requests": [{"id": 0, "delivery_task": 0}, {"id": 1, "delivery_task": 1}],
    "config": {"max_iterations": 1000}
  }'

Integration paths

Why ALNS, not HGS

HGS (Hybrid Genetic Search by Vidal) is state-of-the-art on clean CVRP benchmarks. But its architecture makes three commitments that conflict with rich VRP:

• Giant tour + Split decoder — With PD precedence, Split becomes NP-hard. PyVRP explicitly does not support PDPTW for this reason.
• O(1) concatenation scheme — Breaks for setup times (depends on adjacent node), max ride time (non-decomposable), commodity conflicts (set membership), and breaks (state machine). Falls back to O(n) per move, eliminating HGS's speed advantage.
• Crossover destroys structure — OX/SREX permute individual nodes without awareness of PD pairs, commodity conflicts, or exclusion groups. Repair required after nearly every crossover.

Adding a new constraint to ALNS touches 1–2 files (feasibility check + cost component). Adding a new constraint to HGS touches 5+ subsystems (Split, crossover, move evaluation, penalties, route updates). For 25+ simultaneous constraint types, ALNS is the right architecture.

Memory management

Zero malloc/free in the hot loop. Arena allocators for per-solution memory, optimized single-memcpy solution copy, pre-allocated scratch buffers for feasibility and local search. 21% speedup on Solomon from arenas alone.

Codebase

27K lines of solver library code (Surge + Arbor). A competent C developer can read the entire solver in a day. No metaprogramming, no templates, no macros beyond basics. Deterministic: same seed = same output. ASan/UBSan clean. Per-operator telemetry built in.

Three ways to try Surge

1. Browser (zero install)

The API documentation page includes a live WASM demo. Click "Solve Problem" to run the actual solver in your browser.

2. Build from source

# Clone and build
git clone https://github.com/ottofleet/otto.git
cd otto && make surge

# Run tests (454 tests)
make test-surge

# Run Solomon benchmarks
make -C surge bench

3. REST API server

# Build and start the API server
make -C surge/api
./surge/api/surge-solver

# Solve a problem
curl -X POST http://localhost:8085/api/v1/solve \
  -H "Content-Type: application/json" \
  -d @problem.json

4. Python bindings

# Build shared library
make -C surge shared-lib

# Use from Python
from surge import Surge

solver = Surge()
solver.add_vehicle(depot=0, capacity=[20], shift=(0, 1000))
solver.add_task(x=45.0, y=55.0, tw=(0, 500), demand=[5])
result = solver.solve(max_iterations=1000)

5. Node.js (WASM)

import { loadSurge } from '@artalis/surge';

const surge = await loadSurge();
const result = surge.solve({
    vehicles: [{ id: 0, depot_start: 0, depot_end: 0,
                 capacity: [20], shift: [0, 1000] }],
    depots: [{ id: 0, x: 40.0, y: 50.0, tw: [0, 1000] }],
    tasks: [{ id: 0, x: 45.0, y: 55.0, tw: [0, 500],
              service: 10, demand: [5] }],
    requests: [{ id: 0, delivery_task: 0 }],
    config: { max_iterations: 1000 }
});

Common questions

How does Surge compare to OR-Tools for large instances?

OR-Tools uses CP-SAT, which degrades badly beyond ~500 requests — memory footprint explodes with distance matrix size. Surge's ALNS architecture scales by construction: destroy/repair operates on a fixed-size solution representation regardless of instance size. On Gehring-Homberger 200-customer instances, Surge matches BKS vehicle count 90% of the time with +7.9% avg distance gap. 400+ instances need per-iteration speedups (distance matrix caching, global time limits) to be practical.

Why C and not Rust?

Universal ABI. C is the only language callable from literally everything: Python (ctypes), Node (ffi-napi), Go (cgo), Rust (bindgen), Java (Panama), Swift, WebAssembly. Rust would provide memory safety at compile time, but the C ABI means zero FFI friction. Arena allocation mitigates the most dangerous class of memory bugs while delivering best-in-class performance.

Is WASM performance competitive with native?

WASM runs at 50–80% of native speed depending on the workload. For a 100-customer problem, that's the difference between 9 seconds and 14 seconds — both acceptable for batch optimization. The deployment advantage (run in any browser, no install) outweighs the speed penalty for most use cases.

Can I use this for real-time dispatch?

For re-optimization of an existing plan (insert 1–5 new requests), yes. Use request locking (FROZEN) to pin committed deliveries, then solve with a low iteration budget (100–500 iterations, sub-second). For full fleet re-planning from scratch with 1000+ requests, budget 30–120 seconds.

What's missing vs. commercial solvers?

At the solver kernel level: energy/EV cost model (experimental in OR-Tools, niche for trucking). Everything else — compartments, precedence, locking, breaks, multi-trip, setup times — is implemented. At the platform level: real-time traffic, driver apps, dashboards, reporting. Those are application-layer concerns handled by other OTTO modules or your own infrastructure.

What license? Can I embed this in a commercial product?

AGPLv3 with a Trucking Exception. If you're a trucking fleet using Surge for your own operations, the exception applies and you don't need to open-source your application code. If you're embedding Surge in a commercial SaaS product for resale, AGPL requires source disclosure — or contact us for a commercial license.