solverforge_solver/manager/phase_factory/
k_opt.rs

1/* K-opt phase builder for tour optimization.
2
3Creates a local search phase that uses k-opt moves to improve solutions.
4This is commonly used for vehicle routing and traveling salesman problems.
5*/
6
7use std::fmt::Debug;
8use std::marker::PhantomData;
9
10use solverforge_core::domain::PlanningSolution;
11use solverforge_scoring::{Director, RecordingDirector};
12
13use crate::heuristic::r#move::MoveArena;
14use crate::heuristic::selector::k_opt::{KOptConfig, KOptMoveSelector};
15use crate::phase::control::{
16    append_interruptibly, settle_search_interrupt, should_interrupt_evaluation, StepInterrupt,
17};
18use crate::phase::Phase;
19use crate::scope::{PhaseScope, SolverScope, StepScope};
20
21use super::super::PhaseFactory;
22
23/// Builder for creating k-opt local search phases.
24///
25/// # Type Parameters
26///
27/// * `S` - The planning solution type
28/// * `V` - The list element value type (e.g., `usize` for visit indices)
29/// * `DM` - The distance meter type (for nearby selection, stored for future use)
30/// * `ESF` - Entity selector factory type (for nearby selection, stored for future use)
31///
32/// # Example
33///
34/// ```
35/// use solverforge_solver::KOptPhaseBuilder;
36/// use solverforge_solver::heuristic::selector::{DefaultDistanceMeter, FromSolutionEntitySelector};
37/// use solverforge_core::domain::PlanningSolution;
38/// use solverforge_core::score::SoftScore;
39///
40/// #[derive(Clone, Debug)]
41/// struct Vehicle { visits: Vec<usize> }
42///
43/// #[derive(Clone, Debug)]
44/// struct Plan {
45///     vehicles: Vec<Vehicle>,
46///     score: Option<SoftScore>,
47/// }
48///
49/// impl PlanningSolution for Plan {
50///     type Score = SoftScore;
51///     fn score(&self) -> Option<Self::Score> { self.score }
52///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
53/// }
54///
55/// fn list_len(s: &Plan, idx: usize) -> usize {
56///     s.vehicles.get(idx).map_or(0, |v| v.visits.len())
57/// }
58///
59/// fn sublist_remove(s: &mut Plan, idx: usize, start: usize, end: usize) -> Vec<usize> {
60///     s.vehicles.get_mut(idx)
61///         .map(|v| v.visits.drain(start..end).collect())
62///         .unwrap_or_default()
63/// }
64///
65/// fn sublist_insert(s: &mut Plan, idx: usize, pos: usize, items: Vec<usize>) {
66///     if let Some(v) = s.vehicles.get_mut(idx) {
67///         for (i, item) in items.into_iter().enumerate() {
68///             v.visits.insert(pos + i, item);
69///         }
70///     }
71/// }
72///
73/// let builder = KOptPhaseBuilder::<Plan, usize, _, _>::new(
74///     DefaultDistanceMeter,
75///     || FromSolutionEntitySelector::new(0),
76///     list_len,
77///     |s, idx, pos| s.vehicles.get(idx).and_then(|v| v.visits.get(pos)).copied(),
78///     sublist_remove,
79///     sublist_insert,
80///     "visits",
81///     0,
82/// );
83/// ```
84pub struct KOptPhaseBuilder<S, V, DM, ESF>
85where
86    S: PlanningSolution,
87    V: Clone + Send + Sync + Debug + 'static,
88{
89    list_len: fn(&S, usize) -> usize,
90    list_get: fn(&S, usize, usize) -> Option<V>,
91    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
92    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
93    variable_name: &'static str,
94    descriptor_index: usize,
95    k: usize,
96    step_limit: Option<u64>,
97    _marker: PhantomData<(fn() -> S, fn() -> V, fn() -> DM, fn() -> ESF)>,
98}
99
100impl<S, V, DM, ESF> KOptPhaseBuilder<S, V, DM, ESF>
101where
102    S: PlanningSolution,
103    V: Clone + Send + Sync + Debug + 'static,
104{
105    /// Creates a new k-opt phase builder.
106    ///
107    /// The `distance_meter` and `entity_selector_factory` parameters are accepted
108    /// for API compatibility but not currently used (reserved for nearby selection).
109    #[allow(clippy::too_many_arguments)]
110    pub fn new(
111        _distance_meter: DM,
112        _entity_selector_factory: ESF,
113        list_len: fn(&S, usize) -> usize,
114        list_get: fn(&S, usize, usize) -> Option<V>,
115        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
116        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
117        variable_name: &'static str,
118        descriptor_index: usize,
119    ) -> Self {
120        Self {
121            list_len,
122            list_get,
123            sublist_remove,
124            sublist_insert,
125            variable_name,
126            descriptor_index,
127            k: 3, // Default to 3-opt
128            step_limit: Some(1000),
129            _marker: PhantomData,
130        }
131    }
132
133    pub fn with_k(mut self, k: usize) -> Self {
134        assert!((2..=5).contains(&k), "k must be between 2 and 5");
135        self.k = k;
136        self
137    }
138
139    pub fn with_step_limit(mut self, limit: u64) -> Self {
140        self.step_limit = Some(limit);
141        self
142    }
143
144    /// Removes the step limit.
145    pub fn without_step_limit(mut self) -> Self {
146        self.step_limit = None;
147        self
148    }
149}
150
151impl<S, V, DM, ESF> Debug for KOptPhaseBuilder<S, V, DM, ESF>
152where
153    S: PlanningSolution,
154    V: Clone + Send + Sync + Debug + 'static,
155{
156    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
157        f.debug_struct("KOptPhaseBuilder")
158            .field("k", &self.k)
159            .field("variable_name", &self.variable_name)
160            .field("descriptor_index", &self.descriptor_index)
161            .field("step_limit", &self.step_limit)
162            .finish()
163    }
164}
165
166/// K-opt local search phase.
167///
168/// Iterates through k-opt moves and accepts improving ones using hill climbing.
169pub struct KOptPhase<S, V>
170where
171    S: PlanningSolution,
172    V: Clone + Send + Sync + Debug + 'static,
173{
174    config: KOptConfig,
175    list_len: fn(&S, usize) -> usize,
176    list_get: fn(&S, usize, usize) -> Option<V>,
177    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
178    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
179    variable_name: &'static str,
180    descriptor_index: usize,
181    step_limit: Option<u64>,
182    _marker: PhantomData<(fn() -> S, fn() -> V)>,
183}
184
185impl<S, V> Debug for KOptPhase<S, V>
186where
187    S: PlanningSolution,
188    V: Clone + Send + Sync + Debug + 'static,
189{
190    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
191        f.debug_struct("KOptPhase")
192            .field("k", &self.config.k)
193            .field("variable_name", &self.variable_name)
194            .finish()
195    }
196}
197
198impl<S, V, D> Phase<S, D> for KOptPhase<S, V>
199where
200    S: PlanningSolution,
201    V: Clone + Send + Sync + Debug + 'static,
202    D: Director<S>,
203{
204    fn solve(&mut self, solver_scope: &mut SolverScope<S, D>) {
205        use crate::heuristic::r#move::Move;
206        use crate::heuristic::selector::entity::FromSolutionEntitySelector;
207        use crate::heuristic::selector::move_selector::MoveSelector;
208
209        let mut phase_scope = PhaseScope::new(solver_scope, 0);
210
211        // Calculate initial score
212        let mut last_step_score = phase_scope.calculate_score();
213
214        // Create move selector
215        let entity_selector = FromSolutionEntitySelector::new(self.descriptor_index);
216        let move_selector = KOptMoveSelector::<S, V, _>::new(
217            entity_selector,
218            self.config.clone(),
219            self.list_len,
220            self.list_get,
221            self.sublist_remove,
222            self.sublist_insert,
223            self.variable_name,
224            self.descriptor_index,
225        );
226
227        let step_limit = self.step_limit.unwrap_or(u64::MAX);
228        let mut steps = 0u64;
229        let mut arena = MoveArena::new();
230
231        while steps < step_limit && !phase_scope.solver_scope_mut().should_terminate() {
232            let mut step_scope = StepScope::new(&mut phase_scope);
233
234            arena.reset();
235            let generation_interrupted = {
236                let iter = move_selector.iter_moves(step_scope.score_director());
237                append_interruptibly(&step_scope, &mut arena, iter)
238            };
239            if generation_interrupted {
240                match settle_search_interrupt(&mut step_scope) {
241                    StepInterrupt::Restart => continue,
242                    StepInterrupt::TerminatePhase => break,
243                }
244            }
245
246            let mut best_move_idx = None;
247            let mut best_score = None;
248            let mut interrupted_step = false;
249
250            // Evaluate all moves
251            for idx in 0..arena.len() {
252                if should_interrupt_evaluation(&step_scope, idx) {
253                    interrupted_step = true;
254                    break;
255                }
256
257                let mv = arena.get(idx).unwrap();
258                if !mv.is_doable(step_scope.score_director()) {
259                    continue;
260                }
261
262                // Use RecordingDirector for automatic undo
263                {
264                    let mut recording = RecordingDirector::new(step_scope.score_director_mut());
265                    mv.do_move(&mut recording);
266                    let move_score = recording.calculate_score();
267
268                    // Accept if improving over last step
269                    if move_score > last_step_score
270                        && best_score.as_ref().is_none_or(|b| move_score > *b)
271                    {
272                        best_score = Some(move_score);
273                        best_move_idx = Some(idx);
274                    }
275
276                    // Undo the move
277                    recording.undo_changes();
278                }
279            }
280
281            if interrupted_step {
282                match settle_search_interrupt(&mut step_scope) {
283                    StepInterrupt::Restart => continue,
284                    StepInterrupt::TerminatePhase => break,
285                }
286            }
287
288            // Apply best move if found
289            if let (Some(idx), Some(score)) = (best_move_idx, best_score) {
290                let selected_move = arena.take(idx);
291                step_scope.apply_committed_move(&selected_move);
292                step_scope.set_step_score(score);
293                last_step_score = score;
294                step_scope.phase_scope_mut().update_best_solution();
295            } else {
296                // No improving moves found - phase is done
297                break;
298            }
299
300            step_scope.complete();
301            steps += 1;
302        }
303
304        // Ensure we have a best solution
305        if phase_scope.solver_scope().best_solution().is_none() {
306            phase_scope.update_best_solution();
307        }
308    }
309
310    fn phase_type_name(&self) -> &'static str {
311        "KOpt"
312    }
313}
314
315impl<S, V, DM, ESF, D> PhaseFactory<S, D> for KOptPhaseBuilder<S, V, DM, ESF>
316where
317    S: PlanningSolution,
318    V: Clone + Send + Sync + Debug + 'static,
319    DM: Send + Sync,
320    ESF: Send + Sync,
321    D: Director<S>,
322{
323    type Phase = KOptPhase<S, V>;
324
325    fn create(&self) -> Self::Phase {
326        KOptPhase {
327            config: KOptConfig::new(self.k),
328            list_len: self.list_len,
329            list_get: self.list_get,
330            sublist_remove: self.sublist_remove,
331            sublist_insert: self.sublist_insert,
332            variable_name: self.variable_name,
333            descriptor_index: self.descriptor_index,
334            step_limit: self.step_limit,
335            _marker: PhantomData,
336        }
337    }
338}
solverforge_solver/manager/phase_factory/k_opt.rs

solverforge_solver/manager/phase_factory/
k_opt.rs
