routik-solver 0.1.0

# 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`](#the-costmatrix-trait) — 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](https://routik.dev), 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](#open-core).

## Install

```toml
[dependencies]
routik-solver = "0.1"
```

## Quickstart

```rust
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):

```sh
cargo run --example demo
```

## The `CostMatrix` trait

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

```rust
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

1. **Construction** — Clarke-Wright savings, time-window aware: a merge is kept
   only if the route stays feasible.
2. **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.
3. **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:

```sh
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](https://routik.dev). 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](LICENSE).