solverforge_cvrp/
lib.rs

1//! CVRP domain helpers for SolverForge.
2//!
3//! Provides `ProblemData`, `MatrixDistanceMeter`, `MatrixIntraDistanceMeter`,
4//! the `VrpSolution` trait, and a suite of free functions for Clarke-Wright
5//! and k-opt construction phases.
6
7use solverforge_solver::CrossEntityDistanceMeter;
8
9// ============================================================================
10// Problem data
11// ============================================================================
12
13/// Immutable problem data shared by all vehicles.
14///
15/// Stored via raw pointer in each vehicle so the framework can clone vehicles
16/// freely during local search without copying matrices.
17pub struct ProblemData {
18    pub capacity: i64,
19    pub depot: usize,
20    pub demands: Vec<i32>,
21    pub distance_matrix: Vec<Vec<i64>>,
22    pub time_windows: Vec<(i64, i64)>,
23    pub service_durations: Vec<i64>,
24    pub travel_times: Vec<Vec<i64>>,
25    pub vehicle_departure_time: i64,
26}
27
28// ============================================================================
29// VrpSolution trait
30// ============================================================================
31
32/// Trait implemented by a planning solution that holds a fleet of vehicles,
33/// each carrying a `*const ProblemData` pointer and a list of visited stops.
34///
35/// # Safety
36/// Implementors must ensure every `vehicle_data_ptr` points to a valid
37/// `ProblemData` for the entire duration of a solve call.
38pub trait VrpSolution {
39    fn vehicle_data_ptr(&self, entity_idx: usize) -> *const ProblemData;
40    fn vehicle_visits(&self, entity_idx: usize) -> &[usize];
41    fn vehicle_visits_mut(&mut self, entity_idx: usize) -> &mut Vec<usize>;
42    fn vehicle_count(&self) -> usize;
43}
44
45// ============================================================================
46// Free functions (callable as fn-pointer fields in ListSpec)
47// ============================================================================
48
49/// Distance between two element indices using the first vehicle's data pointer.
50pub fn distance<S: VrpSolution>(plan: &S, i: usize, j: usize) -> i64 {
51    if plan.vehicle_count() == 0 {
52        return 0;
53    }
54    // SAFETY: pointer is valid for the lifetime of solve (guaranteed by VrpSolution contract)
55    let data = unsafe { &*plan.vehicle_data_ptr(0) };
56    data.distance_matrix[i][j]
57}
58
59/// Returns the depot index (same for all vehicles).
60pub fn depot_for_entity<S: VrpSolution>(plan: &S, _entity_idx: usize) -> usize {
61    if plan.vehicle_count() == 0 {
62        return 0;
63    }
64    // SAFETY: see distance()
65    let data = unsafe { &*plan.vehicle_data_ptr(0) };
66    data.depot
67}
68
69/// Returns the depot index for Clarke-Wright (plan-level, not per-entity).
70pub fn depot_for_cw<S: VrpSolution>(plan: &S) -> usize {
71    if plan.vehicle_count() == 0 {
72        return 0;
73    }
74    // SAFETY: see distance()
75    let data = unsafe { &*plan.vehicle_data_ptr(0) };
76    data.depot
77}
78
79/// Returns the demand (load) for a single customer element.
80pub fn element_load<S: VrpSolution>(plan: &S, elem: usize) -> i64 {
81    if plan.vehicle_count() == 0 {
82        return 0;
83    }
84    // SAFETY: see distance()
85    let data = unsafe { &*plan.vehicle_data_ptr(0) };
86    data.demands[elem] as i64
87}
88
89/// Returns the vehicle capacity.
90pub fn capacity<S: VrpSolution>(plan: &S) -> i64 {
91    if plan.vehicle_count() == 0 {
92        return i64::MAX;
93    }
94    // SAFETY: see distance()
95    let data = unsafe { &*plan.vehicle_data_ptr(0) };
96    data.capacity
97}
98
99/// Assigns a constructed route to the given vehicle.
100pub fn assign_route<S: VrpSolution>(plan: &mut S, entity_idx: usize, route: Vec<usize>) {
101    *plan.vehicle_visits_mut(entity_idx) = route;
102}
103
104/// Returns the current route for entity `entity_idx`.
105pub fn get_route<S: VrpSolution>(plan: &S, entity_idx: usize) -> Vec<usize> {
106    plan.vehicle_visits(entity_idx).to_vec()
107}
108
109/// Replaces the current route for entity `entity_idx`.
110pub fn set_route<S: VrpSolution>(plan: &mut S, entity_idx: usize, route: Vec<usize>) {
111    *plan.vehicle_visits_mut(entity_idx) = route;
112}
113
114/// Returns `true` if the route satisfies all time-window constraints.
115pub fn is_time_feasible<S: VrpSolution>(plan: &S, route: &[usize]) -> bool {
116    if route.is_empty() || plan.vehicle_count() == 0 {
117        return true;
118    }
119    // SAFETY: see distance()
120    let data = unsafe { &*plan.vehicle_data_ptr(0) };
121    check_time_feasible(route, data)
122}
123
124/// K-opt feasibility gate: returns `true` if the route satisfies all time-window constraints.
125/// The `entity_idx` parameter is ignored — time windows are uniform across vehicles.
126pub fn is_kopt_feasible<S: VrpSolution>(plan: &S, _entity_idx: usize, route: &[usize]) -> bool {
127    is_time_feasible(plan, route)
128}
129
130fn check_time_feasible(route: &[usize], data: &ProblemData) -> bool {
131    let mut current_time = data.vehicle_departure_time;
132    let mut prev = data.depot;
133
134    for &visit in route {
135        current_time += data.travel_times[prev][visit];
136
137        let (min_start, max_end) = data.time_windows[visit];
138
139        if current_time < min_start {
140            current_time = min_start;
141        }
142
143        let service_end = current_time + data.service_durations[visit];
144
145        if service_end > max_end {
146            return false;
147        }
148
149        current_time = service_end;
150        prev = visit;
151    }
152
153    true
154}
155
156// ============================================================================
157// Distance meters
158// ============================================================================
159
160/// Cross-entity distance meter backed by the solution's distance matrix.
161#[derive(Clone, Default)]
162pub struct MatrixDistanceMeter;
163
164impl<S: VrpSolution> CrossEntityDistanceMeter<S> for MatrixDistanceMeter {
165    fn distance(
166        &self,
167        solution: &S,
168        src_entity: usize,
169        src_pos: usize,
170        dst_entity: usize,
171        dst_pos: usize,
172    ) -> f64 {
173        let src_visits = solution.vehicle_visits(src_entity);
174        let dst_visits = solution.vehicle_visits(dst_entity);
175        if src_pos >= src_visits.len() || dst_pos >= dst_visits.len() {
176            return f64::INFINITY;
177        }
178        // SAFETY: see distance()
179        let data = unsafe { &*solution.vehicle_data_ptr(src_entity) };
180        data.distance_matrix[src_visits[src_pos]][dst_visits[dst_pos]] as f64
181    }
182}
183
184/// Intra-entity distance meter backed by the solution's distance matrix.
185#[derive(Clone, Default)]
186pub struct MatrixIntraDistanceMeter;
187
188impl<S: VrpSolution> CrossEntityDistanceMeter<S> for MatrixIntraDistanceMeter {
189    fn distance(
190        &self,
191        solution: &S,
192        src_entity: usize,
193        src_pos: usize,
194        _dst_entity: usize,
195        dst_pos: usize,
196    ) -> f64 {
197        let visits = solution.vehicle_visits(src_entity);
198        if src_pos >= visits.len() || dst_pos >= visits.len() {
199            return f64::INFINITY;
200        }
201        // SAFETY: see distance()
202        let data = unsafe { &*solution.vehicle_data_ptr(src_entity) };
203        data.distance_matrix[visits[src_pos]][visits[dst_pos]] as f64
204    }
205}
solverforge_cvrp/lib.rs

solverforge_cvrp/
lib.rs
