routik-solver 0.1.0

//! Hard-constraint feasibility and the per-route metrics the construction and
//! search share.
//!
//! A route is a sequence of stop location indices (`1..=n`), with the depot
//! implicit at both ends. The two hard constraints are **capacity** and
//! **time windows**; a route that breaks either is rejected outright.
//!
//! Time model (Solomon VRPTW): a vehicle leaves the depot at
//! [`Problem::depot_open`]. Reaching a stop, `arrive = t + time(prev, stop)`;
//! if it arrives before the stop's ready time it *waits*; service may not
//! **begin** after the window end (arriving early is fine, arriving late is
//! not); then `t = begin + service_time`. The return leg must land at the
//! depot no later than [`Problem::depot_due`].

use crate::matrix::CostMatrix;
use crate::model::{LocationId, Problem, Route, Solution};

/// Rolled-up metrics of a single feasible route.
#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) struct RouteMetrics {
    /// Total travelled distance, including both depot legs.
    pub distance: f64,
    /// Route duration: depot-departure to depot-return, including waiting and
    /// service. Equals travel + service when no waiting occurs (e.g. no
    /// windows), matching the pure-CVRP definition.
    pub duration: f64,
    /// Total demand carried.
    pub load: u32,
}

/// Walk a route sequence once, rolling up metrics and reporting whether every
/// hard constraint held. The metrics are always well-defined (we never stop
/// early), so callers that already know a route is feasible can take the
/// metrics and ignore the flag; callers validating a candidate read the flag.
pub(crate) fn walk_route(
    problem: &Problem,
    matrix: &impl CostMatrix,
    capacity: u32,
    seq: &[usize],
) -> (RouteMetrics, bool) {
    if seq.is_empty() {
        let zero = RouteMetrics {
            distance: 0.0,
            duration: 0.0,
            load: 0,
        };
        return (zero, true);
    }

    let depart = problem.depot_open();
    let mut prev = LocationId::DEPOT;
    let mut t = depart;
    let mut distance = 0.0;
    // u64 so summing adversarially-large demands can't overflow (and panic); a
    // feasible route's load is ≤ capacity ≤ u32::MAX, so it narrows back losslessly.
    let mut load: u64 = 0;
    let mut feasible = true;

    for &loc in seq {
        let cur = LocationId(loc);
        distance += matrix.distance(prev, cur);
        let arrive = t + matrix.time(prev, cur);
        let stop = &problem.stops[loc - 1];
        let begin = match stop.time_window {
            Some(tw) => {
                let begin = arrive.max(tw.start);
                if begin > tw.end {
                    feasible = false; // arrived too late to start service
                }
                begin
            }
            None => arrive,
        };
        t = begin + stop.service_time;
        load += u64::from(stop.demand);
        prev = cur;
    }

    distance += matrix.distance(prev, LocationId::DEPOT);
    t += matrix.time(prev, LocationId::DEPOT);
    feasible &= t <= problem.depot_due(); // returned to depot in time
    feasible &= load <= u64::from(capacity); // within capacity

    let metrics = RouteMetrics {
        distance,
        duration: t - depart,
        // Feasible ⇒ load ≤ capacity ≤ u32::MAX; an overloaded candidate (verdict
        // already false) clamps rather than panicking — it is never emitted.
        load: u32::try_from(load).unwrap_or(u32::MAX),
    };
    (metrics, feasible)
}

/// Evaluate a route sequence under capacity + time windows.
///
/// Returns [`RouteMetrics`] iff the route is feasible, `None` on any
/// hard-constraint violation (late service, late depot return, overload). An
/// empty sequence is feasible with zero metrics.
pub(crate) fn evaluate_route(
    problem: &Problem,
    matrix: &impl CostMatrix,
    capacity: u32,
    seq: &[usize],
) -> Option<RouteMetrics> {
    match walk_route(problem, matrix, capacity, seq) {
        (metrics, true) => Some(metrics),
        (_, false) => None,
    }
}

