C++17 · ALNS Metaheuristic · Production API

Vehicle
Routing
Engine

A production-grade solver that handles 2,000+ stops with 15 real-world constraints — time windows, capacity, zones, driver breaks, multi-trip reloads — and returns optimized routes in under 30 seconds.

Explore Architecture View API

Stops Solved

<0s

Solve Time

Constraint Types

Operators

APIs (HTTP + gRPC)

Unit Tests

System Architecture

From HTTP request to optimized routes in one call. Every layer is visible, configurable, and tested.

API Layer

HTTP :8080 · gRPC :50051

Dual protocol — REST/JSON for drop-in Tookan replacement, gRPC/Protobuf for high-performance clients

Tookan Converter

JSON → Problem Model

Visits/fleets → Tasks/Orders/Vehicles. Typo detection, duplicate ID resolution, input validation

Distance Matrix

GraphHopper · Google

Concurrent batched API calls with coordinate deduplication. Traffic-aware via Google departure_time

Constraint Manager

Auto-detected · 15 types

Scans problem data to activate only relevant constraints. Each configurable as hard or soft

Worker Pool

N parallel ALNS solvers

Multi-start with different seeds. Best-of-N selection. Adaptive worker count by problem size

ALNS Solver

Construction → Destroy/Repair → Local Search

Regret insertion, 3 destroy + 2 repair operators with adaptive weights, 4 LS operators, SA acceptance

Post-Processing

Validation · Trip Chaining · Polylines

Chain reload trips, validate feasibility, fetch road polylines, fire webhooks with retry

ALNS Metaheuristic Solver

Adaptive Large Neighborhood Search with Simulated Annealing. Construction → iterative improvement → local search polish.

The solver builds an initial solution using Regret Insertion (k=2). Tasks are inserted one at a time — the task with the highest regret goes first. Regret measures how much worse the second-best option is compared to the best, so tasks that would suffer most from deferral get priority.

STEP 1

Pre-place Locked

Locked tasks go first — pickups before deliveries. These are immovable once placed.

STEP 2

Priority Sort

Remaining tasks sorted by priority. High-priority tasks get a 10⁶ regret bonus to ensure insertion.

STEP 3

Regret Insert

Iteratively insert the task with highest regret into its best feasible position. Constraint-checked every time.

15 Real-World Constraints

Auto-detected from problem data. Every one configurable as hard or soft. The solver only activates what's needed.

Capacity & Load

Capacity

Hard

3D load tracking — weight, volume, pallets. Safe capacity soft threshold before hard limit. Accounts for existing cargo already aboard.

Store Capacity

Hard

Prevents oversized trucks from delivering to stores with limited receiving docks. Checks vehicle weight capacity against per-store limits.

Time

Time Windows

Soft

Per-stop delivery windows. Lateness penalized proportional to delay. Early arrivals wait, late arrivals accumulate penalty.

Max Duration

Hard

Total route duration capped per vehicle. Default 24h. Prevents unreasonably long routes.

Shift

Hard

Route must finish within the driver's shift window. Supports overnight shifts crossing midnight.

Driver Breaks

Hard

Max continuous driving time enforced. Tracks cumulative drive since last qualifying break. Configurable earliest/latest break windows.

Routing

Precedence

Hard

Pickup must come before delivery on the same route. Per-order hard/soft/none. Prevents impossible delivery sequencing.

Backhaul

Hard

Backhaul pickups must come after ALL deliveries on the route. Enforces linehaul-then-backhaul pattern.

Zone Routing

Hard

Geographic zone restrictions. Vehicle zone must match task zone. Empty zone on either side = unconstrained.

Compatibility

Tag Matching

Hard

Every tag on a task must exist in the vehicle's tag set. Case-insensitive. Unmatched tags = violation.

Incompatible Cargo

Hard

Tasks with overlapping incompatible_types from different orders cannot ride the same vehicle. Food vs chemicals, etc.

Locked Tasks

Hard

Pre-placed tasks that cannot be moved by the solver. ALNS destroy operators skip them entirely.

Limits

Max Stops

Hard

Per-vehicle stop limit. Default 999. Useful for drivers with hourly pay or union-regulated stop counts.

Multi-Trip Reload

Hard

Vehicles return to depot, reload, and run another trip. Virtual trip expansion with sequential chaining post-solve.

Performance

Built for production throughput. Adaptive tuning ensures small problems are fast and large problems get the time they need.

Before — jsprit (Java)

~180s

Single-threaded solve for 60–70 routes. Fixed search budget, no way to trade accuracy for latency.

6×

faster

Now — VRP Engine (C++17)

<30s

Parallel multi-start ALNS, cached constraint scores, deduplicated matrix fetches. The time budget is a request parameter — tune it per call to trade solve time for solution quality.

