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::{RecordingScoreDirector, ScoreDirector};
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::SimpleScore;
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<SimpleScore>,
42/// }
43///
44/// impl PlanningSolution for Plan {
45///     type Score = SimpleScore;
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<(S, V, DM, 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<(S, 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: ScoreDirector<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().is_terminate_early() {
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 RecordingScoreDirector for automatic undo
238                {
239                    let mut recording =
240                        RecordingScoreDirector::new(step_scope.score_director_mut());
241                    mv.do_move(&mut recording);
242                    let move_score = recording.calculate_score();
243
244                    // Accept if improving over last step
245                    if move_score > last_step_score
246                        && best_score.as_ref().is_none_or(|b| move_score > *b)
247                    {
248                        best_score = Some(move_score);
249                        best_move_idx = Some(idx);
250                    }
251
252                    // Undo the move
253                    recording.undo_changes();
254                }
255            }
256
257            // Apply best move if found
258            if let (Some(idx), Some(score)) = (best_move_idx, best_score) {
259                moves[idx].do_move(step_scope.score_director_mut());
260                step_scope.set_step_score(score);
261                last_step_score = score;
262                step_scope.phase_scope_mut().update_best_solution();
263            } else {
264                // No improving moves found - phase is done
265                break;
266            }
267
268            step_scope.complete();
269            steps += 1;
270        }
271
272        // Ensure we have a best solution
273        if phase_scope.solver_scope().best_solution().is_none() {
274            phase_scope.update_best_solution();
275        }
276    }
277
278    fn phase_type_name(&self) -> &'static str {
279        "KOpt"
280    }
281}
282
283impl<S, V, DM, ESF, D> PhaseFactory<S, D> for KOptPhaseBuilder<S, V, DM, ESF>
284where
285    S: PlanningSolution,
286    V: Clone + Send + Sync + Debug + 'static,
287    DM: Send + Sync,
288    ESF: Send + Sync,
289    D: ScoreDirector<S>,
290{
291    type Phase = KOptPhase<S, V>;
292
293    fn create(&self) -> Self::Phase {
294        KOptPhase {
295            config: KOptConfig::new(self.k),
296            list_len: self.list_len,
297            sublist_remove: self.sublist_remove,
298            sublist_insert: self.sublist_insert,
299            variable_name: self.variable_name,
300            descriptor_index: self.descriptor_index,
301            step_limit: self.step_limit,
302            _marker: PhantomData,
303        }
304    }
305}
solverforge_solver/manager/phase_factory/k_opt.rs

solverforge_solver/manager/phase_factory/
k_opt.rs
