solverforge_cvrp/
helpers.rs

1use crate::{ProblemData, VrpSolution};
2
3#[inline]
4pub(crate) fn problem_data_for_entity<S: VrpSolution>(
5    plan: &S,
6    entity_idx: usize,
7) -> Option<&ProblemData> {
8    if entity_idx >= plan.vehicle_count() {
9        return None;
10    }
11    let ptr = plan.vehicle_data_ptr(entity_idx);
12    assert!(
13        !ptr.is_null(),
14        "VrpSolution::vehicle_data_ptr({entity_idx}) returned null for a non-empty fleet"
15    );
16    // SAFETY: VrpSolution implementors guarantee valid pointers for the duration
17    // of the solve call; null for a non-empty fleet is rejected above.
18    unsafe { ptr.as_ref() }
19}
20
21pub fn depot_for_entity<S: VrpSolution>(plan: &S, entity_idx: usize) -> usize {
22    problem_data_for_entity(plan, entity_idx).map_or(0, |data| data.depot)
23}
24
25/// Construction metric class for the route owner.
26///
27/// Owners that share the same `ProblemData` pointer share depot and distance
28/// behavior, so Clarke-Wright can compute their savings rows once.
29pub fn route_metric_class<S: VrpSolution>(plan: &S, entity_idx: usize) -> usize {
30    if entity_idx >= plan.vehicle_count() {
31        return entity_idx;
32    }
33
34    let ptr = plan.vehicle_data_ptr(entity_idx);
35    assert!(
36        !ptr.is_null(),
37        "VrpSolution::vehicle_data_ptr({entity_idx}) returned null for a non-empty fleet"
38    );
39    ptr as usize
40}
41
42/// Distance between two element indices for the route owner.
43pub fn route_distance<S: VrpSolution>(plan: &S, entity_idx: usize, from: usize, to: usize) -> i64 {
44    problem_data_for_entity(plan, entity_idx).map_or(0, |data| data.distance_matrix[from][to])
45}
46
47/// Replaces the current route for entity `entity_idx`.
48///
49/// Callers must pass a valid `entity_idx` for the current solution.
50pub fn replace_route<S: VrpSolution>(plan: &mut S, entity_idx: usize, route: Vec<usize>) {
51    *plan.vehicle_visits_mut(entity_idx) = route;
52}
53
54/// Returns a cloned snapshot of the route for entity `entity_idx`.
55///
56/// Callers must pass a valid `entity_idx` for the current solution.
57pub fn get_route<S: VrpSolution>(plan: &S, entity_idx: usize) -> Vec<usize> {
58    plan.vehicle_visits(entity_idx).to_vec()
59}
60
61/// Returns `true` if the route satisfies capacity and time-window constraints.
62pub fn route_feasible<S: VrpSolution>(plan: &S, entity_idx: usize, route: &[usize]) -> bool {
63    if route.is_empty() {
64        return true;
65    }
66    match problem_data_for_entity(plan, entity_idx) {
67        Some(data) => check_capacity_feasible(route, data) && check_time_feasible(route, data),
68        None => true,
69    }
70}
71
72fn check_capacity_feasible(route: &[usize], data: &ProblemData) -> bool {
73    route
74        .iter()
75        .map(|&visit| data.demands[visit] as i64)
76        .sum::<i64>()
77        <= data.capacity
78}
79
80fn check_time_feasible(route: &[usize], data: &ProblemData) -> bool {
81    let mut current_time = data.vehicle_departure_time;
82    let mut prev = data.depot;
83
84    for &visit in route {
85        current_time += data.travel_times[prev][visit];
86
87        let (min_start, max_end) = data.time_windows[visit];
88
89        if current_time < min_start {
90            current_time = min_start;
91        }
92
93        let service_end = current_time + data.service_durations[visit];
94
95        if service_end > max_end {
96            return false;
97        }
98
99        current_time = service_end;
100        prev = visit;
101    }
102
103    true
104}
solverforge_cvrp/helpers.rs

solverforge_cvrp/
helpers.rs
