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::move_selector::{ArenaMoveCursor, 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    list_get: fn(&S, usize, usize) -> Option<V>,
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    #[allow(clippy::too_many_arguments)]
58    pub fn new(
59        entity_selector: ES,
60        config: KOptConfig,
61        list_len: fn(&S, usize) -> usize,
62        list_get: fn(&S, usize, usize) -> Option<V>,
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            list_get,
82            sublist_remove,
83            sublist_insert,
84            variable_name,
85            descriptor_index,
86            _phantom: PhantomData,
87        }
88    }
89}
90
91impl<S, V, ES> MoveSelector<S, KOptMove<S, V>> for KOptMoveSelector<S, V, ES>
92where
93    S: PlanningSolution,
94    ES: EntitySelector<S>,
95    V: Clone + Send + Sync + Debug + 'static,
96{
97    type Cursor<'a>
98        = ArenaMoveCursor<S, KOptMove<S, V>>
99    where
100        Self: 'a;
101
102    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
103        let k = self.config.k;
104        let min_seg = self.config.min_segment_len;
105        let patterns = &self.owned_patterns;
106        let list_len = self.list_len;
107        let list_get = self.list_get;
108        let sublist_remove = self.sublist_remove;
109        let sublist_insert = self.sublist_insert;
110        let variable_name = self.variable_name;
111        let descriptor_index = self.descriptor_index;
112        let entity_lens: Vec<_> = self
113            .entity_selector
114            .iter(score_director)
115            .map(|entity_ref| {
116                let entity_idx = entity_ref.entity_index;
117                let len = list_len(score_director.working_solution(), entity_idx);
118                (entity_idx, len)
119            })
120            .collect();
121
122        ArenaMoveCursor::from_moves(entity_lens.into_iter().flat_map(move |(entity_idx, len)| {
123            let cuts_iter = CutCombinationIterator::new(k, len, min_seg, entity_idx);
124
125            cuts_iter.flat_map(move |cuts| {
126                patterns.iter().map(move |pattern| {
127                    KOptMove::new(
128                        &cuts,
129                        pattern,
130                        list_len,
131                        list_get,
132                        sublist_remove,
133                        sublist_insert,
134                        variable_name,
135                        descriptor_index,
136                    )
137                })
138            })
139        }))
140    }
141
142    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
143        let k = self.config.k;
144        let min_seg = self.config.min_segment_len;
145        let pattern_count = self.owned_patterns.len();
146
147        self.entity_selector
148            .iter(score_director)
149            .map(|entity_ref| {
150                let solution = score_director.working_solution();
151                let len = (self.list_len)(solution, entity_ref.entity_index);
152                count_cut_combinations(k, len, min_seg) * pattern_count
153            })
154            .sum()
155    }
156}
solverforge_solver/heuristic/selector/k_opt/selector.rs

solverforge_solver/heuristic/selector/k_opt/
selector.rs
