solverforge_solver/heuristic/selector/
list_swap.rs

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

solverforge_solver/heuristic/selector/
list_swap.rs
