volare

Vehicle routing solver in Rust, with no dependencies.

Describe a fleet, a set of stops and the limits each vehicle has to respect. volare builds a first solution with cheapest insertion, then improves it with local search. Readers for CVRPLIB and Solomon VRPTW files and a benchmark runner are included.

Early days. CVRP, hard time windows, optional nodes, per-vehicle node exclusion and in-route ordering work today. No soft windows, pickup and delivery or multi depot yet.

Install

[dependencies]
volare = "0.2.2"

Requires Rust 1.85 or later. To build from source:

git clone https://github.com/thiagomoretto/volare.git
cd volare
cargo build --release

Usage

use volare::{Construct, Improve, ModelBuilder, NodeId, solve};

let coords: [(f64, f64); 5] = [(0.0, 0.0), (10.0, 0.0), (20.0, 0.0), (30.0, 0.0), (40.0, 0.0)];

let mut b = ModelBuilder::new(coords.len());

let cost = b.cost_class(move |from, to| {
    let (p, q) = (coords[from.index()], coords[to.index()]);
    (p.0 - q.0).hypot(p.1 - q.1).round() as i64
});

// Two vehicles, both starting and ending at node 0. Add vehicles before
// dimensions: cumul limits are indexed by vehicle.
b.vehicle(NodeId(0), NodeId(0), cost);
b.vehicle(NodeId(0), NodeId(0), cost);

// One unit of demand per stop, three units of room per vehicle.
b.dimension("demand", |_from, to| if to == NodeId(0) { 0 } else { 1 }, vec![3, 3]);

let model = b.build();
let sol = solve(&model, Construct::CheapestInsertion, Improve::Gls { iters: 200 });

println!("{:?} costs {}", sol.routes, sol.cost);

Arc costs are closures, so distances can come from coordinates, a precomputed matrix or a live routing service. The solver itself never sees a coordinate.

solve_with takes the same arguments plus a callback, if you want to watch the search progress. search_log() is a ready made one that prints to stderr. The callback can also stop the search: return ControlFlow::Break(()) and the solver hands back the best solution so far. The early_stop example stops once the search stalls.

Full API docs with cargo doc --open.

Constraints

A dimension is a quantity that accumulates along a route: load, time, distance. max_cumul bounds it per vehicle. cumul_bounds bounds it per node, which is what makes a time window.

// Time: travel on the arc plus service at the node we leave. No vehicle
// limit, so the windows do all the work.
b.dimension("time", move |from, to| travel(from, to) + service(from), vec![i64::MAX; 2]);

// Hard window at node 3. Arriving after 90 is infeasible; arriving before
// 30 makes the vehicle wait until 30.
b.cumul_bounds("time", NodeId(3), 30, 90);

// Vehicle 0 may not serve node 4: no permit, no cold chain, whatever the
// reason. Construction panics if a node ends up forbidden on every vehicle.
b.forbid(VehicleId(0), NodeId(4));

// Node 5 may be left unserved, for 500 added to the total cost. Nodes you
// do not declare stay mandatory.
b.allow_drop(NodeId(5), 500);

After the solve, sol.unserved(&model) lists the dropped nodes. Their penalties are already inside sol.cost.

The two upper bounds are not the same test. cumul_bounds checks the arrival before any wait; max_cumul checks it after. So waiting counts against the vehicle's endurance but never against the node's window, and neither bound expresses the other.

What is in the box

Construction	cheapest insertion
Improvement	hill climb, guided local search on top of it, or ruin and recreate (SISR)
Operators	relocate, swap, 2-opt, 2-opt*
Constraints	per-vehicle cumul limits, hard windows per node, per-vehicle node exclusion, optional nodes with a drop penalty
Input	CVRPLIB EUC_2D files, Solomon VRPTW files with the DIMACS metric

Benchmarks

Mean gap against the best known cost across the 43 CVRPLIB X instances with n up to 300, measured at commit b0995dc (ruin and recreate at the commit that added it):

Strategy	Mean gap
cheapest insertion	25.2%
hill climb	9.5%
guided local search, 300 rounds	5.5%
ruin and recreate, 50,000 rounds	1.2%

cargo run --release --bin bench -- X-n              # hill climb, about 2 seconds
cargo run --release --bin bench -- X-n --gls=300    # about 3 minutes
cargo run --release --bin bench -- X-n --sisr=50000 # about 80 seconds

Drop the X-n filter and the run also takes in the five Belgium XL instances, 3k to 11k nodes each, which is a much longer wait.

baseline.csv pins the hill climb gap for each X instance, and the runner exits non-zero if any instance regresses by more than two points.

--scenario swaps the plain CVRP for a constrained variant on the same instances and reports the cost delta against the unconstrained solve:

cargo run --release --bin bench -- X-n --scenario=forbid  # per-vehicle exclusions
cargo run --release --bin bench -- X-n --scenario=drop    # optional nodes
cargo run --release --bin bench -- X-n --scenario=tw      # hard time windows

Development

cargo test --release
cargo clippy --all-targets -- -D warnings
cargo fmt --check

tests/oracle.rs and tests/solomon_oracle.rs re-evaluate every published best known solution, CVRP and VRPTW, and check each reproduces the published cost. That catches the rounding and indexing mistakes that would otherwise surface as a gap percentage which looks plausible and means nothing. For the VRPTW set it also pins the window semantics against someone else's answers.

License

Apache 2.0, see LICENSE.