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, MoveArena};
8use crate::heuristic::selector::MoveSelector;
9use crate::phase::Phase;
10use crate::scope::{PhaseScope, ProgressCallback, SolverScope, StepScope};
11
12pub struct DynamicVndPhase<S, M, MS> {
13    neighborhoods: Vec<MS>,
14    _phantom: PhantomData<(fn() -> S, fn() -> M)>,
15}
16
17impl<S, M, MS> DynamicVndPhase<S, M, MS> {
18    pub fn new(neighborhoods: Vec<MS>) -> Self {
19        Self {
20            neighborhoods,
21            _phantom: PhantomData,
22        }
23    }
24}
25
26impl<S, M, MS: Debug> Debug for DynamicVndPhase<S, M, MS> {
27    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28        f.debug_struct("DynamicVndPhase")
29            .field("neighborhoods", &self.neighborhoods)
30            .finish()
31    }
32}
33
34impl<S, D, ProgressCb, M, MS> Phase<S, D, ProgressCb> for DynamicVndPhase<S, M, MS>
35where
36    S: PlanningSolution,
37    D: Director<S>,
38    ProgressCb: ProgressCallback<S>,
39    M: Move<S>,
40    MS: MoveSelector<S, M>,
41{
42    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
43        let mut arena = MoveArena::<M>::new();
44        let mut phase_scope = PhaseScope::new(solver_scope, 0);
45        let mut current_score = phase_scope.calculate_score();
46        let mut k = 0usize;
47
48        while k < self.neighborhoods.len() {
49            let mut step_scope = StepScope::new(&mut phase_scope);
50            arena.reset();
51            arena.extend(self.neighborhoods[k].iter_moves(step_scope.score_director()));
52
53            let best_index =
54                find_best_improving_move_index(&arena, &mut step_scope, &current_score);
55
56            if let Some((selected_index, selected_score)) = best_index {
57                let selected_move = arena.take(selected_index);
58                selected_move.do_move(step_scope.score_director_mut());
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            } else {
65                step_scope.complete();
66                k += 1;
67            }
68        }
69    }
70
71    fn phase_type_name(&self) -> &'static str {
72        "VariableNeighborhoodDescent"
73    }
74}
75
76fn find_best_improving_move_index<S, D, ProgressCb, M>(
77    arena: &MoveArena<M>,
78    step_scope: &mut StepScope<'_, '_, '_, S, D, ProgressCb>,
79    current_score: &S::Score,
80) -> Option<(usize, S::Score)>
81where
82    S: PlanningSolution,
83    D: Director<S>,
84    ProgressCb: ProgressCallback<S>,
85    M: Move<S>,
86{
87    let mut best: Option<(usize, S::Score)> = None;
88
89    for i in 0..arena.len() {
90        let m = arena.get(i).unwrap();
91
92        if !m.is_doable(step_scope.score_director()) {
93            continue;
94        }
95
96        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
97        m.do_move(&mut recording);
98        let move_score = recording.calculate_score();
99        recording.undo_changes();
100
101        if move_score > *current_score {
102            match &best {
103                Some((_, best_score)) if move_score > *best_score => {
104                    best = Some((i, move_score));
105                }
106                None => best = Some((i, move_score)),
107                _ => {}
108            }
109        }
110    }
111
112    best
113}
solverforge_solver/phase/dynamic_vnd.rs

solverforge_solver/phase/
dynamic_vnd.rs