/// Assemble a public [`Solution`] from internal index-routes (each a sequence
/// of `1..=n` stop indices). Empty routes are dropped; the remaining routes are
/// paired with vehicles in order. `feasible` rolls up every route's check.
///
/// Contract: the number of non-empty routes must not exceed the fleet size
/// (both callers — construction and search — guarantee this); if it ever does,
/// the surplus routes are dropped and `feasible` is forced `false`.
pub(crate) fn build_solution(
    problem: &Problem,
    matrix: &impl CostMatrix,
    capacity: u32,
    routes: &[Vec<usize>],
) -> Solution {
    let mut out_routes = Vec::new();
    let mut total_distance = 0.0;
    let mut total_time = 0.0;
    let mut feasible = true;

    for (route, vehicle) in routes
        .iter()
        .filter(|r| !r.is_empty())
        .zip(&problem.vehicles)
    {
        let (metrics, ok) = walk_route(problem, matrix, capacity, route);
        feasible &= ok;
        let stop_ids = route.iter().map(|&loc| problem.stops[loc - 1].id).collect();
        total_distance += metrics.distance;
        total_time += metrics.duration;
        out_routes.push(Route {
            vehicle_id: vehicle.id,
            stop_ids,
            load: metrics.load,
            distance: metrics.distance,
            time: metrics.duration,
        });
    }

    let non_empty = routes.iter().filter(|r| !r.is_empty()).count();
    if non_empty > out_routes.len() {
        feasible = false; // ran out of vehicles to assign
    }

    // Construction and search keep the routed-stop set; whoever has the
    // unassigned diagnostics (the construction) stamps them onto the result.
    Solution {
        routes: out_routes,
        total_distance,
        total_time,
        feasible,
        unassigned: Vec::new(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::matrix::EuclideanMatrix;
    use crate::model::{Coord, Stop, StopId, TimeWindow, Vehicle, VehicleId};

    /// Depot at origin, stops on the x-axis at x = 10, 20, 30 (so leg times of
    /// 10 each under the Euclidean unit-speed matrix). Windows optional.
    fn problem(windows: [Option<(f64, f64)>; 3], depot_due: f64) -> Problem {
        let mk = |id: u32, x: f64, w: Option<(f64, f64)>| Stop {
            id: StopId(id),
            coord: Coord::new(0.0, x), // lon = x, lat = 0
            demand: 10,
            time_window: w.map(|(start, end)| TimeWindow { start, end }),
            service_time: 5.0,
        };
        Problem {
            depot: Coord::new(0.0, 0.0),
            stops: vec![
                mk(1, 10.0, windows[0]),
                mk(2, 20.0, windows[1]),
                mk(3, 30.0, windows[2]),
            ],
            vehicles: vec![Vehicle {
                id: VehicleId(1),
                capacity: 100,
            }],
            depot_window: Some(TimeWindow {
                start: 0.0,
                end: depot_due,
            }),
        }
    }

    #[test]
    fn no_windows_route_is_feasible_and_metrics_add_up() {
        let p = problem([None, None, None], f64::INFINITY);
        let m = EuclideanMatrix::from_problem(&p);
        let metrics = evaluate_route(&p, &m, 100, &[1, 2, 3]).expect("feasible");
        // distance: 10 + 10 + 10 + 30 (return) = 60.
        assert!((metrics.distance - 60.0).abs() < 1e-9);
        // duration: travel 60 + 3 services * 5 = 75 (no waiting).
        assert!((metrics.duration - 75.0).abs() < 1e-9);
        assert_eq!(metrics.load, 30);
    }

    #[test]
    fn late_window_is_rejected() {
        // Stop 3 reachable only at t=20 (travel) but window closes at 15.
        let p = problem([None, None, Some((0.0, 15.0))], f64::INFINITY);
        let m = EuclideanMatrix::from_problem(&p);
        assert!(evaluate_route(&p, &m, 100, &[1, 2, 3]).is_none());
    }

    #[test]
    fn early_arrival_waits_then_serves() {
        // Stop 1 not ready until t=100; arrival at t=10 must wait.
        let p = problem([Some((100.0, 200.0)), None, None], f64::INFINITY);
        let m = EuclideanMatrix::from_problem(&p);
        let metrics = evaluate_route(&p, &m, 100, &[1, 2, 3]).expect("feasible");
        // begin@1 = 100, depart 105; arrive@2 = 115 (+5 = 120); arrive@3 = 130
        // (+5 = 135); return leg 30 -> 165.
        assert!(
            (metrics.duration - 165.0).abs() < 1e-9,
            "got {}",
            metrics.duration
        );
    }

    #[test]
    fn late_depot_return_is_rejected() {
        let p = problem([None, None, None], 50.0); // return needs t=75 > 50
        let m = EuclideanMatrix::from_problem(&p);
        assert!(evaluate_route(&p, &m, 100, &[1, 2, 3]).is_none());
    }

    #[test]
    fn overload_is_rejected() {
        let p = problem([None, None, None], f64::INFINITY);
        let m = EuclideanMatrix::from_problem(&p);
        assert!(evaluate_route(&p, &m, 25, &[1, 2, 3]).is_none()); // load 30 > 25
    }
}