#[cfg(test)]
#[path = "../../../tests/unit/construction/heuristics/insertions_test.rs"]
mod insertions_test;
use crate::construction::heuristics::*;
use crate::models::common::{Cost, IdDimension};
use crate::models::problem::{Actor, Job};
use crate::models::solution::Activity;
use crate::models::ViolationCode;
use rosomaxa::prelude::*;
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::fmt::{Debug, Formatter};
use std::ops::{Add, ControlFlow, Index, Sub};
use std::sync::Arc;
use tinyvec::{TinyVec, TinyVecIterator};
#[derive(Debug)]
pub enum InsertionResult {
Success(InsertionSuccess),
Failure(InsertionFailure),
}
pub struct InsertionSuccess {
pub cost: InsertionCost,
pub job: Job,
pub activities: Vec<(Activity, usize)>,
pub actor: Arc<Actor>,
}
impl Debug for InsertionSuccess {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
f.debug_struct(short_type_name::<Self>())
.field("cost", &self.cost)
.field("job", &self.job)
.field(
"activities",
&self
.activities
.iter()
.map(|(a, idx)| {
(
a.retrieve_job()
.and_then(|job| job.dimens().get_id().cloned())
.unwrap_or("undef".to_string()),
*idx,
)
})
.collect::<Vec<_>>(),
)
.field("actor", self.actor.as_ref())
.finish()
}
}
#[derive(Debug)]
pub struct InsertionFailure {
pub constraint: ViolationCode,
pub stopped: bool,
pub job: Option<Job>,
}
const COST_DIMENSION: usize = 6;
type CostArray = [Cost; COST_DIMENSION];
#[derive(Clone, Default)]
pub struct InsertionCost {
data: TinyVec<CostArray>,
}
impl InsertionCost {
pub fn new(data: &[Cost]) -> Self {
Self { data: data.into() }
}
pub fn iter(&self) -> impl Iterator<Item = Cost> + '_ {
self.data.iter().cloned()
}
pub fn max_value() -> Self {
Self::new(&[Cost::MAX])
}
}
impl FromIterator<Cost> for InsertionCost {
fn from_iter<T: IntoIterator<Item = Cost>>(iter: T) -> Self {
Self { data: TinyVec::<CostArray>::from_iter(iter) }
}
}
impl IntoIterator for InsertionCost {
type Item = Cost;
type IntoIter = TinyVecIterator<CostArray>;
fn into_iter(self) -> Self::IntoIter {
self.data.into_iter()
}
}
impl Eq for InsertionCost {}
impl PartialEq for InsertionCost {
fn eq(&self, other: &Self) -> bool {
self.cmp(other) == Ordering::Equal
}
}
impl PartialOrd for InsertionCost {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for InsertionCost {
fn cmp(&self, other: &Self) -> Ordering {
let size = self.data.len().max(other.data.len());
(0..size)
.try_fold(Ordering::Equal, |acc, idx| {
let left = self.data.get(idx).cloned().unwrap_or_default();
let right = other.data.get(idx).cloned().unwrap_or_default();
let result = left.total_cmp(&right);
match result {
Ordering::Equal => ControlFlow::Continue(acc),
_ => ControlFlow::Break(result),
}
})
.unwrap_value()
}
}
impl<'a, B> Add<B> for &'a InsertionCost
where
B: Borrow<InsertionCost>,
{
type Output = InsertionCost;
fn add(self, rhs: B) -> Self::Output {
let rhs = rhs.borrow();
let size = self.data.len().max(rhs.data.len());
(0..size)
.map(|idx| {
self.data.get(idx).copied().unwrap_or(Cost::default())
+ rhs.data.get(idx).copied().unwrap_or(Cost::default())
})
.collect()
}
}
impl<B> Add<B> for InsertionCost
where
B: Borrow<InsertionCost>,
{
type Output = InsertionCost;
fn add(self, rhs: B) -> Self::Output {
&self + rhs
}
}
impl<'a, B> Sub<B> for &'a InsertionCost
where
B: Borrow<InsertionCost>,
{
type Output = InsertionCost;
fn sub(self, rhs: B) -> Self::Output {
let rhs = rhs.borrow();
let size = self.data.len().max(rhs.data.len());
(0..size)
.map(|idx| {
self.data.get(idx).copied().unwrap_or(Cost::default())
- rhs.data.get(idx).copied().unwrap_or(Cost::default())
})
.collect()
}
}
impl<B> Sub<B> for InsertionCost
where
B: Borrow<InsertionCost>,
{
type Output = InsertionCost;
fn sub(self, rhs: B) -> Self::Output {
&self - rhs
}
}
impl Debug for InsertionCost {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
f.debug_list().entries(&self.data).finish()
}
}
impl Index<usize> for InsertionCost {
type Output = Cost;
fn index(&self, index: usize) -> &Self::Output {
if index < self.data.len() {
&self.data[index]
} else {
panic!("index out of range: {index}, size is {}", self.data.len())
}
}
}
pub struct InsertionHeuristic {
insertion_evaluator: Box<dyn InsertionEvaluator + Send + Sync>,
}
impl Default for InsertionHeuristic {
fn default() -> Self {
InsertionHeuristic::new(Box::<PositionInsertionEvaluator>::default())
}
}
impl InsertionHeuristic {
pub fn new(insertion_evaluator: Box<dyn InsertionEvaluator + Send + Sync>) -> Self {
Self { insertion_evaluator }
}
}
impl InsertionHeuristic {
pub fn process(
&self,
insertion_ctx: InsertionContext,
job_selector: &(dyn JobSelector + Send + Sync),
route_selector: &(dyn RouteSelector + Send + Sync),
leg_selection: &LegSelection,
result_selector: &(dyn ResultSelector + Send + Sync),
) -> InsertionContext {
let mut insertion_ctx = insertion_ctx;
prepare_insertion_ctx(&mut insertion_ctx);
while !insertion_ctx.solution.required.is_empty()
&& !insertion_ctx.environment.quota.as_ref().map_or(false, |q| q.is_reached())
{
job_selector.prepare(&mut insertion_ctx);
route_selector.prepare(&mut insertion_ctx);
let jobs = job_selector.select(&insertion_ctx).collect::<Vec<_>>();
let routes = route_selector.select(&insertion_ctx, jobs.as_slice()).collect::<Vec<_>>();
let result =
self.insertion_evaluator.evaluate_all(&insertion_ctx, &jobs, &routes, leg_selection, result_selector);
match result {
InsertionResult::Success(success) => {
apply_insertion_success(&mut insertion_ctx, success);
}
InsertionResult::Failure(failure) => {
let (route_indices, jobs) = copy_selection_data(&insertion_ctx, routes.as_slice(), jobs.as_slice());
apply_insertion_failure(&mut insertion_ctx, failure, &route_indices, &jobs);
}
}
}
finalize_insertion_ctx(&mut insertion_ctx);
insertion_ctx
}
}
impl InsertionResult {
pub fn make_success(
cost: InsertionCost,
job: Job,
activities: Vec<(Activity, usize)>,
route_ctx: &RouteContext,
) -> Self {
Self::Success(InsertionSuccess { cost, job, activities, actor: route_ctx.route().actor.clone() })
}
pub fn make_failure() -> Self {
Self::make_failure_with_code(-1, false, None)
}
pub fn make_failure_with_code(code: i32, stopped: bool, job: Option<Job>) -> Self {
Self::Failure(InsertionFailure { constraint: code, stopped, job })
}
pub fn choose_best_result(left: Self, right: Self) -> Self {
match (&left, &right) {
(Self::Success(_), Self::Failure(_)) => left,
(Self::Failure(_), Self::Success(_)) => right,
(Self::Success(lhs), Self::Success(rhs)) => {
if lhs.cost > rhs.cost {
right
} else {
left
}
}
(Self::Failure(_), Self::Failure(rhs)) => {
if rhs.constraint == -1 {
left
} else {
right
}
}
}
}
pub fn as_success(&self) -> Option<&InsertionSuccess> {
match self {
Self::Success(success) => Some(success),
Self::Failure(_) => None,
}
}
}
impl TryFrom<InsertionResult> for InsertionSuccess {
type Error = InsertionFailure;
fn try_from(value: InsertionResult) -> Result<Self, Self::Error> {
match value {
InsertionResult::Success(success) => Ok(success),
InsertionResult::Failure(failure) => Err(failure),
}
}
}
pub(crate) fn prepare_insertion_ctx(insertion_ctx: &mut InsertionContext) {
insertion_ctx.solution.required.extend(insertion_ctx.solution.unassigned.iter().map(|(job, _)| job.clone()));
insertion_ctx.problem.goal.accept_solution_state(&mut insertion_ctx.solution);
}
pub(crate) fn finalize_insertion_ctx(insertion_ctx: &mut InsertionContext) {
finalize_unassigned(insertion_ctx, UnassignmentInfo::Unknown);
insertion_ctx.problem.goal.accept_solution_state(&mut insertion_ctx.solution);
}
pub(crate) fn apply_insertion_success(insertion_ctx: &mut InsertionContext, success: InsertionSuccess) {
let route_index = if let Some(new_route_ctx) = insertion_ctx.solution.registry.get_route(&success.actor) {
insertion_ctx.solution.routes.push(new_route_ctx);
insertion_ctx.solution.routes.len() - 1
} else {
insertion_ctx
.solution
.routes
.iter()
.position(|route_ctx| route_ctx.route().actor == success.actor)
.expect("registry is out of sync with used routes")
};
let route_ctx = insertion_ctx.solution.routes.get_mut(route_index).unwrap();
let route = route_ctx.route_mut();
success.activities.into_iter().for_each(|(a, index)| {
route.tour.insert_at(a, index + 1);
});
let job = success.job;
insertion_ctx.solution.required.retain(|j| *j != job);
insertion_ctx.solution.unassigned.remove(&job);
insertion_ctx.problem.goal.accept_insertion(&mut insertion_ctx.solution, route_index, &job);
}
fn apply_insertion_failure(
insertion_ctx: &mut InsertionContext,
failure: InsertionFailure,
route_indices: &[usize],
jobs: &[Job],
) {
let selected_routes = route_indices.len();
let selected_jobs = jobs.len();
let all_unassignable = selected_jobs == insertion_ctx.solution.required.len()
&& selected_routes == insertion_ctx.solution.routes.len();
let failure_handled = insertion_ctx.problem.goal.notify_failure(&mut insertion_ctx.solution, route_indices, jobs);
if failure_handled {
return;
}
let no_routes_available = failure.job.is_none();
if let Some(job) = failure.job {
insertion_ctx.solution.unassigned.insert(job.clone(), UnassignmentInfo::Simple(failure.constraint));
insertion_ctx.solution.required.retain(|j| *j != job);
}
if all_unassignable || no_routes_available {
let code =
if all_unassignable { UnassignmentInfo::Unknown } else { UnassignmentInfo::Simple(failure.constraint) };
finalize_unassigned(insertion_ctx, code);
}
}
fn finalize_unassigned(insertion_ctx: &mut InsertionContext, code: UnassignmentInfo) {
let unassigned = &insertion_ctx.solution.unassigned;
insertion_ctx.solution.required.retain(|job| !unassigned.contains_key(job));
insertion_ctx.solution.unassigned.extend(insertion_ctx.solution.required.drain(0..).map(|job| (job, code.clone())));
}
fn copy_selection_data(
insertion_ctx: &InsertionContext,
routes: &[&RouteContext],
jobs: &[&Job],
) -> (Vec<usize>, Vec<Job>) {
let route_indices = routes
.iter()
.filter_map(|route| insertion_ctx.solution.routes.iter().position(|r| r == *route))
.collect::<Vec<_>>();
let jobs = jobs.iter().map(|&job| job.clone()).collect::<Vec<_>>();
(route_indices, jobs)
}