routik-solver 0.1.0

//! VRP data model.
//!
//! Ids are newtypes — nothing stringly- or `usize`-typed leaks into the public
//! API. [`LocationId`] is the one exception: it is the index into a
//! [`CostMatrix`](crate::matrix::CostMatrix), where `0` is the depot and
//! `1..=n` are the stops in [`Problem::stops`] order.

/// A geographic coordinate in decimal degrees (WGS84).
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Coord {
    pub lat: f64,
    pub lon: f64,
}

impl Coord {
    #[must_use]
    pub const fn new(lat: f64, lon: f64) -> Self {
        Self { lat, lon }
    }
}

/// Stable, caller-facing identifier of a stop.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct StopId(pub u32);

/// Stable, caller-facing identifier of a vehicle.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct VehicleId(pub u32);

/// Index into a [`CostMatrix`](crate::matrix::CostMatrix).
///
/// `LocationId(0)` is always the depot; `LocationId(1..=n)` map to
/// [`Problem::stops`] in order. The solver works in terms of these indices;
/// callers never build them by hand.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct LocationId(pub usize);

impl LocationId {
    /// The depot, always index `0`.
    pub const DEPOT: LocationId = LocationId(0);
}

/// A `[start, end]` service window, in the same time unit as the matrix.
///
/// Not enforced yet by the construction heuristic — kept here so the model is
/// stable for the upcoming time-window constraint.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct TimeWindow {
    pub start: f64,
    pub end: f64,
}

/// A delivery stop: where to go, how much to drop, and when.
#[derive(Debug, Clone, PartialEq)]
pub struct Stop {
    pub id: StopId,
    pub coord: Coord,
    /// Units of demand to drop at this stop.
    pub demand: u32,
    /// Optional service window (not yet enforced).
    pub time_window: Option<TimeWindow>,
    /// Time spent servicing the stop, in the matrix time unit.
    pub service_time: f64,
}

/// A vehicle in the (assumed homogeneous) fleet.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Vehicle {
    pub id: VehicleId,
    pub capacity: u32,
}

/// A capacitated VRP instance: one depot, a set of stops, a fleet.
#[derive(Debug, Clone, PartialEq)]
pub struct Problem {
    pub depot: Coord,
    pub stops: Vec<Stop>,
    pub vehicles: Vec<Vehicle>,
    /// Optional depot operating window. Its `end` is the latest time a vehicle
    /// may return to the depot; `start` is when vehicles may leave. `None`
    /// means the depot imposes no temporal bound (pure CVRP behaviour).
    pub depot_window: Option<TimeWindow>,
}

impl Problem {
    /// Number of locations including the depot (`stops.len() + 1`).
    #[must_use]
    pub fn location_count(&self) -> usize {
        self.stops.len() + 1
    }

    /// All coordinates indexed by [`LocationId`]: depot first, then stops.
    #[must_use]
    pub fn coords(&self) -> Vec<Coord> {
        let mut coords = Vec::with_capacity(self.location_count());
        coords.push(self.depot);
        coords.extend(self.stops.iter().map(|s| s.coord));
        coords
    }

    /// Earliest time a vehicle may leave the depot (`0` if unconstrained).
    #[must_use]
    pub fn depot_open(&self) -> f64 {
        self.depot_window.map_or(0.0, |w| w.start)
    }

    /// Latest time a vehicle may return to the depot (`+∞` if unconstrained).
    #[must_use]
    pub fn depot_due(&self) -> f64 {
        self.depot_window.map_or(f64::INFINITY, |w| w.end)
    }
}

/// One vehicle's tour: the ordered stops it serves and its rolled-up metrics.
///
/// The depot is implicit at both ends (`depot → stop_ids → depot`); it is not
/// listed in `stop_ids`.
#[derive(Debug, Clone, PartialEq)]
pub struct Route {
    pub vehicle_id: VehicleId,
    pub stop_ids: Vec<StopId>,
    /// Total demand carried; never exceeds the vehicle capacity.
    pub load: u32,
    pub distance: f64,
    pub time: f64,
}

/// A complete assignment of stops to routes, plus rolled-up totals and the
/// stops the solver could not place.
#[derive(Debug, Clone, PartialEq)]
pub struct Solution {
    pub routes: Vec<Route>,
    pub total_distance: f64,
    pub total_time: f64,
    /// True iff every hard constraint (capacity, time windows) holds **and**
    /// every stop was assigned to a route. A solution carrying
    /// [`unassigned`](Self::unassigned) stops is never `feasible`, even though
    /// the routes it did build are each individually valid.
    pub feasible: bool,
    /// Stops the solver could not place, each with an indicative reason. Empty on
    /// a fully-solved instance.
    pub unassigned: Vec<Unassigned>,
}

/// A stop the solver could not place on any route, with an indicative reason.
///
/// The reason is a **diagnostic, not a proof**: it reports the constraint that
/// blocked the last attempt to place the stop. A stop reported as unassigned may
/// still be placeable under a different (e.g. larger or differently-ordered)
/// fleet assignment; conversely the reported `code` is the dominant blocker the
/// solver observed, not necessarily the only one.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Unassigned {
    /// The stop that stayed unassigned.
    pub stop: StopId,
    /// Machine-readable cause.
    pub code: UnassignedCode,
    /// Human-readable explanation of the blocking constraint.
    pub detail: String,
}

/// Why a stop could not be placed. Stable, machine-readable diagnostic codes.
///
/// [`MissingSkill`](Self::MissingSkill) and [`MaxTravelTime`](Self::MaxTravelTime)
/// are **reserved**: the current model has neither skills nor a per-vehicle
/// travel-time bound, so the solver never emits them yet. They are part of the
/// enum so the contract is stable for when those constraints land.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum UnassignedCode {
    /// The stop cannot be reached, serviced within its window, and returned
    /// before the depot closes — even alone on an otherwise empty route.
    TimeWindowInfeasible,
    /// The stop's demand exceeds the capacity of the (smallest) vehicle, so it
    /// fits on no route on its own.
    CapacityExceeded,
    /// The stop requires a skill no vehicle provides. *Reserved* — not emitted
    /// yet (the model has no skills).
    MissingSkill,
    /// Serving the stop would exceed a vehicle's maximum travel time. *Reserved*
    /// — not emitted yet (the model has no max-travel bound).
    MaxTravelTime,
    /// Every vehicle is already assigned and none of the built routes can absorb
    /// the stop — the fleet is exhausted.
    NoCompatibleVehicle,
}

impl UnassignedCode {
    /// The stable snake_case wire form of the code.
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            UnassignedCode::TimeWindowInfeasible => "time_window_infeasible",
            UnassignedCode::CapacityExceeded => "capacity_exceeded",
            UnassignedCode::MissingSkill => "missing_skill",
            UnassignedCode::MaxTravelTime => "max_travel_time",
            UnassignedCode::NoCompatibleVehicle => "no_compatible_vehicle",
        }
    }
}