u-routing

Vehicle routing optimization library providing building-block algorithms for TSP, CVRP, and VRPTW variants.

Features

• Models — Customer, Vehicle, Route, Solution, TimeWindow, RoutingProblem trait
• Distance — Dense distance/travel-time matrix with nearest-neighbor lookup
• Evaluation — Route feasibility checking (capacity, time windows, max distance/duration)
• Constructive heuristics — Nearest Neighbor (O(n²)), Clarke-Wright Savings (O(n² log n))
• Local search — Intra-route 2-opt (Croes 1958), inter-route Relocate (Or 1976)
• Genetic algorithm — Giant tour + Prins (2004) split DP, OX crossover, 2-opt refinement
• ALNS — Random/Worst/Shaw removal + Greedy/Regret-k insertion (Ropke & Pisinger 2006)

Quick Start

use u_routing::models::{Customer, Vehicle};
use u_routing::distance::DistanceMatrix;
use u_routing::constructive::nearest_neighbor;
use u_routing::local_search::{two_opt_improve, relocate_improve};

let customers = vec![
    Customer::depot(0.0, 0.0),
    Customer::new(1, 1.0, 0.0, 10, 0.0),
    Customer::new(2, 2.0, 0.0, 10, 0.0),
    Customer::new(3, 3.0, 0.0, 10, 0.0),
];
let dm = DistanceMatrix::from_customers(&customers);
let vehicles = vec![Vehicle::new(0, 30)];

// Constructive → Local search pipeline
let initial = nearest_neighbor(&customers, &dm, &vehicles);
let improved = relocate_improve(&initial, &customers, &dm, &vehicles[0]);
println!("Distance: {}", improved.total_distance());

GA Solver

use u_routing::models::Customer;
use u_routing::distance::DistanceMatrix;
use u_routing::ga::RoutingGaProblem;
use u_metaheur::ga::{GaConfig, GaRunner};

let customers = vec![
    Customer::depot(0.0, 0.0),
    Customer::new(1, 1.0, 0.0, 10, 0.0),
    Customer::new(2, 2.0, 0.0, 10, 0.0),
    Customer::new(3, 3.0, 0.0, 10, 0.0),
];
let dm = DistanceMatrix::from_customers(&customers);

let problem = RoutingGaProblem::new(customers, dm, 30);
let config = GaConfig::default()
    .with_population_size(50)
    .with_max_generations(200);

let result = GaRunner::run(&problem, &config);
println!("Best distance: {}", result.best_fitness);

ALNS Solver

use u_routing::models::Customer;
use u_routing::distance::DistanceMatrix;
use u_routing::alns::{RoutingAlnsProblem, destroy::RandomRemoval, repair::GreedyInsertion};
use u_metaheur::alns::{AlnsConfig, AlnsRunner};

let customers = vec![
    Customer::depot(0.0, 0.0),
    Customer::new(1, 1.0, 0.0, 10, 0.0),
    Customer::new(2, 2.0, 0.0, 10, 0.0),
    Customer::new(3, 3.0, 0.0, 10, 0.0),
];
let dm = DistanceMatrix::from_customers(&customers);

let problem = RoutingAlnsProblem::new(customers.clone(), dm.clone(), 30);
let destroy = vec![RandomRemoval];
let repair = vec![GreedyInsertion::new(dm, customers, 30)];
let config = AlnsConfig::default().with_max_iterations(5000).with_seed(42);

let result = AlnsRunner::run(&problem, &destroy, &repair, &config);
println!("Best cost: {}", result.best_cost);

Architecture

u-routing
├── models/          Domain types (Customer, Vehicle, Route, Solution)
├── distance/        Distance matrix
├── evaluation/      Route evaluator + constraint checking
├── constructive/    Nearest Neighbor, Clarke-Wright Savings
├── local_search/    2-opt, Relocate
├── ga/              Giant tour + Split DP + GaProblem bridge
└── alns/            Destroy/Repair operators + AlnsProblem bridge

Dependencies

• u-metaheur — GA/ALNS framework
• u-numflow — Math primitives, RNG

References

• Clarke, G. & Wright, J.W. (1964). "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points"
• Croes, G.A. (1958). "A method for solving traveling salesman problems"
• Or, I. (1976). "Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking"
• Prins, C. (2004). "A simple and effective evolutionary algorithm for the vehicle routing problem"
• Ropke, S. & Pisinger, D. (2006). "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows"
• Shaw, P. (1998). "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems"

WebAssembly / npm

Available as an npm package via wasm-pack.

npm install @iyulab/u-routing

Quick Start

import init, { solve_vrp } from '@iyulab/u-routing';

await init();
const result = solve_vrp({
  customers: [
    { id: 1, x: 1.0, y: 2.0, demand: 10 },
    { id: 2, x: 3.0, y: 4.0, demand: 15 },
  ],
  vehicles: [{ capacity: 100 }],
  depot: { x: 0.0, y: 0.0 },
  method: "nn"
});

Functions

solve_vrp(input) -> VrpOutput

Solve a capacitated VRP with optional time windows. Four solver methods available.

Methods: "nn" (Nearest Neighbor), "savings" (Clarke-Wright), "ga" (Genetic Algorithm + Split DP), "alns" (Adaptive Large Neighborhood Search).

Input:

{
  "customers": [
    { "id": 1, "x": 1.0, "y": 2.0, "demand": 10, "service_time": 0.5, "time_window": [8.0, 12.0] }
  ],
  "vehicles": [{ "capacity": 100 }],
  "depot": { "x": 0.0, "y": 0.0 },
  "method": "ga",
  "config": {
    "population_size": 50, "max_generations": 200,
    "mutation_rate": 0.1, "elite_ratio": 0.1,
    "max_iterations": 500, "seed": 42
  }
}

GA config uses population_size, max_generations, mutation_rate, elite_ratio. ALNS config uses max_iterations. Both accept seed.

Config constraints:

| Parameter | Method | Constraint | Default | |---|---|---|---| | population_size | GA | >= 2 | 50 | | max_generations | GA | >= 1 | 200 | | mutation_rate | GA | 0.0 – 1.0 (clamped) | 0.1 | | elite_ratio | GA | 0.0 – 1.0; must not fill entire population | 0.1 | | max_iterations | ALNS | >= 1 | 500 | | seed | Both | any u64 (optional) | random |

Error handling:

solve_vrp() returns a JS error (string) for:

• Invalid JSON input (missing required fields, wrong types)
• Unknown method name
• Invalid config values (e.g., population_size: 0, max_iterations: 0)

Errors are returned as rejected promises — they never cause RuntimeError: unreachable panics.

Output:

{
  "routes": [[1, 3, 5], [2, 4]],
  "total_distance": 42.5,
  "num_vehicles": 2,
  "method_used": "ga",
  "computation_time_ms": 120.0
}

Related

• u-numflow — Mathematical optimization primitives
• u-metaheur — Metaheuristic algorithms
• u-schedule — Scheduling optimization