solverforge_solver/heuristic/selector/
list_swap.rs

1/* List swap move selector for element exchange.
2
3Generates `ListSwapMove`s that swap elements within or between list variables.
4Useful for inter-route rebalancing in vehicle routing problems.
5
6# Complexity
7
8For n entities with average route length m:
9- Intra-entity swaps: O(n * m * (m-1) / 2)
10- Inter-entity swaps: O(n² * m²)
11- Total: O(n² * m²) worst case (triangular optimization halves constant)
12
13# Example
14
15```
16use solverforge_solver::heuristic::selector::list_swap::ListSwapMoveSelector;
17use solverforge_solver::heuristic::selector::entity::FromSolutionEntitySelector;
18use solverforge_solver::heuristic::selector::MoveSelector;
19use solverforge_core::domain::PlanningSolution;
20use solverforge_core::score::SoftScore;
21
22#[derive(Clone, Debug)]
23struct Vehicle { visits: Vec<i32> }
24
25#[derive(Clone, Debug)]
26struct Solution { vehicles: Vec<Vehicle>, score: Option<SoftScore> }
27
28impl PlanningSolution for Solution {
29type Score = SoftScore;
30fn score(&self) -> Option<Self::Score> { self.score }
31fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
32}
33
34fn list_len(s: &Solution, entity_idx: usize) -> usize {
35s.vehicles.get(entity_idx).map_or(0, |v| v.visits.len())
36}
37fn list_get(s: &Solution, entity_idx: usize, pos: usize) -> Option<i32> {
38s.vehicles.get(entity_idx).and_then(|v| v.visits.get(pos).copied())
39}
40fn list_set(s: &mut Solution, entity_idx: usize, pos: usize, val: i32) {
41if let Some(v) = s.vehicles.get_mut(entity_idx) {
42if let Some(elem) = v.visits.get_mut(pos) { *elem = val; }
43}
44}
45
46let selector = ListSwapMoveSelector::<Solution, i32, _>::new(
47FromSolutionEntitySelector::new(0),
48list_len,
49list_get,
50list_set,
51"visits",
520,
53);
54```
55*/
56
57use std::fmt::Debug;
58use std::marker::PhantomData;
59
60use solverforge_core::domain::PlanningSolution;
61use solverforge_scoring::Director;
62
63use crate::heuristic::r#move::{ListMoveImpl, ListSwapMove};
64
65use super::entity::EntitySelector;
66use super::typed_move_selector::MoveSelector;
67
68/// A move selector that generates list swap moves.
69///
70/// Enumerates all valid (entity_a, pos_a, entity_b, pos_b) pairs for swapping
71/// elements within or between list variables. Intra-entity swaps use a
72/// triangular iteration to avoid duplicate pairs.
73///
74/// # Type Parameters
75/// * `S` - The solution type
76/// * `V` - The list element type
77/// * `ES` - The entity selector type
78pub struct ListSwapMoveSelector<S, V, ES> {
79    entity_selector: ES,
80    list_len: fn(&S, usize) -> usize,
81    list_get: fn(&S, usize, usize) -> Option<V>,
82    list_set: fn(&mut S, usize, usize, V),
83    variable_name: &'static str,
84    descriptor_index: usize,
85    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
86}
87
88impl<S, V: Debug, ES: Debug> Debug for ListSwapMoveSelector<S, V, ES> {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        f.debug_struct("ListSwapMoveSelector")
91            .field("entity_selector", &self.entity_selector)
92            .field("variable_name", &self.variable_name)
93            .field("descriptor_index", &self.descriptor_index)
94            .finish()
95    }
96}
97
98impl<S, V, ES> ListSwapMoveSelector<S, V, ES> {
99    /// Creates a new list swap move selector.
100    ///
101    /// # Arguments
102    /// * `entity_selector` - Selects entities to consider for swaps
103    /// * `list_len` - Function to get list length for an entity
104    /// * `list_get` - Function to get element at position
105    /// * `list_set` - Function to set element at position
106    /// * `variable_name` - Name of the list variable
107    /// * `descriptor_index` - Entity descriptor index
108    pub fn new(
109        entity_selector: ES,
110        list_len: fn(&S, usize) -> usize,
111        list_get: fn(&S, usize, usize) -> Option<V>,
112        list_set: fn(&mut S, usize, usize, V),
113        variable_name: &'static str,
114        descriptor_index: usize,
115    ) -> Self {
116        Self {
117            entity_selector,
118            list_len,
119            list_get,
120            list_set,
121            variable_name,
122            descriptor_index,
123            _phantom: PhantomData,
124        }
125    }
126}
127
128impl<S, V, ES> MoveSelector<S, ListSwapMove<S, V>> for ListSwapMoveSelector<S, V, ES>
129where
130    S: PlanningSolution,
131    V: Clone + PartialEq + Send + Sync + Debug + 'static,
132    ES: EntitySelector<S>,
133{
134    fn iter_moves<'a, D: Director<S>>(
135        &'a self,
136        score_director: &'a D,
137    ) -> impl Iterator<Item = ListSwapMove<S, V>> + 'a {
138        let solution = score_director.working_solution();
139        let list_len = self.list_len;
140        let list_get = self.list_get;
141        let list_set = self.list_set;
142        let variable_name = self.variable_name;
143        let descriptor_index = self.descriptor_index;
144
145        let entities: Vec<usize> = self
146            .entity_selector
147            .iter(score_director)
148            .map(|r| r.entity_index)
149            .collect();
150
151        let route_lens: Vec<usize> = entities.iter().map(|&e| list_len(solution, e)).collect();
152
153        let mut moves = Vec::new();
154
155        for (i, &entity_a) in entities.iter().enumerate() {
156            let len_a = route_lens[i];
157            if len_a == 0 {
158                continue;
159            }
160
161            // Intra-entity swaps: triangular pairs (pos_a, pos_b) with pos_a < pos_b
162            for pos_a in 0..len_a {
163                for pos_b in pos_a + 1..len_a {
164                    moves.push(ListSwapMove::new(
165                        entity_a,
166                        pos_a,
167                        entity_a,
168                        pos_b,
169                        list_len,
170                        list_get,
171                        list_set,
172                        variable_name,
173                        descriptor_index,
174                    ));
175                }
176            }
177
178            // Inter-entity swaps: all pairs (entity_a, pos_a) x (entity_b, pos_b) where b > a
179            for (j, &entity_b) in entities.iter().enumerate() {
180                if j <= i {
181                    continue;
182                }
183                let len_b = route_lens[j];
184                if len_b == 0 {
185                    continue;
186                }
187
188                for pos_a in 0..len_a {
189                    for pos_b in 0..len_b {
190                        moves.push(ListSwapMove::new(
191                            entity_a,
192                            pos_a,
193                            entity_b,
194                            pos_b,
195                            list_len,
196                            list_get,
197                            list_set,
198                            variable_name,
199                            descriptor_index,
200                        ));
201                    }
202                }
203            }
204        }
205
206        moves.into_iter()
207    }
208
209    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
210        let solution = score_director.working_solution();
211        let list_len = self.list_len;
212
213        let entities: Vec<usize> = self
214            .entity_selector
215            .iter(score_director)
216            .map(|r| r.entity_index)
217            .collect();
218
219        let route_lens: Vec<usize> = entities.iter().map(|&e| list_len(solution, e)).collect();
220        let n = entities.len();
221        if n == 0 {
222            return 0;
223        }
224
225        // Intra: sum of m*(m-1)/2 per entity
226        // Inter: sum over pairs of m_a * m_b
227        let intra: usize = route_lens
228            .iter()
229            .map(|&m| m * m.saturating_sub(1) / 2)
230            .sum();
231        let inter: usize = (0..n)
232            .flat_map(|i| (i + 1..n).map(move |j| (i, j)))
233            .map(|(i, j)| route_lens[i] * route_lens[j])
234            .sum();
235        intra + inter
236    }
237}
238
239/// Wraps a `ListSwapMoveSelector` to yield `ListMoveImpl::ListSwap`.
240pub struct ListMoveListSwapSelector<S, V, ES> {
241    inner: ListSwapMoveSelector<S, V, ES>,
242}
243
244impl<S, V: Debug, ES: Debug> Debug for ListMoveListSwapSelector<S, V, ES> {
245    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
246        f.debug_struct("ListMoveListSwapSelector")
247            .field("inner", &self.inner)
248            .finish()
249    }
250}
251
252impl<S, V, ES> ListMoveListSwapSelector<S, V, ES> {
253    /// Wraps an existing [`ListSwapMoveSelector`].
254    pub fn new(inner: ListSwapMoveSelector<S, V, ES>) -> Self {
255        Self { inner }
256    }
257}
258
259impl<S, V, ES> MoveSelector<S, ListMoveImpl<S, V>> for ListMoveListSwapSelector<S, V, ES>
260where
261    S: PlanningSolution,
262    V: Clone + PartialEq + Send + Sync + Debug + 'static,
263    ES: EntitySelector<S>,
264{
265    fn iter_moves<'a, D: Director<S>>(
266        &'a self,
267        score_director: &'a D,
268    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
269        self.inner
270            .iter_moves(score_director)
271            .map(ListMoveImpl::ListSwap)
272    }
273
274    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
275        self.inner.size(score_director)
276    }
277}
solverforge_solver/heuristic/selector/list_swap.rs

solverforge_solver/heuristic/selector/
list_swap.rs
