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

//! This module contains various Local Search operators.

use crate::algorithms::nsga2::Objective;
use crate::construction::heuristics::InsertionContext;
use crate::solver::RefinementContext;
use std::cmp::Ordering;

mod exchange_inter_route;
pub use self::exchange_inter_route::ExchangeInterRouteBest;
pub use self::exchange_inter_route::ExchangeInterRouteRandom;

mod exchange_intra_route;
pub use self::exchange_intra_route::ExchangeIntraRouteRandom;

/// Specifies behavior of a local search operator.
pub trait LocalSearch {
    /// Applies local search operator to passed solution in order to explore possible
    /// small move in solution space which leads to a different solution.
    fn explore(&self, refinement_ctx: &RefinementContext, insertion_ctx: &InsertionContext)
        -> Option<InsertionContext>;
}

/// Provides the way to run multiple local search operators with different probability.
pub struct CompositeLocalSearch {
    operators: Vec<Box<dyn LocalSearch + Send + Sync>>,
    weights: Vec<usize>,
    times: (i32, i32),
}

impl CompositeLocalSearch {
    /// Creates a new instance of `CompositeLocalSearch`.
    pub fn new(operators: Vec<(Box<dyn LocalSearch + Send + Sync>, usize)>, min: usize, max: usize) -> Self {
        let weights = operators.iter().map(|(_, weight)| *weight).collect();
        let operators = operators.into_iter().map(|(operator, _)| operator).collect();

        Self { operators, weights, times: (min as i32, max as i32) }
    }
}

impl Default for CompositeLocalSearch {
    fn default() -> Self {
        Self::new(
            vec![
                (Box::new(ExchangeInterRouteBest::default()), 100),
                (Box::new(ExchangeInterRouteRandom::default()), 30),
                (Box::new(ExchangeIntraRouteRandom::default()), 30),
            ],
            1,
            2,
        )
    }
}

impl LocalSearch for CompositeLocalSearch {
    fn explore(
        &self,
        refinement_ctx: &RefinementContext,
        insertion_ctx: &InsertionContext,
    ) -> Option<InsertionContext> {
        let times = insertion_ctx.random.uniform_int(self.times.0, self.times.1);

        let mut old_result = insertion_ctx.deep_copy();

        for _ in 0..times {
            let index = insertion_ctx.random.weighted(self.weights.as_slice());
            let new_result = self.operators.get(index).unwrap().explore(refinement_ctx, &old_result);

            if let Some(new_result) = new_result {
                if refinement_ctx.problem.objective.total_order(insertion_ctx, &new_result) == Ordering::Greater {
                    return Some(new_result);
                } else {
                    old_result = new_result;
                }
            }
        }

        Some(old_result)
    }
}