solverforge_solver/manager/phase_factory/
k_opt.rs

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

solverforge_solver/manager/phase_factory/
k_opt.rs
