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

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

use super::*;
use crate::construction::heuristics::{group_routes_by_proximity, InsertionContext, RouteContext, SolutionContext};
use crate::models::problem::Job;
use crate::solver::RefinementContext;

/// A ruin strategy which removes random route from solution.
pub struct RandomRouteRemoval {
    /// Specifies minimum amount of removed routes.
    min: f64,
    /// Specifies maximum amount of removed routes.
    max: f64,
    /// Specifies threshold ratio of maximum removed routes.
    threshold: f64,
}

impl RandomRouteRemoval {
    /// Creates a new instance of `RandomRouteRemoval`.
    pub fn new(rmin: usize, rmax: usize, threshold: f64) -> Self {
        Self { min: rmin as f64, max: rmax as f64, threshold }
    }
}

impl Default for RandomRouteRemoval {
    fn default() -> Self {
        Self::new(1, 4, 0.1)
    }
}

impl Ruin for RandomRouteRemoval {
    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
        let random = insertion_ctx.environment.random.clone();
        let max = (insertion_ctx.solution.routes.len() as f64 * self.threshold).max(self.min).round() as usize;
        let affected = random
            .uniform_int(self.min as i32, self.max as i32)
            .min(insertion_ctx.solution.routes.len().min(max) as i32) as usize;

        (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();

            remove_route(solution, route_ctx)
        });

        insertion_ctx
    }
}

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

impl Default for CloseRouteRemoval {
    fn default() -> Self {
        Self {}
    }
}

impl Ruin for CloseRouteRemoval {
    // NOTE clippy's false positive in route_groups_distances loop
    #[allow(clippy::needless_collect)]
    fn run(&self, _refinement_ctx: &RefinementContext, mut insertion_ctx: InsertionContext) -> InsertionContext {
        if let Some(route_groups_distances) = group_routes_by_proximity(&insertion_ctx) {
            let random = &insertion_ctx.environment.random;

            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
            };

            let take_count = random.uniform_int(2, 3) as usize;

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

            routes.into_iter().for_each(|mut route_ctx| {
                remove_route(&mut insertion_ctx.solution, &mut route_ctx);
            });
        }

        insertion_ctx
    }
}

fn remove_route(solution: &mut SolutionContext, route_ctx: &mut RouteContext) {
    if solution.locked.is_empty() {
        remove_whole_route(solution, route_ctx);
    } else {
        remove_part_route(solution, route_ctx);
    }
}

fn remove_whole_route(solution: &mut SolutionContext, route_ctx: &RouteContext) {
    solution.routes.retain(|rc| rc != route_ctx);
    solution.registry.free_route(route_ctx);
    solution.required.extend(route_ctx.route.tour.jobs());
}

fn remove_part_route(solution: &mut SolutionContext, route_ctx: &mut RouteContext) {
    let locked = solution.locked.clone();

    let can_remove_full_route = route_ctx.route.tour.jobs().all(|job| !locked.contains(&job));

    if can_remove_full_route {
        remove_whole_route(solution, route_ctx);
    } else {
        {
            let jobs: Vec<Job> = route_ctx.route.tour.jobs().filter(|job| !locked.contains(job)).collect();

            jobs.iter().for_each(|job| {
                route_ctx.route_mut().tour.remove(job);
            });
            solution.required.extend(jobs);
        }
    }
}