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::Director;
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    list_len: fn(&S, usize) -> usize,
33    // Remove sublist [start, end).
34    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
35    // Insert elements at position.
36    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
37    // Variable name.
38    variable_name: &'static str,
39    // Descriptor index.
40    descriptor_index: usize,
41    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
42}
43
44impl<S, V: Debug, ES: Debug> Debug for KOptMoveSelector<S, V, ES> {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        f.debug_struct("KOptMoveSelector")
47            .field("entity_selector", &self.entity_selector)
48            .field("config", &self.config)
49            .field("pattern_count", &self.owned_patterns.len())
50            .field("variable_name", &self.variable_name)
51            .finish()
52    }
53}
54
55impl<S: PlanningSolution, V, ES> KOptMoveSelector<S, V, ES> {
56    #[allow(clippy::too_many_arguments)]
57    pub fn new(
58        entity_selector: ES,
59        config: KOptConfig,
60        list_len: fn(&S, usize) -> usize,
61        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
62        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
63        variable_name: &'static str,
64        descriptor_index: usize,
65    ) -> Self {
66        // For k=3, copy from the static table; for other k values, generate and own the patterns.
67        // This avoids Box::leak() which permanently leaks memory on every selector creation.
68        let owned_patterns: Vec<KOptReconnection> = if config.k == 3 {
69            THREE_OPT_RECONNECTIONS.to_vec()
70        } else {
71            enumerate_reconnections(config.k)
72        };
73
74        Self {
75            entity_selector,
76            config,
77            owned_patterns,
78            list_len,
79            sublist_remove,
80            sublist_insert,
81            variable_name,
82            descriptor_index,
83            _phantom: PhantomData,
84        }
85    }
86}
87
88impl<S, V, ES> MoveSelector<S, KOptMove<S, V>> for KOptMoveSelector<S, V, ES>
89where
90    S: PlanningSolution,
91    ES: EntitySelector<S>,
92    V: Clone + Send + Sync + Debug + 'static,
93{
94    fn iter_moves<'a, D: Director<S>>(
95        &'a self,
96        score_director: &'a D,
97    ) -> impl Iterator<Item = KOptMove<S, V>> + 'a {
98        let k = self.config.k;
99        let min_seg = self.config.min_segment_len;
100        let patterns = &self.owned_patterns;
101        let list_len = self.list_len;
102        let sublist_remove = self.sublist_remove;
103        let sublist_insert = self.sublist_insert;
104        let variable_name = self.variable_name;
105        let descriptor_index = self.descriptor_index;
106
107        self.entity_selector
108            .iter(score_director)
109            .flat_map(move |entity_ref| {
110                let entity_idx = entity_ref.entity_index;
111                let solution = score_director.working_solution();
112                let len = list_len(solution, entity_idx);
113
114                // Generate all valid cut combinations
115                let cuts_iter = CutCombinationIterator::new(k, len, min_seg, entity_idx);
116
117                cuts_iter.flat_map(move |cuts| {
118                    // For each cut combination, generate moves for each pattern
119                    patterns.iter().map(move |pattern| {
120                        KOptMove::new(
121                            &cuts,
122                            pattern,
123                            list_len,
124                            sublist_remove,
125                            sublist_insert,
126                            variable_name,
127                            descriptor_index,
128                        )
129                    })
130                })
131            })
132    }
133
134    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
135        let k = self.config.k;
136        let min_seg = self.config.min_segment_len;
137        let pattern_count = self.owned_patterns.len();
138
139        self.entity_selector
140            .iter(score_director)
141            .map(|entity_ref| {
142                let solution = score_director.working_solution();
143                let len = (self.list_len)(solution, entity_ref.entity_index);
144                count_cut_combinations(k, len, min_seg) * pattern_count
145            })
146            .sum()
147    }
148}
solverforge_solver/heuristic/selector/k_opt/selector.rs

solverforge_solver/heuristic/selector/k_opt/
selector.rs
