vrp_core/construction/heuristics/
selectors.rs

1#[cfg(test)]
2#[path = "../../../tests/unit/construction/heuristics/selectors_test.rs"]
3mod selectors_test;
4
5use crate::construction::heuristics::*;
6use crate::models::problem::Job;
7use crate::models::solution::Leg;
8use crate::utils::*;
9use rand::prelude::*;
10use std::cmp::Ordering;
11use std::ops::ControlFlow;
12use std::sync::Arc;
13
14/// On each insertion step, selects a list of routes where jobs can be inserted.
15/// It is up to implementation to decide whether list consists of all possible routes or just some subset.
16pub trait RouteSelector: Send + Sync {
17    /// This method is called before select. It allows to apply some changes on mutable context
18    /// before immutable borrowing could happen within select method.
19    /// Default implementation simply shuffles existing routes.
20    fn prepare(&self, insertion_ctx: &mut InsertionContext) {
21        insertion_ctx.solution.routes.shuffle(&mut insertion_ctx.environment.random.get_rng());
22    }
23
24    /// Returns routes for job insertion.
25    fn select<'a>(
26        &'a self,
27        insertion_ctx: &'a InsertionContext,
28        jobs: &[&'a Job],
29    ) -> Box<dyn Iterator<Item = &'a RouteContext> + 'a>;
30}
31
32/// Returns a list of all possible routes for insertion.
33#[derive(Default)]
34pub struct AllRouteSelector {}
35
36impl RouteSelector for AllRouteSelector {
37    fn select<'a>(
38        &'a self,
39        insertion_ctx: &'a InsertionContext,
40        _: &[&'a Job],
41    ) -> Box<dyn Iterator<Item = &'a RouteContext> + 'a> {
42        Box::new(insertion_ctx.solution.routes.iter().chain(insertion_ctx.solution.registry.next_route()))
43    }
44}
45
46/// On each insertion step, selects a list of jobs to be inserted.
47/// It is up to implementation to decide whether list consists of all jobs or just some subset.
48pub trait JobSelector: Send + Sync {
49    /// This method is called before select. It allows to apply some changes on mutable context
50    /// before immutable borrowing could happen within select method.
51    /// Default implementation simply shuffles jobs in required collection.
52    fn prepare(&self, insertion_ctx: &mut InsertionContext) {
53        insertion_ctx.solution.required.shuffle(&mut insertion_ctx.environment.random.get_rng());
54    }
55
56    /// Returns a portion of all jobs.
57    fn select<'a>(&'a self, insertion_ctx: &'a InsertionContext) -> Box<dyn Iterator<Item = &'a Job> + 'a> {
58        Box::new(insertion_ctx.solution.required.iter())
59    }
60}
61
62/// Returns a list of all jobs to be inserted.
63#[derive(Default)]
64pub struct AllJobSelector {}
65
66impl JobSelector for AllJobSelector {}
67
68/// Evaluates insertion.
69pub trait InsertionEvaluator: Send + Sync {
70    /// Evaluates insertion of a job collection into the given collection of routes.
71    fn evaluate_all(
72        &self,
73        insertion_ctx: &InsertionContext,
74        jobs: &[&Job],
75        routes: &[&RouteContext],
76        leg_selection: &LegSelection,
77        result_selector: &(dyn ResultSelector),
78    ) -> InsertionResult;
79}
80
81/// Evaluates job insertion in routes at given position.
82pub struct PositionInsertionEvaluator {
83    insertion_position: InsertionPosition,
84}
85
86impl Default for PositionInsertionEvaluator {
87    fn default() -> Self {
88        Self::new(InsertionPosition::Any)
89    }
90}
91
92impl PositionInsertionEvaluator {
93    /// Creates a new instance of `PositionInsertionEvaluator`.
94    pub fn new(insertion_position: InsertionPosition) -> Self {
95        Self { insertion_position }
96    }
97
98    /// Evaluates all jobs ad routes.
99    pub(crate) fn evaluate_and_collect_all(
100        &self,
101        insertion_ctx: &InsertionContext,
102        jobs: &[&Job],
103        routes: &[&RouteContext],
104        leg_selection: &LegSelection,
105        result_selector: &(dyn ResultSelector),
106    ) -> Vec<InsertionResult> {
107        let is_fold_jobs = insertion_ctx.solution.required.len() > insertion_ctx.solution.routes.len();
108        let goal = &insertion_ctx.problem.goal;
109
110        // NOTE using `fold_reduce` seems less effective
111        // TODO use alternative strategies specific for each use case when `evaluate_and_collect_all` is used?
112        if is_fold_jobs {
113            parallel_collect(jobs, |job| {
114                let eval_ctx = EvaluationContext { goal, job, leg_selection, result_selector };
115                routes.iter().fold(InsertionResult::make_failure(), |acc, route_ctx| {
116                    eval_job_insertion_in_route(insertion_ctx, &eval_ctx, route_ctx, self.insertion_position, acc)
117                })
118            })
119        } else {
120            parallel_collect(routes, |route_ctx| {
121                jobs.iter().fold(InsertionResult::make_failure(), |acc, job| {
122                    let eval_ctx = EvaluationContext { goal, job, leg_selection, result_selector };
123                    eval_job_insertion_in_route(insertion_ctx, &eval_ctx, route_ctx, self.insertion_position, acc)
124                })
125            })
126        }
127    }
128}
129
130impl InsertionEvaluator for PositionInsertionEvaluator {
131    fn evaluate_all(
132        &self,
133        insertion_ctx: &InsertionContext,
134        jobs: &[&Job],
135        routes: &[&RouteContext],
136        leg_selection: &LegSelection,
137        result_selector: &(dyn ResultSelector),
138    ) -> InsertionResult {
139        let goal = &insertion_ctx.problem.goal;
140
141        fold_reduce(
142            cartesian_product(routes, jobs),
143            InsertionResult::make_failure,
144            |acc, (route_ctx, job)| {
145                let eval_ctx = EvaluationContext { goal, job, leg_selection, result_selector };
146                eval_job_insertion_in_route(insertion_ctx, &eval_ctx, route_ctx, self.insertion_position, acc)
147            },
148            |left, right| result_selector.select_insertion(insertion_ctx, left, right),
149        )
150    }
151}
152
153/// Insertion result selector.
154pub trait ResultSelector: Send + Sync {
155    /// Selects one insertion result from two to promote as best.
156    fn select_insertion(
157        &self,
158        ctx: &InsertionContext,
159        left: InsertionResult,
160        right: InsertionResult,
161    ) -> InsertionResult;
162
163    /// Selects one insertion result from two to promote as best.
164    fn select_cost<'a>(
165        &self,
166        left: &'a InsertionCost,
167        right: &'a InsertionCost,
168    ) -> Either<&'a InsertionCost, &'a InsertionCost> {
169        if left < right {
170            Either::Left(left)
171        } else {
172            Either::Right(right)
173        }
174    }
175}
176
177/// Selects best result.
178#[derive(Default)]
179pub struct BestResultSelector {}
180
181impl ResultSelector for BestResultSelector {
182    fn select_insertion(&self, _: &InsertionContext, left: InsertionResult, right: InsertionResult) -> InsertionResult {
183        InsertionResult::choose_best_result(left, right)
184    }
185}
186
187/// Selects results with noise.
188pub struct NoiseResultSelector {
189    noise: Noise,
190}
191
192impl NoiseResultSelector {
193    /// Creates a new instance of `NoiseResultSelector`.
194    pub fn new(noise: Noise) -> Self {
195        Self { noise }
196    }
197}
198
199impl ResultSelector for NoiseResultSelector {
200    fn select_insertion(&self, _: &InsertionContext, left: InsertionResult, right: InsertionResult) -> InsertionResult {
201        match (&left, &right) {
202            (InsertionResult::Success(_), InsertionResult::Failure(_)) => left,
203            (InsertionResult::Failure(_), InsertionResult::Success(_)) => right,
204            (InsertionResult::Success(left_success), InsertionResult::Success(right_success)) => {
205                let left_cost: InsertionCost = self.noise.generate_multi(left_success.cost.iter()).collect();
206                let right_cost = self.noise.generate_multi(right_success.cost.iter()).collect();
207
208                match left_cost.cmp(&right_cost) {
209                    Ordering::Less => left,
210                    Ordering::Greater => right,
211                    Ordering::Equal if self.noise.random().is_head_not_tails() => left,
212                    _ => right,
213                }
214            }
215            _ => right,
216        }
217    }
218
219    fn select_cost<'a>(
220        &self,
221        left: &'a InsertionCost,
222        right: &'a InsertionCost,
223    ) -> Either<&'a InsertionCost, &'a InsertionCost> {
224        let left_cost: InsertionCost = self.noise.generate_multi(left.iter()).collect();
225        let right_cost: InsertionCost = self.noise.generate_multi(right.iter()).collect();
226
227        match left_cost.cmp(&right_cost) {
228            Ordering::Less => Either::Left(left),
229            Ordering::Greater => Either::Right(right),
230            Ordering::Equal if self.noise.random().is_head_not_tails() => Either::Left(left),
231            _ => Either::Right(right),
232        }
233    }
234}
235
236/// Selects a job with the highest cost insertion occurs into a new route.
237#[derive(Default)]
238pub struct FarthestResultSelector {}
239
240impl ResultSelector for FarthestResultSelector {
241    fn select_insertion(
242        &self,
243        insertion_ctx: &InsertionContext,
244        left: InsertionResult,
245        right: InsertionResult,
246    ) -> InsertionResult {
247        match (&left, &right) {
248            (InsertionResult::Success(_), InsertionResult::Failure(_)) => left,
249            (InsertionResult::Failure(_), InsertionResult::Success(_)) => right,
250            (InsertionResult::Success(lhs), InsertionResult::Success(rhs)) => {
251                let routes = &insertion_ctx.solution.routes;
252                let lhs_route = routes.iter().find(|route_ctx| route_ctx.route().actor == lhs.actor);
253                let rhs_route = routes.iter().find(|route_ctx| route_ctx.route().actor == rhs.actor);
254
255                let insert_right = match (lhs_route.is_some(), rhs_route.is_some()) {
256                    (false, false) => lhs.cost < rhs.cost,
257                    (true, false) => false,
258                    (false, true) => true,
259                    (true, true) => lhs.cost > rhs.cost,
260                };
261
262                if insert_right {
263                    right
264                } else {
265                    left
266                }
267            }
268            _ => right,
269        }
270    }
271}
272
273/// A result selector strategy inspired by "Slack Induction by String Removals for Vehicle
274/// Routing Problems", Jan Christiaens, Greet Vanden Berghe.
275pub struct BlinkResultSelector {
276    random: Arc<dyn Random>,
277    ratio: Float,
278}
279
280impl BlinkResultSelector {
281    /// Creates an instance of `BlinkResultSelector`.
282    pub fn new(ratio: Float, random: Arc<dyn Random>) -> Self {
283        Self { random, ratio }
284    }
285
286    /// Creates an instance of `BlinkResultSelector` with default values.
287    pub fn new_with_defaults(random: Arc<dyn Random>) -> Self {
288        Self::new(0.01, random)
289    }
290}
291
292impl ResultSelector for BlinkResultSelector {
293    fn select_insertion(&self, _: &InsertionContext, left: InsertionResult, right: InsertionResult) -> InsertionResult {
294        let is_blink = self.random.is_hit(self.ratio);
295
296        if is_blink {
297            return if self.random.is_head_not_tails() { left } else { right };
298        }
299
300        InsertionResult::choose_best_result(left, right)
301    }
302
303    fn select_cost<'a>(
304        &self,
305        left: &'a InsertionCost,
306        right: &'a InsertionCost,
307    ) -> Either<&'a InsertionCost, &'a InsertionCost> {
308        let is_blink = self.random.is_hit(self.ratio);
309
310        if is_blink {
311            return if self.random.is_head_not_tails() { Either::Left(left) } else { Either::Right(right) };
312        }
313
314        match left.cmp(right) {
315            Ordering::Less => Either::Left(left),
316            Ordering::Greater => Either::Right(right),
317            Ordering::Equal if self.random.is_head_not_tails() => Either::Left(left),
318            _ => Either::Right(right),
319        }
320    }
321}
322
323/// Keeps either specific result selector implementation or multiple implementations.
324pub enum ResultSelection {
325    /// Returns a provider which returns one of built-in result selectors non-deterministically.
326    Stochastic(ResultSelectorProvider),
327
328    /// Returns concrete instance of result selector to be used.
329    Concrete(Box<dyn ResultSelector>),
330}
331
332/// Provides way to access one of built-in result selectors non-deterministically.
333pub struct ResultSelectorProvider {
334    inners: Vec<Box<dyn ResultSelector>>,
335    weights: Vec<usize>,
336    random: Arc<dyn Random>,
337}
338
339impl ResultSelectorProvider {
340    /// Creates a new instance of `StochasticResultSelectorFn`
341    pub fn new_default(random: Arc<dyn Random>) -> Self {
342        Self {
343            inners: vec![
344                Box::<BestResultSelector>::default(),
345                Box::new(NoiseResultSelector::new(Noise::new_with_addition(0.05, (-0.25, 0.25), random.clone()))),
346                Box::new(BlinkResultSelector::new_with_defaults(random.clone())),
347                Box::<FarthestResultSelector>::default(),
348            ],
349            weights: vec![60, 10, 10, 20],
350            random,
351        }
352    }
353
354    /// Returns random result selector from the list.
355    pub fn pick(&self) -> &(dyn ResultSelector) {
356        self.inners[self.random.weighted(self.weights.as_slice())].as_ref()
357    }
358}
359
360/// Provides way to control routing leg selection mode.
361#[derive(Clone)]
362pub enum LegSelection {
363    /// Stochastic mode: depending on route size, not all legs could be selected.
364    Stochastic(Arc<dyn Random>),
365    /// Exhaustive mode: all legs are selected.
366    Exhaustive,
367}
368
369impl LegSelection {
370    /// Selects a best leg for insertion.
371    pub(crate) fn sample_best<R, FM, FC>(
372        &self,
373        route_ctx: &RouteContext,
374        job: &Job,
375        skip: usize,
376        init: R,
377        mut map_fn: FM,
378        compare_fn: FC,
379    ) -> R
380    where
381        R: Default,
382        FM: FnMut(Leg, R) -> ControlFlow<R, R>,
383        FC: Fn(&R, &R) -> bool,
384    {
385        if let Some((sample_size, random)) = self.get_sample_data(route_ctx, job, skip) {
386            route_ctx
387                .route()
388                .tour
389                .legs()
390                .skip(skip)
391                .sample_search(
392                    sample_size,
393                    random.clone(),
394                    &mut |leg: Leg<'_>| map_fn(leg, R::default()).unwrap_value(),
395                    |leg: &Leg<'_>| leg.1 - skip,
396                    &compare_fn,
397                )
398                .unwrap_or(init)
399        } else {
400            route_ctx.route().tour.legs().skip(skip).try_fold(init, |acc, leg| map_fn(leg, acc)).unwrap_value()
401        }
402    }
403
404    /// Returns a sample data for stochastic mode.
405    fn get_sample_data(&self, route_ctx: &RouteContext, job: &Job, skip: usize) -> Option<(usize, Arc<dyn Random>)> {
406        match self {
407            Self::Stochastic(random) => {
408                let gen_usize = |min: i32, max: i32| random.uniform_int(min, max) as usize;
409                let greedy_threshold = match job {
410                    Job::Single(_) => gen_usize(32, 48),
411                    Job::Multi(_) => gen_usize(16, 32),
412                };
413
414                let total_legs = route_ctx.route().tour.legs().size_hint().0;
415                let visit_legs = if total_legs > skip { total_legs - skip } else { 0 };
416
417                if visit_legs < greedy_threshold {
418                    None
419                } else {
420                    Some((
421                        match job {
422                            Job::Single(_) => 8,
423                            Job::Multi(_) => 4,
424                        },
425                        random.clone(),
426                    ))
427                }
428            }
429            Self::Exhaustive => None,
430        }
431    }
432}
vrp_core/construction/heuristics/selectors.rs

vrp_core/construction/heuristics/
selectors.rs
