ferrox/vrptw/
problem.rs

1use serde::{Deserialize, Serialize};
2
3use converge_pack::{ExecutionIdentity, FactPayload};
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
6#[serde(rename_all = "snake_case")]
7pub enum VrptwSolveStatus {
8    Optimal,
9    Feasible,
10    Infeasible,
11    Error,
12    Invalid,
13}
14
15impl VrptwSolveStatus {
16    pub fn is_successful(self) -> bool {
17        matches!(self, Self::Optimal | Self::Feasible)
18    }
19}
20
21/// A customer to be visited by the vehicle.
22#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
23#[serde(deny_unknown_fields)]
24pub struct Customer {
25    pub id: usize,
26    pub name: String,
27    pub x: f64,
28    pub y: f64,
29    /// Earliest arrival time.
30    pub window_open: i64,
31    /// Latest arrival time (must arrive by this time).
32    pub window_close: i64,
33    /// Service duration at this customer.
34    pub service_time: i64,
35}
36
37impl Customer {
38    pub fn travel_to(&self, other: &Customer) -> f64 {
39        let dx = self.x - other.x;
40        let dy = self.y - other.y;
41        (dx * dx + dy * dy).sqrt()
42    }
43}
44
45/// The depot — vehicle starts and ends here.
46#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
47#[serde(deny_unknown_fields)]
48pub struct Depot {
49    pub x: f64,
50    pub y: f64,
51    pub ready_time: i64,
52    pub due_time: i64,
53}
54
55impl Depot {
56    pub fn travel_to_customer(&self, c: &Customer) -> f64 {
57        let dx = self.x - c.x;
58        let dy = self.y - c.y;
59        (dx * dx + dy * dy).sqrt()
60    }
61}
62
63/// Seeded into `ContextKey::Seeds` with id prefix `"vrptw-request:"`.
64///
65/// Models a single-vehicle TSP with Time Windows (TSPTW).
66/// Customers are optional: the objective is to maximise customers visited
67/// while respecting time windows and the vehicle's return deadline.
68#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
69#[serde(deny_unknown_fields)]
70pub struct VrptwRequest {
71    pub id: String,
72    pub depot: Depot,
73    pub customers: Vec<Customer>,
74    #[serde(default = "default_time_limit")]
75    pub time_limit_seconds: f64,
76}
77
78impl FactPayload for VrptwRequest {
79    const FAMILY: &'static str = "ferrox.vrptw.request";
80    const VERSION: u16 = 1;
81}
82
83fn default_time_limit() -> f64 {
84    30.0
85}
86
87/// One stop in the vehicle's route.
88#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
89#[serde(deny_unknown_fields)]
90pub struct RouteStop {
91    pub customer_id: usize,
92    pub customer_name: String,
93    pub arrival: i64,
94    pub departure: i64,
95}
96
97/// Written to `ContextKey::Strategies` with id prefix `"vrptw-plan-<solver>:"`.
98#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
99#[serde(deny_unknown_fields)]
100pub struct VrptwPlan {
101    pub request_id: String,
102    /// Ordered stops (depot → customers → depot is implied).
103    pub route: Vec<RouteStop>,
104    pub customers_total: usize,
105    pub customers_visited: usize,
106    /// Total travel distance (unscaled, Euclidean).
107    pub total_distance: f64,
108    /// Time the vehicle returns to depot.
109    pub return_time: i64,
110    pub solver: String,
111    pub execution_identity: ExecutionIdentity,
112    pub status: VrptwSolveStatus,
113    pub wall_time_seconds: f64,
114}
115
116impl FactPayload for VrptwPlan {
117    const FAMILY: &'static str = "ferrox.vrptw.plan";
118    const VERSION: u16 = 1;
119}
120
121impl VrptwPlan {
122    #[allow(clippy::cast_precision_loss)]
123    pub fn visit_ratio(&self) -> f64 {
124        if self.customers_total == 0 {
125            return 0.0;
126        }
127        self.customers_visited as f64 / self.customers_total as f64
128    }
129}
130
131#[cfg(test)]
132mod tests {
133    use super::*;
134    use crate::solver_identity::non_native_solver_identity;
135
136    fn cust(x: f64, y: f64) -> Customer {
137        Customer {
138            id: 1,
139            name: "c".into(),
140            x,
141            y,
142            window_open: 0,
143            window_close: 100,
144            service_time: 1,
145        }
146    }
147
148    #[test]
149    fn customer_travel_is_euclidean() {
150        let a = cust(0.0, 0.0);
151        let b = cust(3.0, 4.0);
152        assert!((a.travel_to(&b) - 5.0).abs() < 1e-9);
153    }
154
155    #[test]
156    fn depot_travel_to_customer_is_euclidean() {
157        let d = Depot {
158            x: 0.0,
159            y: 0.0,
160            ready_time: 0,
161            due_time: 100,
162        };
163        assert!((d.travel_to_customer(&cust(0.0, 5.0)) - 5.0).abs() < 1e-9);
164    }
165
166    #[test]
167    fn visit_ratio_zero_when_no_customers() {
168        let p = VrptwPlan {
169            request_id: "r".into(),
170            route: vec![],
171            customers_total: 0,
172            customers_visited: 0,
173            total_distance: 0.0,
174            return_time: 0,
175            solver: "x".into(),
176            execution_identity: non_native_solver_identity("x", "test"),
177            status: VrptwSolveStatus::Feasible,
178            wall_time_seconds: 0.0,
179        };
180        assert!((p.visit_ratio() - 0.0).abs() < f64::EPSILON);
181    }
182
183    #[test]
184    fn request_default_time_limit() {
185        let json =
186            r#"{"id":"r","depot":{"x":0,"y":0,"ready_time":0,"due_time":100},"customers":[]}"#;
187        let r: VrptwRequest = serde_json::from_str(json).unwrap();
188        assert!((r.time_limit_seconds - 30.0).abs() < f64::EPSILON);
189    }
190}
ferrox/vrptw/problem.rs

ferrox/vrptw/
problem.rs
