vrp_core/solver/search/
mod.rs

1//! The mutation module specifies building blocks for mutation operator used by evolution.
2//!
3//! The default implementation of mutation operator is `RuinAndRecreateMutation` which is based on
4//! **ruin and recreate** principle, introduced by [`Schrimpf et al. (2000)`].
5//!
6//! [`Schrimpf et al. (2000)`]: https://www.sciencedirect.com/science/article/pii/S0021999199964136
7//!
8
9use crate::construction::heuristics::InsertionContext;
10use crate::models::GoalContext;
11use crate::solver::{RefinementContext, TargetSearchOperator};
12use rosomaxa::hyper::HeuristicDiversifyOperator;
13use rosomaxa::prelude::{Float, HeuristicSearchOperator};
14use rosomaxa::HeuristicSolution;
15
16mod local;
17pub use self::local::*;
18
19mod recreate;
20pub use self::recreate::*;
21
22mod ruin;
23pub use self::ruin::*;
24
25mod utils;
26pub(crate) use self::utils::*;
27
28mod decompose_search;
29pub use self::decompose_search::DecomposeSearch;
30
31mod infeasible_search;
32pub use self::infeasible_search::InfeasibleSearch;
33
34mod local_search;
35pub use self::local_search::LocalSearch;
36
37mod redistribute_search;
38pub use self::redistribute_search::RedistributeSearch;
39
40mod ruin_recreate;
41pub use self::ruin_recreate::RuinAndRecreate;
42
43/// Provides the way to pick one heuristic operator from the group.
44pub struct WeightedHeuristicOperator {
45    mutations: Vec<TargetSearchOperator>,
46    weights: Vec<usize>,
47}
48
49impl WeightedHeuristicOperator {
50    /// Creates a new instance of `WeightedHeuristicOperator`.
51    pub fn new(mutations: Vec<TargetSearchOperator>, weights: Vec<usize>) -> Self {
52        Self { mutations, weights }
53    }
54}
55
56impl HeuristicSearchOperator for WeightedHeuristicOperator {
57    type Context = RefinementContext;
58    type Objective = GoalContext;
59    type Solution = InsertionContext;
60
61    fn search(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Self::Solution {
62        let index = solution.environment.random.weighted(self.weights.as_slice());
63
64        self.mutations[index].search(heuristic_ctx, solution)
65    }
66}
67
68impl HeuristicDiversifyOperator for WeightedHeuristicOperator {
69    type Context = RefinementContext;
70    type Objective = GoalContext;
71    type Solution = InsertionContext;
72
73    fn diversify(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Vec<Self::Solution> {
74        vec![self.search(heuristic_ctx, solution)]
75    }
76}
77
78/// Provides the way to run multiple heuristic operators one by one on the same solution.
79pub struct CompositeHeuristicOperator {
80    mutations: Vec<(TargetSearchOperator, Float)>,
81}
82
83impl CompositeHeuristicOperator {
84    /// Creates a new instance of `CompositeHeuristicOperator`.
85    pub fn new(mutations: Vec<(TargetSearchOperator, Float)>) -> Self {
86        Self { mutations }
87    }
88}
89
90impl HeuristicSearchOperator for CompositeHeuristicOperator {
91    type Context = RefinementContext;
92    type Objective = GoalContext;
93    type Solution = InsertionContext;
94
95    fn search(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Self::Solution {
96        let mut new_solution = None;
97
98        for (mutation, probability) in self.mutations.iter() {
99            if solution.environment.random.is_hit(*probability) {
100                new_solution = Some(mutation.search(heuristic_ctx, new_solution.as_ref().unwrap_or(solution)));
101            }
102        }
103
104        new_solution.unwrap_or_else(|| solution.deep_copy())
105    }
106}
vrp_core/solver/search/mod.rs

vrp_core/solver/search/
mod.rs