Solve Time vs Problem Size

0–30s

0.5s

200

500

15s

1,000

22s

2,000

30s

stopsSingle-node solve, adaptive worker countseconds

Parallel Multi-Start

N workers with different seeds. Best-of-N selection. Worker count auto-scales by problem size.

Adaptive Parameters

Cooling rate, stagnation limit, and LS frequency all scale with task count. Small problems get fast settings.

Score Caching

Constraint results cached per route content hash. Unchanged routes skip re-evaluation entirely.

Matrix Deduplication

Shared coordinates (depots, warehouses) get one matrix entry. Quadratic savings on repeated locations.

O(1) Task Lookup

Hash-indexed task map replaces linear scan. Eliminates ~57M string comparisons on a 30-task solve.

Concurrent Matrix Fetch

Distance matrix batches fire in parallel via std::async. Google batches of 10, GraphHopper batches of 50.

Production-Ready APIs

Dual protocol. Stateless. Multi-tenant. API keys passed per-request — the engine stores nothing.

HTTP — POST /api/vrp/v1/solveJSON

{
  "visits": [
    {
      "id": "order_1",
      "load": 3,
      "pickup": { "lat": 28.6139, "lng": 77.2090 },
      "dropoff": { "lat": 28.5355, "lng": 77.3910 },
      "time_window_start": 28800,
      "time_window_end": 43200
    }
  ],
  "fleets": [
    {
      "id": "truck_1",
      "capacity": 20,
      "start_location": { "lat": 28.62, "lng": 77.22 },
      "shift_start": 800,
      "shift_end": 1800
    }
  ],
  "matrix_provider": "google",
  "api_key": "YOUR_KEY",
  "time_limit_seconds": 30
}

gRPC — vrp.protoProtobuf

syntax = "proto3";

service VRPSolver {
  rpc Solve(SolveRequest)
    returns (SolveResponse);

  rpc SolveTookan(TookanRequest)
    returns (TookanResponse);

  rpc HealthCheck(Empty)
    returns (HealthStatus);
}

message SolveRequest {
  repeated Task tasks = 1;
  repeated Vehicle vehicles = 2;
  MatrixConfig matrix = 3;
  optional uint32 time_limit_seconds = 4;
}

message SolveResponse {
  repeated Route routes = 1;
  repeated Unassigned unassigned = 2;
  double total_cost = 3;
  uint64 solve_time_ms = 4;
}

Webhook Callbacks

Async delivery to return_url with 3-attempt exponential backoff. Credentials auto-redacted.

Typo Detection

Levenshtein-based "did you mean?" warnings on unrecognized fields. No silent data loss.

Polyline-Ready

Road polylines fetched for every route. Supports Google Directions and GraphHopper.

Built-in Viewer

GET /view serves a MapLibre-based route visualizer. Paste any solve response to see routes on a map.

Under the Hood

LanguageC++17

HTTP Servercpp-httplib

RPCgRPC + Protobuf

JSONnlohmann/json

Loggingspdlog

HTTP Clientlibcurl

Matrix APIsGraphHopper / Google

ContainerDocker (Ubuntu 24.04)

TestingGoogle Test

BuildCMake 3.20+

Engineering Standards

165+ unit and integration tests with Google Test

Constraint fuzz testing for edge cases

Full input validation with Levenshtein-based typo detection

Graceful degradation — unassigned tasks with reasons, never silent failure

Webhook delivery with 3-attempt exponential backoff and credential redaction

Score caching per route content hash for O(1) re-evaluation

Safe capacity (soft threshold before hard limit)

Duplicate ID auto-resolution with warnings

Matrix deduplication — shared coordinates reduce quadratic matrix size

Completed task filtering — already-done work excluded from planning

VehicleRoutingEngine

System Architecture

API Layer

Tookan Converter

Distance Matrix

Constraint Manager

Worker Pool

ALNS Solver

Post-Processing

ALNS Metaheuristic Solver

Pre-place Locked

Priority Sort

Regret Insert

15 Real-World Constraints

Capacity & Load

Capacity

Store Capacity

Time

Time Windows

Max Duration

Shift

Driver Breaks

Routing

Precedence

Backhaul

Zone Routing

Compatibility

Tag Matching

Incompatible Cargo

Locked Tasks

Limits

Max Stops

Multi-Trip Reload

Performance

Solve Time vs Problem Size

Parallel Multi-Start

Adaptive Parameters

Score Caching

Matrix Deduplication

O(1) Task Lookup

Concurrent Matrix Fetch

Production-Ready APIs

Webhook Callbacks

Typo Detection

Polyline-Ready

Built-in Viewer

Under the Hood

Engineering Standards

Vehicle
Routing
Engine