vrp_core/solver/search/local/
mod.rs

1//! This module contains various Local Search operators.
2
3use crate::construction::heuristics::*;
4use crate::solver::RefinementContext;
5use rosomaxa::prelude::*;
6use std::cmp::Ordering;
7use std::sync::Arc;
8
9mod exchange_inter_route;
10pub use self::exchange_inter_route::*;
11
12mod exchange_intra_route;
13pub use self::exchange_intra_route::*;
14
15mod exchange_sequence;
16pub use self::exchange_sequence::*;
17
18mod exchange_swap_star;
19pub use self::exchange_swap_star::*;
20
21mod reschedule_departure;
22pub use self::reschedule_departure::*;
23
24/// Specifies behavior of a local search operator.
25pub trait LocalOperator: Send + Sync {
26    /// Applies local search operator to passed solution in order to explore possible
27    /// small move in solution space which leads to a different solution.
28    fn explore(&self, refinement_ctx: &RefinementContext, insertion_ctx: &InsertionContext)
29        -> Option<InsertionContext>;
30}
31
32/// Provides the way to run multiple local search operators with different probability.
33pub struct CompositeLocalOperator {
34    operators: Vec<Arc<dyn LocalOperator>>,
35    weights: Vec<usize>,
36    times: (i32, i32),
37}
38
39impl CompositeLocalOperator {
40    /// Creates a new instance of `CompositeLocalOperator`.
41    pub fn new(operators: Vec<(Arc<dyn LocalOperator>, usize)>, min: usize, max: usize) -> Self {
42        let weights = operators.iter().map(|(_, weight)| *weight).collect();
43        let operators = operators.into_iter().map(|(operator, _)| operator).collect();
44
45        Self { operators, weights, times: (min as i32, max as i32) }
46    }
47}
48
49impl LocalOperator for CompositeLocalOperator {
50    fn explore(
51        &self,
52        refinement_ctx: &RefinementContext,
53        insertion_ctx: &InsertionContext,
54    ) -> Option<InsertionContext> {
55        let random = insertion_ctx.environment.random.as_ref();
56        let times = random.uniform_int(self.times.0, self.times.1);
57
58        let mut old_result = insertion_ctx.deep_copy();
59
60        for _ in 0..times {
61            let index = random.weighted(self.weights.as_slice());
62            let new_result = self.operators.get(index).unwrap().explore(refinement_ctx, &old_result);
63
64            if let Some(new_result) = new_result {
65                if refinement_ctx.problem.goal.total_order(insertion_ctx, &new_result) == Ordering::Greater {
66                    return Some(new_result);
67                } else {
68                    old_result = new_result;
69                }
70            }
71        }
72
73        Some(old_result)
74    }
75}
76
77/// Applies insertion success by creating a new route context from it.
78fn apply_insertion_with_route(insertion_ctx: &mut InsertionContext, result: (InsertionSuccess, Option<RouteContext>)) {
79    let (success, route_ctx) = result;
80
81    if let Some(route_ctx) = route_ctx {
82        debug_assert!(success.actor == route_ctx.route().actor);
83
84        let route_index = insertion_ctx
85            .solution
86            .routes
87            .iter()
88            .position(|route_ctx| route_ctx.route().actor == success.actor)
89            .unwrap();
90
91        // NOTE replace existing route with a new non empty route
92        insertion_ctx.solution.routes[route_index] = route_ctx;
93    }
94
95    apply_insertion_success(insertion_ctx, success)
96}
vrp_core/solver/search/local/mod.rs

vrp_core/solver/search/local/
mod.rs
