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

solverforge_solver/phase/
dynamic_vnd.rs
