vrp-core 1.25.0

A core algorithms to solve a Vehicle Routing Problem
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

//! The mutation module specifies building blocks for mutation operator used by evolution.
//!
//! The default implementation of mutation operator is `RuinAndRecreateMutation` which is based on
//! **ruin and recreate** principle, introduced by [`Schrimpf et al. (2000)`].
//!
//! [`Schrimpf et al. (2000)`]: https://www.sciencedirect.com/science/article/pii/S0021999199964136
//!

use crate::construction::heuristics::InsertionContext;
use crate::models::GoalContext;
use crate::solver::{RefinementContext, TargetSearchOperator};
use rosomaxa::hyper::HeuristicDiversifyOperator;
use rosomaxa::prelude::{Float, HeuristicSearchOperator};
use rosomaxa::HeuristicSolution;

mod local;
pub use self::local::*;

mod recreate;
pub use self::recreate::*;

mod ruin;
pub use self::ruin::*;

mod utils;
pub(crate) use self::utils::*;

mod decompose_search;
pub use self::decompose_search::DecomposeSearch;

mod infeasible_search;
pub use self::infeasible_search::InfeasibleSearch;

mod local_search;
pub use self::local_search::LocalSearch;

mod redistribute_search;
pub use self::redistribute_search::RedistributeSearch;

mod ruin_recreate;
pub use self::ruin_recreate::RuinAndRecreate;

/// Provides the way to pick one heuristic operator from the group.
pub struct WeightedHeuristicOperator {
    mutations: Vec<TargetSearchOperator>,
    weights: Vec<usize>,
}

impl WeightedHeuristicOperator {
    /// Creates a new instance of `WeightedHeuristicOperator`.
    pub fn new(mutations: Vec<TargetSearchOperator>, weights: Vec<usize>) -> Self {
        Self { mutations, weights }
    }
}

impl HeuristicSearchOperator for WeightedHeuristicOperator {
    type Context = RefinementContext;
    type Objective = GoalContext;
    type Solution = InsertionContext;

    fn search(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Self::Solution {
        let index = solution.environment.random.weighted(self.weights.as_slice());

        self.mutations[index].search(heuristic_ctx, solution)
    }
}

impl HeuristicDiversifyOperator for WeightedHeuristicOperator {
    type Context = RefinementContext;
    type Objective = GoalContext;
    type Solution = InsertionContext;

    fn diversify(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Vec<Self::Solution> {
        vec![self.search(heuristic_ctx, solution)]
    }
}

/// Provides the way to run multiple heuristic operators one by one on the same solution.
pub struct CompositeHeuristicOperator {
    mutations: Vec<(TargetSearchOperator, Float)>,
}

impl CompositeHeuristicOperator {
    /// Creates a new instance of `CompositeHeuristicOperator`.
    pub fn new(mutations: Vec<(TargetSearchOperator, Float)>) -> Self {
        Self { mutations }
    }
}

impl HeuristicSearchOperator for CompositeHeuristicOperator {
    type Context = RefinementContext;
    type Objective = GoalContext;
    type Solution = InsertionContext;

    fn search(&self, heuristic_ctx: &Self::Context, solution: &Self::Solution) -> Self::Solution {
        let mut new_solution = None;

        for (mutation, probability) in self.mutations.iter() {
            if solution.environment.random.is_hit(*probability) {
                new_solution = Some(mutation.search(heuristic_ctx, new_solution.as_ref().unwrap_or(solution)));
            }
        }

        new_solution.unwrap_or_else(|| solution.deep_copy())
    }
}