ferrox/vrptw/
problem.rs

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

ferrox/vrptw/
problem.rs
