routik_solver/
model.rs

1//! VRP data model.
2//!
3//! Ids are newtypes — nothing stringly- or `usize`-typed leaks into the public
4//! API. [`LocationId`] is the one exception: it is the index into a
5//! [`CostMatrix`](crate::matrix::CostMatrix), where `0` is the depot and
6//! `1..=n` are the stops in [`Problem::stops`] order.
7
8/// A geographic coordinate in decimal degrees (WGS84).
9#[derive(Debug, Clone, Copy, PartialEq)]
10pub struct Coord {
11    pub lat: f64,
12    pub lon: f64,
13}
14
15impl Coord {
16    #[must_use]
17    pub const fn new(lat: f64, lon: f64) -> Self {
18        Self { lat, lon }
19    }
20}
21
22/// Stable, caller-facing identifier of a stop.
23#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
24pub struct StopId(pub u32);
25
26/// Stable, caller-facing identifier of a vehicle.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
28pub struct VehicleId(pub u32);
29
30/// Index into a [`CostMatrix`](crate::matrix::CostMatrix).
31///
32/// `LocationId(0)` is always the depot; `LocationId(1..=n)` map to
33/// [`Problem::stops`] in order. The solver works in terms of these indices;
34/// callers never build them by hand.
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
36pub struct LocationId(pub usize);
37
38impl LocationId {
39    /// The depot, always index `0`.
40    pub const DEPOT: LocationId = LocationId(0);
41}
42
43/// A `[start, end]` service window, in the same time unit as the matrix.
44///
45/// Not enforced yet by the construction heuristic — kept here so the model is
46/// stable for the upcoming time-window constraint.
47#[derive(Debug, Clone, Copy, PartialEq)]
48pub struct TimeWindow {
49    pub start: f64,
50    pub end: f64,
51}
52
53/// A delivery stop: where to go, how much to drop, and when.
54#[derive(Debug, Clone, PartialEq)]
55pub struct Stop {
56    pub id: StopId,
57    pub coord: Coord,
58    /// Units of demand to drop at this stop.
59    pub demand: u32,
60    /// Optional service window (not yet enforced).
61    pub time_window: Option<TimeWindow>,
62    /// Time spent servicing the stop, in the matrix time unit.
63    pub service_time: f64,
64}
65
66/// A vehicle in the (assumed homogeneous) fleet.
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub struct Vehicle {
69    pub id: VehicleId,
70    pub capacity: u32,
71}
72
73/// A capacitated VRP instance: one depot, a set of stops, a fleet.
74#[derive(Debug, Clone, PartialEq)]
75pub struct Problem {
76    pub depot: Coord,
77    pub stops: Vec<Stop>,
78    pub vehicles: Vec<Vehicle>,
79    /// Optional depot operating window. Its `end` is the latest time a vehicle
80    /// may return to the depot; `start` is when vehicles may leave. `None`
81    /// means the depot imposes no temporal bound (pure CVRP behaviour).
82    pub depot_window: Option<TimeWindow>,
83}
84
85impl Problem {
86    /// Number of locations including the depot (`stops.len() + 1`).
87    #[must_use]
88    pub fn location_count(&self) -> usize {
89        self.stops.len() + 1
90    }
91
92    /// All coordinates indexed by [`LocationId`]: depot first, then stops.
93    #[must_use]
94    pub fn coords(&self) -> Vec<Coord> {
95        let mut coords = Vec::with_capacity(self.location_count());
96        coords.push(self.depot);
97        coords.extend(self.stops.iter().map(|s| s.coord));
98        coords
99    }
100
101    /// Earliest time a vehicle may leave the depot (`0` if unconstrained).
102    #[must_use]
103    pub fn depot_open(&self) -> f64 {
104        self.depot_window.map_or(0.0, |w| w.start)
105    }
106
107    /// Latest time a vehicle may return to the depot (`+∞` if unconstrained).
108    #[must_use]
109    pub fn depot_due(&self) -> f64 {
110        self.depot_window.map_or(f64::INFINITY, |w| w.end)
111    }
112}
113
114/// One vehicle's tour: the ordered stops it serves and its rolled-up metrics.
115///
116/// The depot is implicit at both ends (`depot → stop_ids → depot`); it is not
117/// listed in `stop_ids`.
118#[derive(Debug, Clone, PartialEq)]
119pub struct Route {
120    pub vehicle_id: VehicleId,
121    pub stop_ids: Vec<StopId>,
122    /// Total demand carried; never exceeds the vehicle capacity.
123    pub load: u32,
124    pub distance: f64,
125    pub time: f64,
126}
127
128/// A complete assignment of stops to routes, plus rolled-up totals and the
129/// stops the solver could not place.
130#[derive(Debug, Clone, PartialEq)]
131pub struct Solution {
132    pub routes: Vec<Route>,
133    pub total_distance: f64,
134    pub total_time: f64,
135    /// True iff every hard constraint (capacity, time windows) holds **and**
136    /// every stop was assigned to a route. A solution carrying
137    /// [`unassigned`](Self::unassigned) stops is never `feasible`, even though
138    /// the routes it did build are each individually valid.
139    pub feasible: bool,
140    /// Stops the solver could not place, each with an indicative reason. Empty on
141    /// a fully-solved instance.
142    pub unassigned: Vec<Unassigned>,
143}
144
145/// A stop the solver could not place on any route, with an indicative reason.
146///
147/// The reason is a **diagnostic, not a proof**: it reports the constraint that
148/// blocked the last attempt to place the stop. A stop reported as unassigned may
149/// still be placeable under a different (e.g. larger or differently-ordered)
150/// fleet assignment; conversely the reported `code` is the dominant blocker the
151/// solver observed, not necessarily the only one.
152#[derive(Debug, Clone, PartialEq, Eq)]
153pub struct Unassigned {
154    /// The stop that stayed unassigned.
155    pub stop: StopId,
156    /// Machine-readable cause.
157    pub code: UnassignedCode,
158    /// Human-readable explanation of the blocking constraint.
159    pub detail: String,
160}
161
162/// Why a stop could not be placed. Stable, machine-readable diagnostic codes.
163///
164/// [`MissingSkill`](Self::MissingSkill) and [`MaxTravelTime`](Self::MaxTravelTime)
165/// are **reserved**: the current model has neither skills nor a per-vehicle
166/// travel-time bound, so the solver never emits them yet. They are part of the
167/// enum so the contract is stable for when those constraints land.
168#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
169pub enum UnassignedCode {
170    /// The stop cannot be reached, serviced within its window, and returned
171    /// before the depot closes — even alone on an otherwise empty route.
172    TimeWindowInfeasible,
173    /// The stop's demand exceeds the capacity of the (smallest) vehicle, so it
174    /// fits on no route on its own.
175    CapacityExceeded,
176    /// The stop requires a skill no vehicle provides. *Reserved* — not emitted
177    /// yet (the model has no skills).
178    MissingSkill,
179    /// Serving the stop would exceed a vehicle's maximum travel time. *Reserved*
180    /// — not emitted yet (the model has no max-travel bound).
181    MaxTravelTime,
182    /// Every vehicle is already assigned and none of the built routes can absorb
183    /// the stop — the fleet is exhausted.
184    NoCompatibleVehicle,
185}
186
187impl UnassignedCode {
188    /// The stable snake_case wire form of the code.
189    #[must_use]
190    pub const fn as_str(self) -> &'static str {
191        match self {
192            UnassignedCode::TimeWindowInfeasible => "time_window_infeasible",
193            UnassignedCode::CapacityExceeded => "capacity_exceeded",
194            UnassignedCode::MissingSkill => "missing_skill",
195            UnassignedCode::MaxTravelTime => "max_travel_time",
196            UnassignedCode::NoCompatibleVehicle => "no_compatible_vehicle",
197        }
198    }
199}
routik_solver/model.rs

routik_solver/
model.rs
