#[cfg(test)]
#[path = "../../../tests/unit/construction/heuristics/selectors_test.rs"]
mod selectors_test;
use crate::construction::heuristics::*;
use crate::models::problem::Job;
use crate::utils::{map_reduce, parallel_collect, Either, Noise};
use rand::prelude::*;
pub trait RouteSelector {
fn select<'a>(&'a self, ctx: &'a mut InsertionContext, jobs: &[Job])
-> Box<dyn Iterator<Item = RouteContext> + 'a>;
}
pub struct AllRouteSelector {}
impl Default for AllRouteSelector {
fn default() -> Self {
Self {}
}
}
impl RouteSelector for AllRouteSelector {
fn select<'a>(
&'a self,
ctx: &'a mut InsertionContext,
_jobs: &[Job],
) -> Box<dyn Iterator<Item = RouteContext> + 'a> {
ctx.solution.routes.shuffle(&mut ctx.environment.random.get_rng());
Box::new(ctx.solution.routes.iter().cloned().chain(ctx.solution.registry.next()))
}
}
pub trait JobSelector {
fn select<'a>(&'a self, ctx: &'a mut InsertionContext) -> Box<dyn Iterator<Item = Job> + 'a>;
}
pub struct AllJobSelector {}
impl Default for AllJobSelector {
fn default() -> Self {
Self {}
}
}
impl JobSelector for AllJobSelector {
fn select<'a>(&'a self, ctx: &'a mut InsertionContext) -> Box<dyn Iterator<Item = Job> + 'a> {
ctx.solution.required.shuffle(&mut ctx.environment.random.get_rng());
Box::new(ctx.solution.required.iter().cloned())
}
}
pub trait InsertionEvaluator {
fn evaluate_job(
&self,
ctx: &InsertionContext,
job: &Job,
routes: &[RouteContext],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult;
fn evaluate_route(
&self,
ctx: &InsertionContext,
route: &RouteContext,
jobs: &[Job],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult;
fn evaluate_all(
&self,
ctx: &InsertionContext,
jobs: &[Job],
routes: &[RouteContext],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult;
}
pub struct PositionInsertionEvaluator {
insertion_position: InsertionPosition,
}
impl Default for PositionInsertionEvaluator {
fn default() -> Self {
Self::new(InsertionPosition::Any)
}
}
impl PositionInsertionEvaluator {
pub fn new(insertion_position: InsertionPosition) -> Self {
Self { insertion_position }
}
pub(crate) fn evaluate_and_collect_all(
&self,
ctx: &InsertionContext,
jobs: &[Job],
routes: &[RouteContext],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> Vec<InsertionResult> {
if Self::is_fold_jobs(ctx) {
parallel_collect(&jobs, |job| self.evaluate_job(ctx, job, routes, result_selector))
} else {
parallel_collect(&routes, |route| self.evaluate_route(ctx, route, jobs, result_selector))
}
}
fn is_fold_jobs(ctx: &InsertionContext) -> bool {
ctx.environment.random.is_head_not_tails()
}
}
impl InsertionEvaluator for PositionInsertionEvaluator {
fn evaluate_job(
&self,
ctx: &InsertionContext,
job: &Job,
routes: &[RouteContext],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult {
routes.iter().fold(InsertionResult::make_failure(), |acc, route_ctx| {
evaluate_job_insertion_in_route(&ctx, &route_ctx, job, self.insertion_position, acc, result_selector)
})
}
fn evaluate_route(
&self,
ctx: &InsertionContext,
route: &RouteContext,
jobs: &[Job],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult {
jobs.iter().fold(InsertionResult::make_failure(), |acc, job| {
evaluate_job_insertion_in_route(&ctx, &route, job, self.insertion_position, acc, result_selector)
})
}
fn evaluate_all(
&self,
ctx: &InsertionContext,
jobs: &[Job],
routes: &[RouteContext],
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionResult {
if Self::is_fold_jobs(ctx) {
map_reduce(
jobs,
|job| self.evaluate_job(ctx, job, routes, result_selector),
InsertionResult::make_failure,
|a, b| result_selector.select_insertion(&ctx, a, b),
)
} else {
map_reduce(
routes,
|route| self.evaluate_route(ctx, route, jobs, result_selector),
InsertionResult::make_failure,
|a, b| result_selector.select_insertion(&ctx, a, b),
)
}
}
}
pub trait ResultSelector {
fn select_insertion(
&self,
ctx: &InsertionContext,
left: InsertionResult,
right: InsertionResult,
) -> InsertionResult;
fn select_cost(&self, _route_ctx: &RouteContext, left: f64, right: f64) -> Either {
if left < right {
Either::Left
} else {
Either::Right
}
}
}
pub struct BestResultSelector {}
impl Default for BestResultSelector {
fn default() -> Self {
Self {}
}
}
impl ResultSelector for BestResultSelector {
fn select_insertion(&self, _: &InsertionContext, left: InsertionResult, right: InsertionResult) -> InsertionResult {
InsertionResult::choose_best_result(left, right)
}
}
pub struct NoiseResultSelector {
noise: Noise,
}
impl NoiseResultSelector {
pub fn new(noise: Noise) -> Self {
Self { noise }
}
}
impl ResultSelector for NoiseResultSelector {
fn select_insertion(&self, _: &InsertionContext, left: InsertionResult, right: InsertionResult) -> InsertionResult {
match (&left, &right) {
(InsertionResult::Success(_), InsertionResult::Failure(_)) => left,
(InsertionResult::Failure(_), InsertionResult::Success(_)) => right,
(InsertionResult::Success(left_success), InsertionResult::Success(right_success)) => {
let left_cost = self.noise.add(left_success.cost);
let right_cost = self.noise.add(right_success.cost);
if left_cost < right_cost {
left
} else {
right
}
}
_ => right,
}
}
fn select_cost(&self, _route_ctx: &RouteContext, left: f64, right: f64) -> Either {
let left = self.noise.add(left);
let right = self.noise.add(right);
if left < right {
Either::Left
} else {
Either::Right
}
}
}