solverforge_solver/phase/
dynamic_vnd.rs

1use std::fmt::{self, Debug};
2use std::marker::PhantomData;
3
4use solverforge_core::domain::PlanningSolution;
5use solverforge_scoring::{Director, RecordingDirector};
6
7use crate::heuristic::r#move::Move;
8use crate::heuristic::selector::move_selector::MoveCursor;
9use crate::heuristic::selector::MoveSelector;
10use crate::phase::control::{
11    settle_search_interrupt, should_interrupt_evaluation, should_interrupt_generation,
12    StepInterrupt,
13};
14use crate::phase::Phase;
15use crate::scope::{PhaseScope, ProgressCallback, SolverScope, StepScope};
16
17pub struct DynamicVndPhase<S, M, MS> {
18    neighborhoods: Vec<MS>,
19    _phantom: PhantomData<(fn() -> S, fn() -> M)>,
20}
21
22impl<S, M, MS> DynamicVndPhase<S, M, MS> {
23    pub fn new(neighborhoods: Vec<MS>) -> Self {
24        Self {
25            neighborhoods,
26            _phantom: PhantomData,
27        }
28    }
29}
30
31impl<S, M, MS: Debug> Debug for DynamicVndPhase<S, M, MS> {
32    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
33        f.debug_struct("DynamicVndPhase")
34            .field("neighborhoods", &self.neighborhoods)
35            .finish()
36    }
37}
38
39impl<S, D, ProgressCb, M, MS> Phase<S, D, ProgressCb> for DynamicVndPhase<S, M, MS>
40where
41    S: PlanningSolution,
42    D: Director<S>,
43    ProgressCb: ProgressCallback<S>,
44    M: Move<S>,
45    MS: MoveSelector<S, M>,
46{
47    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
48        let mut phase_scope = PhaseScope::new(solver_scope, 0);
49        let mut current_score = phase_scope.calculate_score();
50        let mut k = 0usize;
51
52        while k < self.neighborhoods.len() {
53            let mut step_scope = StepScope::new(&mut phase_scope);
54            let mut cursor = self.neighborhoods[k].open_cursor(step_scope.score_director());
55
56            match find_best_improving_move(&mut cursor, &mut step_scope, &current_score) {
57                MoveSearchResult::Found(selected_move, selected_score) => {
58                    step_scope.apply_committed_move(&selected_move);
59                    step_scope.set_step_score(selected_score);
60                    current_score = selected_score;
61                    step_scope.phase_scope_mut().update_best_solution();
62                    step_scope.complete();
63                    k = 0;
64                }
65                MoveSearchResult::NotFound => {
66                    step_scope.complete();
67                    k += 1;
68                }
69                MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
70                    StepInterrupt::Restart => continue,
71                    StepInterrupt::TerminatePhase => break,
72                },
73            }
74        }
75    }
76
77    fn phase_type_name(&self) -> &'static str {
78        "VariableNeighborhoodDescent"
79    }
80}
81
82enum MoveSearchResult<M, Sc> {
83    Found(M, Sc),
84    NotFound,
85    Interrupted,
86}
87
88fn find_best_improving_move<S, D, ProgressCb, M, C>(
89    cursor: &mut C,
90    step_scope: &mut StepScope<'_, '_, '_, S, D, ProgressCb>,
91    current_score: &S::Score,
92) -> MoveSearchResult<M, S::Score>
93where
94    S: PlanningSolution,
95    D: Director<S>,
96    ProgressCb: ProgressCallback<S>,
97    M: Move<S>,
98    C: MoveCursor<S, M>,
99{
100    let mut best: Option<(usize, S::Score)> = None;
101
102    let mut generated = 0usize;
103    let mut evaluated = 0usize;
104    loop {
105        if should_interrupt_generation(step_scope, generated) {
106            return MoveSearchResult::Interrupted;
107        }
108        let Some((candidate_index, mov)) = cursor.next_candidate() else {
109            break;
110        };
111        generated += 1;
112
113        if !mov.is_doable(step_scope.score_director()) {
114            continue;
115        }
116        if should_interrupt_evaluation(step_scope, evaluated) {
117            return MoveSearchResult::Interrupted;
118        }
119        evaluated += 1;
120
121        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
122        mov.do_move(&mut recording);
123        let move_score = recording.calculate_score();
124        recording.undo_changes();
125
126        if move_score > *current_score {
127            match &best {
128                Some((_, best_score)) if move_score > *best_score => {
129                    best = Some((candidate_index, move_score));
130                }
131                None => best = Some((candidate_index, move_score)),
132                _ => {}
133            }
134        }
135    }
136
137    match best {
138        Some((index, score)) => MoveSearchResult::Found(cursor.take_candidate(index), score),
139        None => MoveSearchResult::NotFound,
140    }
141}
142
143#[cfg(test)]
144#[path = "dynamic_vnd_tests.rs"]
145mod tests;
solverforge_solver/phase/dynamic_vnd.rs

solverforge_solver/phase/
dynamic_vnd.rs
