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 savings_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/// Depot token used by Clarke-Wright construction.
43pub fn savings_depot_for_entity<S: VrpSolution>(plan: &S, entity_idx: usize) -> usize {
44    depot_for_entity(plan, entity_idx)
45}
46
47/// Construction distance used by Clarke-Wright for models that share CVRP route data.
48pub fn savings_distance<S: VrpSolution>(
49    plan: &S,
50    entity_idx: usize,
51    from: usize,
52    to: usize,
53) -> i64 {
54    route_distance(plan, entity_idx, from, to)
55}
56
57/// Construction feasibility used by Clarke-Wright for models that share CVRP route data.
58pub fn savings_feasible<S: VrpSolution>(plan: &S, entity_idx: usize, route: &[usize]) -> bool {
59    route_feasible(plan, entity_idx, route)
60}
61
62/// Distance between two element indices for the route owner.
63pub fn route_distance<S: VrpSolution>(plan: &S, entity_idx: usize, from: usize, to: usize) -> i64 {
64    problem_data_for_entity(plan, entity_idx).map_or(0, |data| data.distance_matrix[from][to])
65}
66
67/// Replaces the current route for entity `entity_idx`.
68///
69/// Callers must pass a valid `entity_idx` for the current solution.
70pub fn replace_route<S: VrpSolution>(plan: &mut S, entity_idx: usize, route: Vec<usize>) {
71    *plan.vehicle_visits_mut(entity_idx) = route;
72}
73
74/// Returns a cloned snapshot of the route for entity `entity_idx`.
75///
76/// Callers must pass a valid `entity_idx` for the current solution.
77pub fn get_route<S: VrpSolution>(plan: &S, entity_idx: usize) -> Vec<usize> {
78    plan.vehicle_visits(entity_idx).to_vec()
79}
80
81/// Returns `true` if the route satisfies capacity and time-window constraints.
82pub fn route_feasible<S: VrpSolution>(plan: &S, entity_idx: usize, route: &[usize]) -> bool {
83    if route.is_empty() {
84        return true;
85    }
86    match problem_data_for_entity(plan, entity_idx) {
87        Some(data) => check_capacity_feasible(route, data) && check_time_feasible(route, data),
88        None => true,
89    }
90}
91
92/// Route-local hook bundle for `#[planning_list_variable(route_hooks = "...")]`.
93pub mod route_hooks {
94    pub use super::depot_for_entity as depot;
95    pub use super::get_route as get;
96    pub use super::replace_route as set;
97    pub use super::route_distance as distance;
98    pub use super::route_feasible as feasible;
99}
100
101/// Clarke-Wright savings hook bundle for `#[planning_list_variable(savings_hooks = "...")]`.
102///
103/// Use this only when construction should share the same CVRP data as exact
104/// route-local behavior.
105pub mod savings_hooks {
106    pub use super::savings_depot_for_entity as depot;
107    pub use super::savings_distance as distance;
108    pub use super::savings_feasible as feasible;
109}
110
111fn check_capacity_feasible(route: &[usize], data: &ProblemData) -> bool {
112    route
113        .iter()
114        .map(|&visit| data.demands[visit] as i64)
115        .sum::<i64>()
116        <= data.capacity
117}
118
119fn check_time_feasible(route: &[usize], data: &ProblemData) -> bool {
120    let mut current_time = data.vehicle_departure_time;
121    let mut prev = data.depot;
122
123    for &visit in route {
124        current_time += data.travel_times[prev][visit];
125
126        let (min_start, max_end) = data.time_windows[visit];
127
128        if current_time < min_start {
129            current_time = min_start;
130        }
131
132        let service_end = current_time + data.service_durations[visit];
133
134        if service_end > max_end {
135            return false;
136        }
137
138        current_time = service_end;
139        prev = visit;
140    }
141
142    true
143}
solverforge_cvrp/helpers.rs

solverforge_cvrp/
helpers.rs
