vrp_gpu/
instance.rs

1//! Solomon instance data structures and flat Structure-of-Arrays (SoA) layout.
2
3use std::fmt;
4use std::str::FromStr;
5
6/// Configuration and fleet constraints for a Solomon VRP instance.
7#[derive(Debug, Clone, PartialEq)]
8pub struct VehicleConfig {
9    /// Total number of available vehicles.
10    pub num_vehicles: usize,
11    /// Maximum capacity per vehicle.
12    pub capacity: f32,
13}
14
15/// A parsed Solomon CVRP instance with contiguous memory layouts (SoA)
16/// optimized for CPU caching and direct GPU device transfers.
17#[derive(Debug, Clone, PartialEq)]
18pub struct SolomonInstance {
19    /// Instance identifier / name (e.g., "C101").
20    pub name: String,
21    /// Fleet and vehicle capacity settings.
22    pub vehicle: VehicleConfig,
23    /// Total number of nodes (1 depot at index 0 + N customers).
24    pub num_nodes: usize,
25    /// X-coordinates of all nodes (depot at index 0).
26    pub xs: Vec<f32>,
27    /// Y-coordinates of all nodes (depot at index 0).
28    pub ys: Vec<f32>,
29    /// Demand of each node (depot demand at index 0 is always 0.0).
30    pub demands: Vec<f32>,
31    /// Ready times for time-window constraints (available for rich VRP extensions).
32    pub ready_times: Vec<f32>,
33    /// Due times for time-window constraints.
34    pub due_times: Vec<f32>,
35    /// Service times at each customer.
36    pub service_times: Vec<f32>,
37    /// Flattened 1D row-major euclidean distance matrix of size `num_nodes * num_nodes`.
38    /// Distance from node `i` to node `j` is accessed via `distance_matrix[i * num_nodes + j]`.
39    pub distance_matrix: Vec<f32>,
40}
41
42impl SolomonInstance {
43    /// Validates the public arrays and the symmetric CVRP cost model.
44    ///
45    /// Call this after constructing or mutating an instance manually. Validation
46    /// is O(n²), including finite, nonnegative, symmetric distances.
47    pub fn validate(&self) -> Result<(), &'static str> {
48        let n = self.num_nodes;
49        if n == 0 {
50            return Err("instance must contain a depot");
51        }
52        if self.vehicle.num_vehicles == 0
53            || !self.vehicle.capacity.is_finite()
54            || self.vehicle.capacity <= 0.0
55        {
56            return Err("fleet size and finite vehicle capacity must be positive");
57        }
58        let arrays = [
59            &self.xs,
60            &self.ys,
61            &self.demands,
62            &self.ready_times,
63            &self.due_times,
64            &self.service_times,
65        ];
66        if arrays.iter().any(|values| values.len() != n) {
67            return Err("node arrays must match num_nodes");
68        }
69        if arrays
70            .iter()
71            .any(|values| values.iter().any(|value| !value.is_finite()))
72        {
73            return Err("node values must be finite");
74        }
75        if self.demands[0] != 0.0 || self.demands.iter().any(|&demand| demand < 0.0) {
76            return Err("demands must be nonnegative and depot demand must be zero");
77        }
78        if self
79            .ready_times
80            .iter()
81            .zip(&self.due_times)
82            .any(|(&ready, &due)| ready < 0.0 || due < ready)
83            || self.service_times.iter().any(|&service| service < 0.0)
84        {
85            return Err("time windows and service times must be nonnegative and ordered");
86        }
87        if n.checked_mul(n) != Some(self.distance_matrix.len()) {
88            return Err("distance matrix must contain num_nodes squared entries");
89        }
90        for i in 0..n {
91            for j in 0..n {
92                let distance = self.distance_matrix[i * n + j];
93                if !distance.is_finite()
94                    || distance < 0.0
95                    || (i == j && distance != 0.0)
96                    || distance != self.distance_matrix[j * n + i]
97                {
98                    return Err(
99                        "distance matrix must be finite, nonnegative, symmetric, with zero diagonal",
100                    );
101                }
102            }
103        }
104        Ok(())
105    }
106
107    /// Returns the euclidean distance between node `from` and node `to`.
108    #[inline(always)]
109    pub fn distance(&self, from: usize, to: usize) -> f32 {
110        debug_assert!(from < self.num_nodes && to < self.num_nodes);
111        self.distance_matrix[from * self.num_nodes + to]
112    }
113
114    /// Returns the demand of `node`.
115    #[inline(always)]
116    pub fn demand(&self, node: usize) -> f32 {
117        debug_assert!(node < self.num_nodes);
118        self.demands[node]
119    }
120}
121
122/// Computes a flattened 1D row-major euclidean distance matrix from coordinate slices.
123///
124/// Returns a vector of size `n * n`, where `n = xs.len()`.
125/// Element at index `i * n + j` is `sqrt((xs[i] - xs[j])^2 + (ys[i] - ys[j])^2)`.
126pub fn compute_distance_matrix(xs: &[f32], ys: &[f32]) -> Vec<f32> {
127    assert_eq!(
128        xs.len(),
129        ys.len(),
130        "X and Y coordinate slices must have identical length"
131    );
132    let n = xs.len();
133    let mut matrix = Vec::with_capacity(n * n);
134
135    for i in 0..n {
136        let xi = xs[i];
137        let yi = ys[i];
138        for j in 0..n {
139            if i == j {
140                matrix.push(0.0);
141            } else {
142                let dx = xi - xs[j];
143                let dy = yi - ys[j];
144                matrix.push((dx * dx + dy * dy).sqrt());
145            }
146        }
147    }
148
149    matrix
150}
151
152/// Errors that can occur during Solomon instance parsing.
153#[derive(Debug, Clone, PartialEq, Eq)]
154pub enum SolomonParseError {
155    /// Input file or string was empty.
156    EmptyInput,
157    /// Vehicle section header or data was missing or malformed.
158    InvalidVehicleSection(String),
159    /// Customer section header or data row was malformed.
160    InvalidCustomerRow(String),
161    /// No customer/depot nodes found in the instance.
162    NoNodesFound,
163    /// Parsed values do not form a valid symmetric CVRP instance.
164    InvalidInstance(String),
165}
166
167impl fmt::Display for SolomonParseError {
168    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
169        match self {
170            Self::EmptyInput => write!(f, "Solomon instance input is empty"),
171            Self::InvalidVehicleSection(msg) => write!(f, "Invalid vehicle section: {msg}"),
172            Self::InvalidCustomerRow(msg) => write!(f, "Invalid customer row: {msg}"),
173            Self::NoNodesFound => write!(f, "Instance does not contain any customer/depot nodes"),
174            Self::InvalidInstance(msg) => write!(f, "Invalid instance: {msg}"),
175        }
176    }
177}
178
179impl std::error::Error for SolomonParseError {}
180
181impl FromStr for SolomonInstance {
182    type Err = SolomonParseError;
183
184    fn from_str(s: &str) -> Result<Self, Self::Err> {
185        let mut name = None;
186        let mut num_vehicles = None;
187        let mut capacity = None;
188
189        let mut in_vehicle_section = false;
190        let mut in_customer_section = false;
191
192        let mut xs = Vec::new();
193        let mut ys = Vec::new();
194        let mut demands = Vec::new();
195        let mut ready_times = Vec::new();
196        let mut due_times = Vec::new();
197        let mut service_times = Vec::new();
198
199        for raw_line in s.lines() {
200            let line = raw_line.trim();
201            if line.is_empty() {
202                continue;
203            }
204
205            // The first non-empty line before sections is the instance name
206            if name.is_none()
207                && !line.eq_ignore_ascii_case("VEHICLE")
208                && !line.eq_ignore_ascii_case("CUSTOMER")
209            {
210                name = Some(line.to_string());
211                continue;
212            }
213
214            if line.eq_ignore_ascii_case("VEHICLE") {
215                in_vehicle_section = true;
216                in_customer_section = false;
217                continue;
218            }
219
220            if line.eq_ignore_ascii_case("CUSTOMER") {
221                in_vehicle_section = false;
222                in_customer_section = true;
223                continue;
224            }
225
226            if in_vehicle_section {
227                if line.contains("NUMBER") || line.contains("CAPACITY") {
228                    continue;
229                }
230                let tokens: Vec<&str> = line.split_whitespace().collect();
231                if tokens.len() >= 2 && num_vehicles.is_none() {
232                    num_vehicles = Some(tokens[0].parse::<usize>().map_err(|e| {
233                        SolomonParseError::InvalidVehicleSection(format!(
234                            "Invalid vehicle number: {e}"
235                        ))
236                    })?);
237                    capacity = Some(tokens[1].parse::<f32>().map_err(|e| {
238                        SolomonParseError::InvalidVehicleSection(format!("Invalid capacity: {e}"))
239                    })?);
240                }
241                continue;
242            }
243
244            if in_customer_section {
245                if line.contains("CUST") || line.contains("XCOORD") || line.contains("DEMAND") {
246                    continue;
247                }
248
249                let tokens: Vec<&str> = line.split_whitespace().collect();
250                if tokens.len() < 7 {
251                    return Err(SolomonParseError::InvalidCustomerRow(format!(
252                        "Expected 7 columns, found {}: '{}'",
253                        tokens.len(),
254                        line
255                    )));
256                }
257
258                let id = tokens[0].parse::<usize>().map_err(|e| {
259                    SolomonParseError::InvalidCustomerRow(format!("Invalid node ID: {e}"))
260                })?;
261                if id != xs.len() {
262                    return Err(SolomonParseError::InvalidCustomerRow(
263                        "Node IDs must be consecutive from depot 0, in row order".into(),
264                    ));
265                }
266
267                let x = tokens[1].parse::<f32>().map_err(|e| {
268                    SolomonParseError::InvalidCustomerRow(format!("Invalid X coordinate: {e}"))
269                })?;
270                let y = tokens[2].parse::<f32>().map_err(|e| {
271                    SolomonParseError::InvalidCustomerRow(format!("Invalid Y coordinate: {e}"))
272                })?;
273                let demand = tokens[3].parse::<f32>().map_err(|e| {
274                    SolomonParseError::InvalidCustomerRow(format!("Invalid Demand: {e}"))
275                })?;
276                let ready = tokens[4].parse::<f32>().map_err(|e| {
277                    SolomonParseError::InvalidCustomerRow(format!("Invalid Ready time: {e}"))
278                })?;
279                let due = tokens[5].parse::<f32>().map_err(|e| {
280                    SolomonParseError::InvalidCustomerRow(format!("Invalid Due time: {e}"))
281                })?;
282                let service = tokens[6].parse::<f32>().map_err(|e| {
283                    SolomonParseError::InvalidCustomerRow(format!("Invalid Service time: {e}"))
284                })?;
285
286                xs.push(x);
287                ys.push(y);
288                demands.push(demand);
289                ready_times.push(ready);
290                due_times.push(due);
291                service_times.push(service);
292            }
293        }
294
295        let name = name.ok_or(SolomonParseError::EmptyInput)?;
296        let num_vehicles = num_vehicles.ok_or_else(|| {
297            SolomonParseError::InvalidVehicleSection("Vehicle count not found".into())
298        })?;
299        let capacity = capacity.ok_or_else(|| {
300            SolomonParseError::InvalidVehicleSection("Vehicle capacity not found".into())
301        })?;
302
303        let num_nodes = xs.len();
304        if num_nodes == 0 {
305            return Err(SolomonParseError::NoNodesFound);
306        }
307
308        let distance_matrix = compute_distance_matrix(&xs, &ys);
309
310        let instance = Self {
311            name,
312            vehicle: VehicleConfig {
313                num_vehicles,
314                capacity,
315            },
316            num_nodes,
317            xs,
318            ys,
319            demands,
320            ready_times,
321            due_times,
322            service_times,
323            distance_matrix,
324        };
325        instance
326            .validate()
327            .map_err(|message| SolomonParseError::InvalidInstance(message.into()))?;
328        Ok(instance)
329    }
330}
331
332#[cfg(test)]
333mod tests {
334    use super::*;
335
336    #[test]
337    fn test_parser_rejects_invalid_ids_and_numeric_values() {
338        let prefix = "Test\nVEHICLE\n2 10\nCUSTOMER\n";
339        for row in [
340            "1 0 0 0 0 100 0",
341            "bad 0 0 0 0 100 0",
342            "0 NaN 0 0 0 100 0",
343            "0 inf 0 0 0 100 0",
344            "0 0 0 -1 0 100 0",
345            "0 0 0 1 0 100 0",
346            "0 0 0 0 100 0 0",
347            "0 0 0 0 0 100 -1",
348        ] {
349            assert!(
350                format!("{prefix}{row}").parse::<SolomonInstance>().is_err(),
351                "{row}"
352            );
353        }
354        for id in [0, 2] {
355            let input = format!("{prefix}0 0 0 0 0 100 0\n{id} 1 1 1 0 100 0");
356            assert!(input.parse::<SolomonInstance>().is_err());
357        }
358        for fleet in ["0 10", "1 0", "1 -1", "1 NaN", "1 inf"] {
359            let input = format!("Test\nVEHICLE\n{fleet}\nCUSTOMER\n0 0 0 0 0 100 0");
360            assert!(input.parse::<SolomonInstance>().is_err());
361        }
362    }
363
364    #[test]
365    fn test_validation_rejects_malformed_public_arrays() {
366        let input = "Test\nVEHICLE\n2 10\nCUSTOMER\n0 0 0 0 0 100 0\n1 1 0 1 0 100 0";
367        let original: SolomonInstance = input.parse().unwrap();
368        let mut instance = original.clone();
369        instance.demands.pop();
370        assert!(instance.validate().is_err());
371        instance = original.clone();
372        instance.distance_matrix.pop();
373        assert!(instance.validate().is_err());
374        for value in [f32::NAN, f32::INFINITY, -1.0, 2.0] {
375            instance = original.clone();
376            instance.distance_matrix[1] = value;
377            assert!(instance.validate().is_err());
378        }
379        instance = original;
380        instance.num_nodes = usize::MAX;
381        assert!(instance.validate().is_err());
382    }
383
384    #[test]
385    fn test_compute_distance_matrix_triangle() {
386        let xs = vec![0.0, 3.0, 0.0];
387        let ys = vec![0.0, 0.0, 4.0];
388        let matrix = compute_distance_matrix(&xs, &ys);
389
390        assert_eq!(matrix.len(), 9);
391
392        let dist = |i: usize, j: usize| matrix[i * 3 + j];
393
394        assert_eq!(dist(0, 0), 0.0);
395        assert_eq!(dist(1, 1), 0.0);
396        assert_eq!(dist(2, 2), 0.0);
397
398        assert_eq!(dist(0, 1), 3.0);
399        assert_eq!(dist(1, 0), 3.0);
400
401        assert_eq!(dist(0, 2), 4.0);
402        assert_eq!(dist(2, 0), 4.0);
403
404        assert_eq!(dist(1, 2), 5.0);
405        assert_eq!(dist(2, 1), 5.0);
406    }
407
408    #[test]
409    fn test_parse_solomon_c101_sample() {
410        let sample = r#"
411C101
412
413VEHICLE
414NUMBER     CAPACITY
415  25          200
416
417CUSTOMER
418CUST NO.  XCOORD.   YCOORD.    DEMAND   READY TIME  DUE DATE   SERVICE TIME
419    0       40.0      50.0       0.0        0.0     1236.0        0.0
420    1       45.0      68.0      10.0      912.0      967.0       90.0
421    2       45.0      70.0      30.0      825.0      870.0       90.0
422"#;
423
424        let instance: SolomonInstance = sample
425            .parse()
426            .expect("failed to parse valid Solomon string");
427
428        assert_eq!(instance.name, "C101");
429        assert_eq!(instance.vehicle.num_vehicles, 25);
430        assert_eq!(instance.vehicle.capacity, 200.0);
431        assert_eq!(instance.num_nodes, 3);
432
433        // Coordenadas SoA
434        assert_eq!(instance.xs, vec![40.0, 45.0, 45.0]);
435        assert_eq!(instance.ys, vec![50.0, 68.0, 70.0]);
436
437        // Demandas
438        assert_eq!(instance.demand(0), 0.0);
439        assert_eq!(instance.demand(1), 10.0);
440        assert_eq!(instance.demand(2), 30.0);
441
442        // Janelas e tempos
443        assert_eq!(instance.ready_times, vec![0.0, 912.0, 825.0]);
444        assert_eq!(instance.due_times, vec![1236.0, 967.0, 870.0]);
445        assert_eq!(instance.service_times, vec![0.0, 90.0, 90.0]);
446
447        // Distância 1 <-> 2: dx = 0, dy = 2 -> dist = 2.0
448        assert_eq!(instance.distance(1, 2), 2.0);
449        assert_eq!(instance.distance(2, 1), 2.0);
450
451        // Distância 0 <-> 1: dx = 5, dy = 18 -> sqrt(25 + 324) = sqrt(349)
452        let expected_dist_0_1 = (5.0f32 * 5.0 + 18.0 * 18.0).sqrt();
453        assert!((instance.distance(0, 1) - expected_dist_0_1).abs() < 1e-5);
454    }
455
456    #[test]
457    fn test_parse_solomon_empty_fails() {
458        let result: Result<SolomonInstance, _> = "".parse();
459        assert_eq!(result.unwrap_err(), SolomonParseError::EmptyInput);
460    }
461
462    #[test]
463    fn test_parse_solomon_missing_vehicle_fails() {
464        let sample = "C101\nCUSTOMER\nCUST NO. X Y DEMAND READY DUE SERVICE\n0 0 0 0 0 0 0";
465        let result: Result<SolomonInstance, _> = sample.parse();
466        assert!(matches!(
467            result.unwrap_err(),
468            SolomonParseError::InvalidVehicleSection(_)
469        ));
470    }
471
472    #[test]
473    fn test_parse_solomon_invalid_customer_row_fails() {
474        let sample = r#"
475C101
476VEHICLE
477NUMBER CAPACITY
47825 200
479CUSTOMER
480CUST NO. X Y DEMAND READY DUE SERVICE
4810 0 0
482"#;
483        let result: Result<SolomonInstance, _> = sample.parse();
484        assert!(matches!(
485            result.unwrap_err(),
486            SolomonParseError::InvalidCustomerRow(_)
487        ));
488    }
489}
vrp_gpu/instance.rs

vrp_gpu/
instance.rs
