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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#[cfg(test)]
#[path = "../../../../tests/unit/solver/search/ruin/route_removal_test.rs"]
mod route_removal_test;

use super::*;
use crate::solver::search::JobRemovalTracker;
use crate::solver::RefinementContext;
use rand::prelude::SliceRandom;

/// A ruin strategy which removes random route from solution.
pub struct RandomRouteRemoval {
    limits: RemovalLimits,
}

impl RandomRouteRemoval {
    /// Creates a new instance of `RandomRouteRemoval`.
    pub fn new(limits: RemovalLimits) -> Self {
        Self { limits }
    }
}

impl Ruin for RandomRouteRemoval {
    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
        let random = insertion_ctx.environment.random.clone();
        let affected = self.limits.affected_routes_range.end.min(insertion_ctx.solution.routes.len());
        let mut tracker = JobRemovalTracker::new(&self.limits, random.as_ref());

        (0..affected).for_each(|_| {
            let route_index = random.uniform_int(0, (insertion_ctx.solution.routes.len() - 1) as i32) as usize;
            let solution = &mut insertion_ctx.solution;
            let route_ctx = &mut solution.routes.get(route_index).unwrap().clone();

            tracker.try_remove_route(solution, route_ctx, random.as_ref());
        });

        insertion_ctx
    }
}

/// Removes a few random, close to each other, routes from solution.
pub struct CloseRouteRemoval {
    limits: RemovalLimits,
}

impl CloseRouteRemoval {
    /// Creates a new instance of `CloseRouteRemoval`.
    pub fn new(limits: RemovalLimits) -> Self {
        assert!(limits.affected_routes_range.start > 1);
        Self { limits }
    }
}

impl Ruin for CloseRouteRemoval {
    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
        if insertion_ctx.solution.routes.is_empty() {
            return insertion_ctx;
        }

        if let Some(route_groups_distances) = group_routes_by_proximity(&insertion_ctx) {
            let random = insertion_ctx.environment.random.clone();

            let stale_routes = insertion_ctx
                .solution
                .routes
                .iter()
                .enumerate()
                .filter_map(|(idx, route)| if route.is_stale() { Some(idx) } else { None })
                .collect::<Vec<_>>();

            let route_index = if !stale_routes.is_empty() && random.is_head_not_tails() {
                stale_routes[random.uniform_int(0, (stale_routes.len() - 1) as i32) as usize]
            } else {
                random.uniform_int(0, (route_groups_distances.len() - 1) as i32) as usize
            };

            #[allow(clippy::needless_collect)]
            let routes = route_groups_distances[route_index]
                .iter()
                .filter_map(|(idx, _)| insertion_ctx.solution.routes.get(*idx).cloned())
                .collect::<Vec<_>>();

            remove_routes(&mut insertion_ctx.solution, &self.limits, random.as_ref(), routes.into_iter());
        }

        insertion_ctx
    }
}

/// Removes a "worst" routes: e.g. the smallest ones.
pub struct WorstRouteRemoval {
    limits: RemovalLimits,
}

impl WorstRouteRemoval {
    /// Creates a new instance of `WorstRouteRemoval`.
    pub fn new(limits: RemovalLimits) -> Self {
        Self { limits }
    }
}

impl Ruin for WorstRouteRemoval {
    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
        if insertion_ctx.solution.routes.is_empty() {
            return insertion_ctx;
        }

        let random = insertion_ctx.environment.random.clone();

        let mut route_sizes = insertion_ctx
            .solution
            .routes
            .iter()
            .enumerate()
            // TODO exclude locked jobs from calculation
            .map(|(route_idx, route_ctx)| (route_idx, route_ctx.route.tour.job_count()))
            .collect::<Vec<_>>();
        route_sizes.sort_by(|(_, job_count_left), (_, job_count_right)| job_count_left.cmp(job_count_right));
        route_sizes.truncate(8);

        let shuffle_amount = (route_sizes.len() as f64 * 0.25) as usize;
        route_sizes.partial_shuffle(&mut random.get_rng(), shuffle_amount);

        #[allow(clippy::needless_collect)]
        let routes = route_sizes
            .iter()
            .filter_map(|(idx, _)| insertion_ctx.solution.routes.get(*idx).cloned())
            .collect::<Vec<_>>();

        remove_routes(&mut insertion_ctx.solution, &self.limits, random.as_ref(), routes.into_iter());

        insertion_ctx
    }
}

fn remove_routes<Iter>(
    solution_ctx: &mut SolutionContext,
    limits: &RemovalLimits,
    random: &(dyn Random + Send + Sync),
    routes: Iter,
) where
    Iter: Iterator<Item = RouteContext>,
{
    let mut tracker = JobRemovalTracker::new(limits, random);
    routes.for_each(|mut route_ctx| {
        tracker.try_remove_route(solution_ctx, &mut route_ctx, random);
    });
}