solverforge_solver/heuristic/selector/k_opt/
selector.rs

1//! K-opt move selector for tour optimization.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::ScoreDirector;
8
9use crate::heuristic::r#move::k_opt_reconnection::KOptReconnection;
10use crate::heuristic::r#move::k_opt_reconnection::{
11    enumerate_reconnections, THREE_OPT_RECONNECTIONS,
12};
13use crate::heuristic::r#move::KOptMove;
14
15use super::super::entity::EntitySelector;
16use super::super::typed_move_selector::MoveSelector;
17use super::config::KOptConfig;
18use super::iterators::count_cut_combinations;
19use super::iterators::CutCombinationIterator;
20
21/// A move selector that generates k-opt moves.
22///
23/// Enumerates all valid cut point combinations for each selected entity
24/// and generates moves for each reconnection pattern.
25pub struct KOptMoveSelector<S, V, ES> {
26    /// Selects entities (routes) to apply k-opt to.
27    entity_selector: ES,
28    /// K-opt configuration.
29    config: KOptConfig,
30    /// Owned reconnection patterns (avoids `Box::leak` for non-k=3 cases).
31    owned_patterns: Vec<KOptReconnection>,
32    /// Get list length for an entity.
33    list_len: fn(&S, usize) -> usize,
34    /// Remove sublist [start, end).
35    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
36    /// Insert elements at position.
37    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
38    /// Variable name.
39    variable_name: &'static str,
40    /// Descriptor index.
41    descriptor_index: usize,
42    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
43}
44
45impl<S, V: Debug, ES: Debug> Debug for KOptMoveSelector<S, V, ES> {
46    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
47        f.debug_struct("KOptMoveSelector")
48            .field("entity_selector", &self.entity_selector)
49            .field("config", &self.config)
50            .field("pattern_count", &self.owned_patterns.len())
51            .field("variable_name", &self.variable_name)
52            .finish()
53    }
54}
55
56impl<S: PlanningSolution, V, ES> KOptMoveSelector<S, V, ES> {
57    /// Creates a new k-opt move selector.
58    #[allow(clippy::too_many_arguments)]
59    pub fn new(
60        entity_selector: ES,
61        config: KOptConfig,
62        list_len: fn(&S, usize) -> usize,
63        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
64        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
65        variable_name: &'static str,
66        descriptor_index: usize,
67    ) -> Self {
68        // For k=3, copy from the static table; for other k values, generate and own the patterns.
69        // This avoids Box::leak() which permanently leaks memory on every selector creation.
70        let owned_patterns: Vec<KOptReconnection> = if config.k == 3 {
71            THREE_OPT_RECONNECTIONS.to_vec()
72        } else {
73            enumerate_reconnections(config.k)
74        };
75
76        Self {
77            entity_selector,
78            config,
79            owned_patterns,
80            list_len,
81            sublist_remove,
82            sublist_insert,
83            variable_name,
84            descriptor_index,
85            _phantom: PhantomData,
86        }
87    }
88}
89
90impl<S, V, ES> MoveSelector<S, KOptMove<S, V>> for KOptMoveSelector<S, V, ES>
91where
92    S: PlanningSolution,
93    ES: EntitySelector<S>,
94    V: Clone + Send + Sync + Debug + 'static,
95{
96    fn iter_moves<'a, D: ScoreDirector<S>>(
97        &'a self,
98        score_director: &'a D,
99    ) -> impl Iterator<Item = KOptMove<S, V>> + 'a {
100        let k = self.config.k;
101        let min_seg = self.config.min_segment_len;
102        let patterns = &self.owned_patterns;
103        let list_len = self.list_len;
104        let sublist_remove = self.sublist_remove;
105        let sublist_insert = self.sublist_insert;
106        let variable_name = self.variable_name;
107        let descriptor_index = self.descriptor_index;
108
109        self.entity_selector
110            .iter(score_director)
111            .flat_map(move |entity_ref| {
112                let entity_idx = entity_ref.entity_index;
113                let solution = score_director.working_solution();
114                let len = list_len(solution, entity_idx);
115
116                // Generate all valid cut combinations
117                let cuts_iter = CutCombinationIterator::new(k, len, min_seg, entity_idx);
118
119                cuts_iter.flat_map(move |cuts| {
120                    // For each cut combination, generate moves for each pattern
121                    patterns.iter().map(move |pattern| {
122                        KOptMove::new(
123                            &cuts,
124                            pattern,
125                            list_len,
126                            sublist_remove,
127                            sublist_insert,
128                            variable_name,
129                            descriptor_index,
130                        )
131                    })
132                })
133            })
134    }
135
136    fn size<D: ScoreDirector<S>>(&self, score_director: &D) -> usize {
137        let k = self.config.k;
138        let min_seg = self.config.min_segment_len;
139        let pattern_count = self.owned_patterns.len();
140
141        self.entity_selector
142            .iter(score_director)
143            .map(|entity_ref| {
144                let solution = score_director.working_solution();
145                let len = (self.list_len)(solution, entity_ref.entity_index);
146                count_cut_combinations(k, len, min_seg) * pattern_count
147            })
148            .sum()
149    }
150}
solverforge_solver/heuristic/selector/k_opt/selector.rs

solverforge_solver/heuristic/selector/k_opt/
selector.rs
