routik-solver

A pure-Rust solver for the capacitated vehicle routing problem with time windows (CVRPTW): given a depot, stops (demand + an optional time window) and a fleet (capacity), it builds and optimises the delivery routes.

It is a solver, not a map engine. Travel times and distances come from behind a single trait, CostMatrix — you bring them (a real road-distance matrix, your own estimate) or use the built-in straight-line approximation. The crate does zero I/O: no network, no files, no clock. That keeps it deterministic, embeddable, and fast.

routik-solver is the open core of Routik, a hosted route-optimisation API. This crate — the algorithms and the data model — is Apache-2.0; the product around it (the API, billing, dashboard, the packaged road-matrix integration) is closed. See Open core.

Install

[dependencies]
routik-solver = "0.1"

Quickstart

use routik_solver::{
    solve, Coord, HaversineMatrix, Problem, SolverConfig, Stop, StopId, Vehicle, VehicleId,
};

let problem = Problem {
    depot: Coord::new(48.8566, 2.3522),
    stops: vec![Stop {
        id: StopId(1),
        coord: Coord::new(48.8606, 2.3376),
        demand: 10,
        time_window: None,
        service_time: 0.1,
    }],
    vehicles: vec![Vehicle { id: VehicleId(1), capacity: 50 }],
    depot_window: None,
};

// HaversineMatrix is the built-in straight-line estimate (km, at a given speed).
let matrix = HaversineMatrix::from_problem(&problem, 50.0);
let solution = solve(&problem, &matrix, &SolverConfig::default()).expect("feasible");

assert!(solution.feasible);
for route in &solution.routes {
    println!("vehicle {} -> {:?}", route.vehicle_id.0, route.stop_ids);
}

A larger end-to-end run (15 stops around Paris, with the before/after improvement printed):

cargo run --example demo

The `CostMatrix` trait

The solver only ever asks two things about a pair of points:

pub trait CostMatrix {
    fn distance(&self, a: LocationId, b: LocationId) -> f64;
    fn time(&self, a: LocationId, b: LocationId) -> f64;
}

Everything else is built on that. Three implementations ship with the crate:

HaversineMatrix — great-circle distance plus a configurable speed → time. No external data needed.
EuclideanMatrix — planar distance, unit speed (the Solomon-benchmark convention).
ProvidedMatrix — you supply the full n×n time and distance matrices, e.g. from a road-routing engine (OSRM, Valhalla, a commercial Matrix API). Local search queries distance/time millions of times, so a pre-computed matrix is the right shape: call your engine once, fill a ProvidedMatrix, hand it to the solver.

What it does

Construction — Clarke-Wright savings, time-window aware: a merge is kept only if the route stays feasible.
Local search — relocate, swap, 2-opt, or-opt (intra- and inter-route), with O(1) cost deltas per move and feasibility re-checked on the touched routes.
Metaheuristic — multi-start simulated annealing over those neighbourhoods. The objective (distance, vehicle count, time) is configurable via Objective.

Hard constraints — vehicle capacity and time windows, including the depot window — are never violated: an infeasible move is rejected, not penalised. solve never returns a solution worse than the construction baseline under the configured objective.

Deterministic. The RNG is seeded and injected (SolverConfig::seed); the same input and seed always produce the same solution. No thread_rng, no wall-clock branching.

Benchmarks

The solver is benchmarked against the classic Solomon VRPTW instances (C1 / R1 / RC1), which ship under tests/data/. The bench prints, per instance and size, the solver's distance, the published best-known, and the gap — and gates that gap in CI:

cargo bench --bench solomon                  # print the table
cargo bench --bench solomon -- --check-gap   # CI gate: fail on regression

The gate keeps the gap to best-known under 10% on instances up to 50 customers. Run it yourself rather than trusting a number here — the figures are reproducible from the code. (Solomon uses Euclidean distance with time == distance, so the bench uses EuclideanMatrix.)

Scope

This crate solves CVRPTW: one depot, capacity, time windows, a fleet described by capacity. It is intentionally small and dependency-light (thiserror, rand). Pickup-and-delivery, multi-depot, driver shifts, or a lower-bound gap estimate are not here — the hosted product layers road matrices and operational constraints on top, but the routing core is this crate.

Open core

routik-solver is the only open part of Routik. The boundary is deliberate and enforced in the Cargo manifests, not just documented: this crate is a pure, zero-I/O library under Apache-2.0; the API, billing, dashboard, infrastructure, and the packaged road-matrix integration are proprietary. The trait is open so you can plug any matrix in; the hosted road-distance matrix is part of the product.

License

Apache-2.0 — see LICENSE.

routik-solver 0.1.0