vrp-core 1.25.0

A core algorithms to solve a Vehicle Routing Problem
Documentation 
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

use crate::construction::heuristics::SolutionContext;
use crate::models::problem::Job;
use std::collections::HashSet;

/// Defines how jobs are moved in solution context. Index of original affected route context is passed.
pub trait JobContextTransition: Send + Sync {
    /// Returns true if job is moved from required to ignored.
    fn remove_from_required(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool;

    /// Returns true if job is moved from ignored to required.
    fn promote_to_required(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool;

    /// Returns true if job is removed from locked.
    fn remove_from_locked(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool;

    /// Returns true if job is moved to locked.
    fn promote_to_locked(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool;
}

/// A concrete implementation of `JobContextTransition` which allows to use lambdas.
pub struct ConcreteJobContextTransition<FRemoveRequired, FPromoteRequired, FRemoveLocked, FPromoteLocked>
where
    FRemoveRequired: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FPromoteRequired: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FRemoveLocked: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FPromoteLocked: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
{
    /// A function which removes job from required list.
    pub remove_required: FRemoveRequired,
    /// A function which promotes job to required jobs.
    pub promote_required: FPromoteRequired,
    /// A function which removes job from locked list.
    pub remove_locked: FRemoveLocked,
    /// A function which promotes job to locked jobs.
    pub promote_locked: FPromoteLocked,
}

impl<FRemoveRequired, FPromoteRequired, FRemoveLocked, FPromoteLocked> JobContextTransition
    for ConcreteJobContextTransition<FRemoveRequired, FPromoteRequired, FRemoveLocked, FPromoteLocked>
where
    FRemoveRequired: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FPromoteRequired: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FRemoveLocked: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
    FPromoteLocked: Fn(&SolutionContext, Option<usize>, &Job) -> bool + Send + Sync,
{
    fn remove_from_required(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool {
        (self.remove_required)(solution_ctx, route_index, job)
    }

    fn promote_to_required(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool {
        (self.promote_required)(solution_ctx, route_index, job)
    }

    fn remove_from_locked(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool {
        (self.remove_locked)(solution_ctx, route_index, job)
    }

    fn promote_to_locked(&self, solution_ctx: &SolutionContext, route_index: Option<usize>, job: &Job) -> bool {
        (self.promote_locked)(solution_ctx, route_index, job)
    }
}

/// Process conditional jobs: promotes them between ignored/required collections.
pub fn process_conditional_jobs(
    solution_ctx: &mut SolutionContext,
    route_index: Option<usize>,
    context_transition: &(dyn JobContextTransition),
) {
    // analyzed required/ignored
    let ignored: HashSet<Job> = solution_ctx
        .required
        .iter()
        .filter(|job| context_transition.remove_from_required(solution_ctx, route_index, job))
        .cloned()
        .collect();
    solution_ctx.required.retain(|job| !ignored.contains(job));
    solution_ctx.unassigned.retain(|job, _| !ignored.contains(job));

    // identify required inside ignored
    let required: HashSet<Job> = solution_ctx
        .ignored
        .iter()
        .filter(|job| context_transition.promote_to_required(solution_ctx, route_index, job))
        .cloned()
        .collect();
    solution_ctx.ignored.retain(|job| !required.contains(job));

    solution_ctx.required.extend(required);
    solution_ctx.ignored.extend(ignored);

    // analyze locked
    let not_locked: HashSet<Job> = solution_ctx
        .locked
        .iter()
        .filter(|job| context_transition.remove_from_locked(solution_ctx, route_index, job))
        .cloned()
        .collect();
    solution_ctx.locked.retain(|job| !not_locked.contains(job));

    let locked: HashSet<Job> = solution_ctx
        .required
        .iter()
        .chain(solution_ctx.ignored.iter())
        .filter(|job| context_transition.promote_to_locked(solution_ctx, route_index, job))
        .cloned()
        .collect();

    solution_ctx.locked.extend(locked);
}