vrp_core/solver/search/ruin/
route_removal.rs

1#[cfg(test)]
2#[path = "../../../../tests/unit/solver/search/ruin/route_removal_test.rs"]
3mod route_removal_test;
4
5use super::*;
6use crate::models::problem::Actor;
7use crate::solver::search::JobRemovalTracker;
8use crate::solver::RefinementContext;
9use rand::prelude::SliceRandom;
10
11/// A ruin strategy which removes random route from solution.
12pub struct RandomRouteRemoval {
13    limits: RemovalLimits,
14}
15
16impl RandomRouteRemoval {
17    /// Creates a new instance of `RandomRouteRemoval`.
18    pub fn new(limits: RemovalLimits) -> Self {
19        Self { limits }
20    }
21}
22
23impl Ruin for RandomRouteRemoval {
24    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
25        let random = insertion_ctx.environment.random.clone();
26        let affected = self.limits.affected_routes_range.end.min(insertion_ctx.solution.routes.len());
27        let mut tracker = JobRemovalTracker::new(&self.limits, random.as_ref());
28
29        (0..affected).for_each(|_| {
30            let route_idx = random.uniform_int(0, (insertion_ctx.solution.routes.len() - 1) as i32) as usize;
31            let solution = &mut insertion_ctx.solution;
32
33            tracker.try_remove_route(solution, route_idx, random.as_ref());
34        });
35
36        insertion_ctx
37    }
38}
39
40/// Removes a few random, close to each other, routes from solution.
41pub struct CloseRouteRemoval {
42    limits: RemovalLimits,
43}
44
45impl CloseRouteRemoval {
46    /// Creates a new instance of `CloseRouteRemoval`.
47    pub fn new(mut limits: RemovalLimits) -> Self {
48        limits.affected_routes_range.start = limits.affected_routes_range.start.max(2);
49        limits.affected_routes_range.end = limits.affected_routes_range.end.max(3);
50
51        Self { limits }
52    }
53}
54
55impl Ruin for CloseRouteRemoval {
56    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
57        if insertion_ctx.solution.routes.is_empty() {
58            return insertion_ctx;
59        }
60
61        let random = insertion_ctx.environment.random.clone();
62        let route_groups = group_routes_by_proximity(&insertion_ctx);
63
64        let stale_routes = insertion_ctx
65            .solution
66            .routes
67            .iter()
68            .enumerate()
69            .filter_map(|(idx, route)| if route.is_stale() { Some(idx) } else { None })
70            .collect::<Vec<_>>();
71
72        let route_index = if !stale_routes.is_empty() && random.is_head_not_tails() {
73            stale_routes[random.uniform_int(0, (stale_routes.len() - 1) as i32) as usize]
74        } else {
75            random.uniform_int(0, (route_groups.len() - 1) as i32) as usize
76        };
77
78        let routes = route_groups[route_index]
79            .iter()
80            .filter_map(|idx| insertion_ctx.solution.routes.get(*idx))
81            .map(|route_ctx| route_ctx.route().actor.clone())
82            .collect::<Vec<_>>();
83
84        remove_routes_with_actors(&mut insertion_ctx.solution, &self.limits, random.as_ref(), routes.into_iter());
85
86        insertion_ctx
87    }
88}
89
90/// Removes a "worst" routes: e.g. the smallest ones.
91pub struct WorstRouteRemoval {
92    limits: RemovalLimits,
93}
94
95impl WorstRouteRemoval {
96    /// Creates a new instance of `WorstRouteRemoval`.
97    pub fn new(limits: RemovalLimits) -> Self {
98        Self { limits }
99    }
100}
101
102impl Ruin for WorstRouteRemoval {
103    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
104        if insertion_ctx.solution.routes.is_empty() {
105            return insertion_ctx;
106        }
107
108        let random = insertion_ctx.environment.random.clone();
109
110        let mut route_sizes = insertion_ctx
111            .solution
112            .routes
113            .iter()
114            .enumerate()
115            // TODO exclude locked jobs from calculation
116            .map(|(route_idx, route_ctx)| (route_idx, route_ctx.route().tour.job_count()))
117            .collect::<Vec<_>>();
118        route_sizes.sort_by(|(_, job_count_left), (_, job_count_right)| job_count_left.cmp(job_count_right));
119        route_sizes.truncate(8);
120
121        let shuffle_amount = (route_sizes.len() as Float * 0.25) as usize;
122        route_sizes.partial_shuffle(&mut random.get_rng(), shuffle_amount);
123
124        #[allow(clippy::needless_collect)]
125        let routes = route_sizes
126            .iter()
127            .filter_map(|(idx, _)| insertion_ctx.solution.routes.get(*idx))
128            .map(|route_ctx| route_ctx.route().actor.clone())
129            .collect::<Vec<_>>();
130
131        remove_routes_with_actors(&mut insertion_ctx.solution, &self.limits, random.as_ref(), routes.into_iter());
132
133        insertion_ctx
134    }
135}
136
137fn remove_routes_with_actors<Iter>(
138    solution_ctx: &mut SolutionContext,
139    limits: &RemovalLimits,
140    random: &(dyn Random),
141    actors: Iter,
142) where
143    Iter: Iterator<Item = Arc<Actor>>,
144{
145    let mut tracker = JobRemovalTracker::new(limits, random);
146    actors.for_each(|actor| {
147        if let Some(route_idx) = solution_ctx.routes.iter().position(|route_ctx| route_ctx.route().actor == actor) {
148            tracker.try_remove_route(solution_ctx, route_idx, random);
149        }
150    });
151}
vrp_core/solver/search/ruin/route_removal.rs

vrp_core/solver/search/ruin/
route_removal.rs
