#[cfg(test)]
#[path = "../../../tests/unit/construction/heuristics/context_test.rs"]
mod context_test;
use crate::construction::constraints::{TOTAL_DISTANCE_KEY, TOTAL_DURATION_KEY};
use crate::construction::heuristics::factories::*;
use crate::models::common::Cost;
use crate::models::problem::*;
use crate::models::solution::*;
use crate::models::{Extras, Problem, Solution};
use crate::utils::{as_mut, compare_floats, Random};
use hashbrown::{HashMap, HashSet};
use std::any::Any;
use std::ops::Deref;
use std::sync::Arc;
pub struct InsertionContext {
pub problem: Arc<Problem>,
pub solution: SolutionContext,
pub random: Arc<dyn Random + Send + Sync>,
}
impl InsertionContext {
pub fn new(problem: Arc<Problem>, random: Arc<dyn Random + Send + Sync>) -> Self {
create_insertion_context(problem, random)
}
pub fn new_from_solution(
problem: Arc<Problem>,
solution: (Solution, Option<Cost>),
random: Arc<dyn Random + Send + Sync>,
) -> Self {
let mut ctx = create_insertion_context_from_solution(problem, solution, random);
ctx.restore();
ctx
}
pub fn restore(&mut self) {
let constraint = self.problem.constraint.clone();
constraint.accept_solution_state(&mut self.solution);
self.remove_empty_routes();
self.solution.routes.iter_mut().for_each(|route_ctx| {
constraint.accept_route_state(route_ctx);
});
}
pub fn deep_copy(&self) -> Self {
InsertionContext {
problem: self.problem.clone(),
solution: self.solution.deep_copy(),
random: self.random.clone(),
}
}
fn remove_empty_routes(&mut self) {
let registry = &mut self.solution.registry;
self.solution.routes.retain(|rc| {
if rc.route.tour.has_jobs() {
true
} else {
registry.free_route(&rc);
false
}
});
}
}
pub type StateValue = Arc<dyn Any + Send + Sync>;
pub struct SolutionContext {
pub required: Vec<Job>,
pub ignored: Vec<Job>,
pub unassigned: HashMap<Job, i32>,
pub locked: HashSet<Job>,
pub routes: Vec<RouteContext>,
pub registry: RegistryContext,
pub state: HashMap<i32, StateValue>,
}
impl SolutionContext {
pub fn get_total_cost(&self) -> Cost {
self.routes.iter().fold(Cost::default(), |acc, rc| acc + rc.get_route_cost())
}
pub fn get_max_cost(&self) -> Cost {
self.routes.iter().map(|rc| rc.get_route_cost()).max_by(|&a, &b| compare_floats(a, b)).unwrap_or(0.)
}
pub fn to_solution(&self, extras: Arc<Extras>) -> Solution {
Solution {
registry: self.registry.resources().deep_copy(),
routes: self.routes.iter().map(|rc| rc.route.deep_copy()).collect(),
unassigned: self.unassigned.iter().map(|(job, code)| (job.clone(), *code)).collect(),
extras,
}
}
pub fn deep_copy(&self) -> Self {
Self {
required: self.required.clone(),
ignored: self.ignored.clone(),
unassigned: self.unassigned.clone(),
locked: self.locked.clone(),
routes: self.routes.iter().map(|rc| rc.deep_copy()).collect(),
registry: self.registry.deep_copy(),
state: self.state.clone(),
}
}
}
#[derive(Clone)]
pub struct RouteContext {
pub route: Arc<Route>,
pub state: Arc<RouteState>,
}
pub struct RouteState {
route_states: HashMap<i32, StateValue>,
activity_states: HashMap<ActivityWithKey, StateValue>,
keys: HashSet<i32>,
}
impl RouteContext {
pub fn new(actor: Arc<Actor>) -> Self {
let tour = Tour::new(&actor);
RouteContext { route: Arc::new(Route { actor, tour }), state: Arc::new(RouteState::default()) }
}
pub fn deep_copy(&self) -> Self {
let new_route = Route { actor: self.route.actor.clone(), tour: self.route.tour.deep_copy() };
let mut new_state = RouteState::new_with_sizes(self.state.sizes());
self.route.tour.all_activities().zip(0_usize..).for_each(|(a, index)| {
self.state.all_keys().for_each(|key| {
if let Some(value) = self.state.get_activity_state_raw(key, a) {
let a = new_route.tour.get(index).unwrap();
new_state.put_activity_state_raw(key, a, value.clone());
}
});
});
self.state.all_keys().for_each(|key| {
if let Some(value) = self.state.get_route_state_raw(key) {
new_state.put_route_state_raw(key, value.clone());
}
});
RouteContext { route: Arc::new(new_route), state: Arc::new(new_state) }
}
pub fn get_route_cost(&self) -> Cost {
let get_cost = |costs: &Costs, distance: f64, duration: f64| {
costs.fixed
+ costs.per_distance * distance
+ costs.per_driving_time.max(costs.per_service_time).max(costs.per_waiting_time) * duration
};
let actor = &self.route.actor;
let distance = self.state.get_route_state::<f64>(TOTAL_DISTANCE_KEY).cloned().unwrap_or(0.);
let duration = self.state.get_route_state::<f64>(TOTAL_DURATION_KEY).cloned().unwrap_or(0.);
get_cost(&actor.vehicle.costs, distance, duration) + get_cost(&actor.driver.costs, distance, duration)
}
pub fn as_mut(&mut self) -> (&mut Route, &mut RouteState) {
let route: &mut Route = unsafe { as_mut(&self.route) };
let state: &mut RouteState = unsafe { as_mut(&self.state) };
(route, state)
}
pub fn route_mut(&mut self) -> &mut Route {
unsafe { as_mut(&self.route) }
}
pub fn state_mut(&mut self) -> &mut RouteState {
unsafe { as_mut(&self.state) }
}
}
impl PartialEq<RouteContext> for RouteContext {
fn eq(&self, other: &RouteContext) -> bool {
self.route.deref() as *const Route == other.route.deref() as *const Route
}
}
impl Eq for RouteContext {}
impl Default for RouteState {
fn default() -> RouteState {
RouteState::new_with_sizes((2, 4))
}
}
impl RouteState {
pub fn new_with_sizes(sizes: (usize, usize)) -> RouteState {
RouteState {
route_states: HashMap::with_capacity(sizes.0),
activity_states: HashMap::with_capacity(sizes.1),
keys: Default::default(),
}
}
pub fn get_route_state<T: Send + Sync + 'static>(&self, key: i32) -> Option<&T> {
self.route_states.get(&key).and_then(|s| s.downcast_ref::<T>())
}
pub fn get_route_state_raw(&self, key: i32) -> Option<&StateValue> {
self.route_states.get(&key)
}
pub fn get_activity_state<T: Send + Sync + 'static>(&self, key: i32, activity: &Activity) -> Option<&T> {
self.activity_states.get(&(activity as *const Activity as usize, key)).and_then(|s| s.downcast_ref::<T>())
}
pub fn get_activity_state_raw(&self, key: i32, activity: &Activity) -> Option<&StateValue> {
self.activity_states.get(&(activity as *const Activity as usize, key))
}
pub fn put_route_state<T: Send + Sync + 'static>(&mut self, key: i32, value: T) {
self.route_states.insert(key, Arc::new(value));
self.keys.insert(key);
}
pub fn put_route_state_raw(&mut self, key: i32, value: Arc<dyn Any + Send + Sync>) {
self.route_states.insert(key, value);
self.keys.insert(key);
}
pub fn put_activity_state<T: Send + Sync + 'static>(&mut self, key: i32, activity: &Activity, value: T) {
self.activity_states.insert((activity as *const Activity as usize, key), Arc::new(value));
self.keys.insert(key);
}
pub fn put_activity_state_raw(&mut self, key: i32, activity: &Activity, value: StateValue) {
self.activity_states.insert((activity as *const Activity as usize, key), value);
self.keys.insert(key);
}
pub fn remove_activity_states(&mut self, activity: &Activity) {
for (_, key) in self.keys.iter().enumerate() {
self.activity_states.remove(&(activity as *const Activity as usize, *key));
}
}
pub fn all_keys<'a>(&'a self) -> impl Iterator<Item = i32> + 'a {
self.keys.iter().cloned()
}
pub fn sizes(&self) -> (usize, usize) {
(self.route_states.capacity(), self.activity_states.capacity())
}
}
pub struct RouteModifier {
modifier: Arc<dyn Fn(RouteContext) -> RouteContext + Sync + Send>,
}
impl RouteModifier {
pub fn new<F: 'static + Fn(RouteContext) -> RouteContext + Sync + Send>(modifier: F) -> Self {
Self { modifier: Arc::new(modifier) }
}
pub fn modify(&self, route_ctx: RouteContext) -> RouteContext {
self.modifier.deref()(route_ctx)
}
}
pub struct RegistryContext {
registry: Registry,
index: HashMap<Arc<Actor>, RouteContext>,
}
impl RegistryContext {
pub fn new(registry: Registry) -> Self {
Self::new_with_modifier(registry, &RouteModifier::new(|route_ctx| route_ctx))
}
pub fn new_with_modifier(registry: Registry, modifier: &RouteModifier) -> Self {
let index = registry.all().map(|actor| (actor.clone(), modifier.modify(RouteContext::new(actor)))).collect();
Self { registry, index }
}
pub fn resources(&self) -> &Registry {
&self.registry
}
pub fn next<'a>(&'a self) -> impl Iterator<Item = RouteContext> + 'a {
self.registry.next().map(move |actor| self.index[&actor].clone())
}
pub fn use_route(&mut self, route: &RouteContext) -> bool {
self.registry.use_actor(&route.route.actor)
}
pub fn free_route(&mut self, route: &RouteContext) {
self.registry.free_actor(&route.route.actor);
}
pub fn deep_copy(&self) -> Self {
Self { registry: self.registry.deep_copy(), index: self.index.clone() }
}
}
pub struct ActivityContext<'a> {
pub index: usize,
pub prev: &'a Activity,
pub target: &'a Activity,
pub next: Option<&'a Activity>,
}
type ActivityWithKey = (usize, i32);