vrp_core/solver/
heuristic.rs

1use super::*;
2use crate::construction::heuristics::*;
3use crate::models::{Extras, GoalContext};
4use crate::rosomaxa::get_default_selection_size;
5use crate::solver::search::*;
6use rosomaxa::algorithms::gsom::Input;
7use rosomaxa::hyper::*;
8use rosomaxa::population::*;
9use rosomaxa::termination::*;
10use std::marker::PhantomData;
11
12/// A type alias for domain specific evolution strategy.
13pub type TargetEvolutionStrategy =
14    Box<dyn EvolutionStrategy<Context = RefinementContext, Objective = GoalContext, Solution = InsertionContext>>;
15/// A type alias for domain specific population.
16pub type TargetPopulation =
17    Box<dyn HeuristicPopulation<Objective = GoalContext, Individual = InsertionContext> + Send + Sync>;
18/// A type alias for domain specific heuristic.
19pub type TargetHeuristic =
20    Box<dyn HyperHeuristic<Context = RefinementContext, Objective = GoalContext, Solution = InsertionContext>>;
21/// A type for domain specific heuristic operator.
22pub type TargetSearchOperator = Arc<
23    dyn HeuristicSearchOperator<Context = RefinementContext, Objective = GoalContext, Solution = InsertionContext>
24        + Send
25        + Sync,
26>;
27
28/// A type for greedy population.
29pub type GreedyPopulation = Greedy<GoalContext, InsertionContext>;
30/// A type for elitism population.
31pub type ElitismPopulation = Elitism<GoalContext, InsertionContext>;
32/// A type for rosomaxa population.
33pub type RosomaxaPopulation = Rosomaxa<GoalContext, InsertionContext>;
34
35/// A type alias for domain specific termination type.
36pub type DynTermination = dyn Termination<Context = RefinementContext, Objective = GoalContext> + Send + Sync;
37/// A type for composite termination.
38pub type TargetCompositeTermination = CompositeTermination<RefinementContext, GoalContext, InsertionContext>;
39/// A type for max time termination.
40pub type MaxTimeTermination = MaxTime<RefinementContext, GoalContext, InsertionContext>;
41/// A type for max generation termination.
42pub type MaxGenerationTermination = MaxGeneration<RefinementContext, GoalContext, InsertionContext>;
43/// A type for min variation termination.
44pub type MinVariationTermination = MinVariation<RefinementContext, GoalContext, InsertionContext, String>;
45
46/// A heuristic probability type alias.
47pub type TargetHeuristicProbability = HeuristicProbability<RefinementContext, GoalContext, InsertionContext>;
48/// A heuristic group type alias.
49pub type TargetHeuristicGroup = HeuristicSearchGroup<RefinementContext, GoalContext, InsertionContext>;
50
51/// A type alias for evolution config builder.
52pub type ProblemConfigBuilder = EvolutionConfigBuilder<RefinementContext, GoalContext, InsertionContext, String>;
53
54/// A type to filter meta heuristics by name. Returns true if heuristic can be used.
55pub type HeuristicFilterFn = Arc<dyn Fn(&str) -> bool + Send + Sync>;
56
57custom_extra_property!(HeuristicFilter typeof HeuristicFilterFn);
58
59/// Provides the way to get [ProblemConfigBuilder] with reasonable defaults for VRP domain.
60pub struct VrpConfigBuilder {
61    problem: Arc<Problem>,
62    environment: Option<Arc<Environment>>,
63    heuristic: Option<TargetHeuristic>,
64    telemetry_mode: Option<TelemetryMode>,
65}
66
67impl VrpConfigBuilder {
68    /// Creates a new instance of `VrpConfigBuilder`.
69    pub fn new(problem: Arc<Problem>) -> Self {
70        Self { problem, environment: None, heuristic: None, telemetry_mode: None }
71    }
72
73    /// Sets [Environment] instance to be used.
74    pub fn set_environment(mut self, environment: Arc<Environment>) -> Self {
75        self.environment = Some(environment);
76        self
77    }
78
79    /// Sets [TelemetryMode] to be used.
80    pub fn set_telemetry_mode(mut self, mode: TelemetryMode) -> Self {
81        self.telemetry_mode = Some(mode);
82        self
83    }
84
85    /// Sets [TargetHeuristic] to be used.
86    /// By default, it is used what is returned by [get_default_heuristic].
87    pub fn set_heuristic(mut self, heuristic: TargetHeuristic) -> Self {
88        self.heuristic = Some(heuristic);
89        self
90    }
91
92    /// Builds a preconfigured instance of [ProblemConfigBuilder] for further usage.
93    pub fn prebuild(self) -> GenericResult<ProblemConfigBuilder> {
94        let problem = self.problem;
95        let environment = self.environment.unwrap_or_else(|| Arc::new(Environment::default()));
96        let telemetry_mode =
97            self.telemetry_mode.unwrap_or_else(|| get_default_telemetry_mode(environment.logger.clone()));
98
99        let heuristic = self.heuristic.unwrap_or_else(|| get_default_heuristic(problem.clone(), environment.clone()));
100
101        let selection_size = get_default_selection_size(environment.as_ref());
102        let population = get_default_population(problem.goal.clone(), environment.clone(), selection_size);
103
104        Ok(ProblemConfigBuilder::default()
105            .with_heuristic(heuristic)
106            .with_context(RefinementContext::new(problem.clone(), population, telemetry_mode, environment.clone()))
107            .with_processing(create_default_processing())
108            .with_initial(4, 0.05, create_default_init_operators(problem, environment)))
109    }
110}
111
112/// Creates default telemetry mode.B
113pub fn get_default_telemetry_mode(logger: InfoLogger) -> TelemetryMode {
114    TelemetryMode::OnlyLogging { logger, log_best: 100, log_population: 1000 }
115}
116
117/// Gets default heuristic.
118pub fn get_default_heuristic(problem: Arc<Problem>, environment: Arc<Environment>) -> TargetHeuristic {
119    Timer::measure_duration_with_callback(
120        || Box::new(get_dynamic_heuristic(problem, environment.clone())),
121        |duration| (environment.logger)(format!("getting default heuristic took: {}ms", duration.as_millis()).as_str()),
122    )
123}
124
125/// Gets static heuristic using default settings.
126pub fn get_static_heuristic(
127    problem: Arc<Problem>,
128    environment: Arc<Environment>,
129) -> StaticSelective<RefinementContext, GoalContext, InsertionContext> {
130    let default_operator = statik::create_default_heuristic_operator(problem.clone(), environment.clone());
131    let local_search = statik::create_default_local_search(environment.random.clone());
132
133    let heuristic_group: TargetHeuristicGroup = vec![
134        (
135            Arc::new(DecomposeSearch::new(default_operator.clone(), (2, 4), 4, SINGLE_HEURISTIC_QUOTA_LIMIT)),
136            create_context_operator_probability(
137                300,
138                10,
139                vec![(SelectionPhase::Exploration, 0.05), (SelectionPhase::Exploitation, 0.05)],
140                environment.random.clone(),
141            ),
142        ),
143        (local_search.clone(), create_scalar_operator_probability(0.05, environment.random.clone())),
144        (default_operator.clone(), create_scalar_operator_probability(1., environment.random.clone())),
145        (local_search, create_scalar_operator_probability(0.05, environment.random.clone())),
146    ];
147
148    get_static_heuristic_from_heuristic_group(problem, environment, heuristic_group)
149}
150
151/// Gets static heuristic using heuristic group.
152pub fn get_static_heuristic_from_heuristic_group(
153    problem: Arc<Problem>,
154    environment: Arc<Environment>,
155    heuristic_group: TargetHeuristicGroup,
156) -> StaticSelective<RefinementContext, GoalContext, InsertionContext> {
157    StaticSelective::<RefinementContext, GoalContext, InsertionContext>::new(
158        heuristic_group,
159        create_diversify_operators(problem, environment),
160    )
161}
162
163/// Gets dynamic heuristic using default settings.
164pub fn get_dynamic_heuristic(
165    problem: Arc<Problem>,
166    environment: Arc<Environment>,
167) -> DynamicSelective<RefinementContext, GoalContext, InsertionContext> {
168    let search_operators = dynamic::get_operators(problem.clone(), environment.clone());
169    let diversify_operators = create_diversify_operators(problem, environment.clone());
170
171    DynamicSelective::<RefinementContext, GoalContext, InsertionContext>::new(
172        search_operators,
173        diversify_operators,
174        environment.as_ref(),
175    )
176}
177
178/// Creates elitism population algorithm.
179pub fn create_elitism_population(
180    objective: Arc<GoalContext>,
181    environment: Arc<Environment>,
182) -> Elitism<GoalContext, InsertionContext> {
183    let selection_size = get_default_selection_size(environment.as_ref());
184    Elitism::new(objective, environment.random.clone(), 4, selection_size)
185}
186
187custom_solution_state!(SolutionWeights typeof Vec<Float>);
188
189impl RosomaxaWeighted for InsertionContext {
190    fn init_weights(&mut self) {
191        // built a feature vector which is used to classify solution in population
192        let weights = vec![
193            // load related features
194            get_max_load_variance(self),
195            get_max_load_mean(self),
196            get_full_load_ratio(self),
197            // time related features
198            get_duration_mean(self),
199            get_waiting_mean(self),
200            // distance related features
201            get_distance_mean(self),
202            get_longest_distance_between_customers_mean(self),
203            get_first_distance_customer_mean(self),
204            get_last_distance_customer_mean(self),
205            // depot related features
206            get_average_distance_between_depot_customer_mean(self),
207            get_longest_distance_between_depot_customer_mean(self),
208            // tour related features
209            get_customers_deviation(self),
210            // default objective related
211            self.solution.unassigned.len() as Float,
212            self.solution.routes.len() as Float,
213            self.get_total_cost().unwrap_or_default(),
214        ];
215
216        self.solution.state.set_solution_weights(weights);
217    }
218}
219
220impl Input for InsertionContext {
221    fn weights(&self) -> &[Float] {
222        self.solution.state.get_solution_weights().unwrap().as_slice()
223    }
224}
225
226/// Creates a heuristic operator probability which uses `is_hit` method from passed random object.
227pub fn create_scalar_operator_probability(
228    scalar_probability: Float,
229    random: Arc<dyn Random>,
230) -> TargetHeuristicProbability {
231    (Box::new(move |_, _| random.is_hit(scalar_probability)), PhantomData)
232}
233
234/// Creates a heuristic operator probability which uses context state.
235pub fn create_context_operator_probability(
236    jobs_threshold: usize,
237    routes_threshold: usize,
238    phases: Vec<(SelectionPhase, Float)>,
239    random: Arc<dyn Random>,
240) -> TargetHeuristicProbability {
241    let phases = phases.into_iter().collect::<HashMap<_, _>>();
242    (
243        Box::new(move |refinement_ctx, insertion_ctx| {
244            let below_thresholds = insertion_ctx.problem.jobs.size() < jobs_threshold
245                || insertion_ctx.solution.routes.len() < routes_threshold;
246
247            if below_thresholds {
248                return false;
249            }
250
251            let phase_probability = phases.get(&refinement_ctx.selection_phase()).cloned().unwrap_or(0.);
252            random.is_hit(phase_probability)
253        }),
254        PhantomData,
255    )
256}
257
258fn get_limits(problem: &Problem) -> (RemovalLimits, RemovalLimits) {
259    let normal_limits = RemovalLimits::new(problem);
260    let activities_range = normal_limits.removed_activities_range.clone();
261    let small_limits = RemovalLimits {
262        removed_activities_range: (activities_range.start / 3).max(2)..(activities_range.end / 3).max(8),
263        affected_routes_range: 1..2,
264    };
265
266    (normal_limits, small_limits)
267}
268
269const SINGLE_HEURISTIC_QUOTA_LIMIT: usize = 200;
270
271pub use self::builder::create_default_init_operators;
272pub use self::builder::create_default_processing;
273pub use self::statik::create_default_heuristic_operator;
274
275mod builder {
276    use super::*;
277    use crate::rosomaxa::evolution::InitialOperators;
278    use crate::solver::processing::*;
279    use crate::solver::RecreateInitialOperator;
280
281    /// Creates default init operators.
282    pub fn create_default_init_operators(
283        problem: Arc<Problem>,
284        environment: Arc<Environment>,
285    ) -> InitialOperators<RefinementContext, GoalContext, InsertionContext> {
286        let random = environment.random.clone();
287        let wrap = |recreate: Arc<dyn Recreate>| Box::new(RecreateInitialOperator::new(recreate));
288
289        let mut main: InitialOperators<_, _, _> = vec![
290            (wrap(Arc::new(RecreateWithCheapest::new(random.clone()))), 1),
291            (wrap(Arc::new(RecreateWithFarthest::new(random.clone()))), 1),
292            (wrap(Arc::new(RecreateWithRegret::new(2, 3, random.clone()))), 1),
293            (wrap(Arc::new(RecreateWithGaps::new(1, (problem.jobs.size() / 10).max(1), random.clone()))), 1),
294            (wrap(Arc::new(RecreateWithSkipBest::new(1, 2, random.clone()))), 1),
295            (wrap(Arc::new(RecreateWithBlinks::new_with_defaults(random.clone()))), 1),
296            (wrap(Arc::new(RecreateWithPerturbation::new_with_defaults(random.clone()))), 1),
297            (wrap(Arc::new(RecreateWithNearestNeighbor::new(random.clone()))), 1),
298        ];
299
300        let alternatives = get_recreate_with_alternative_goal(problem.goal.as_ref(), {
301            move || RecreateWithCheapest::new(random.clone())
302        })
303        .map(|recreate| {
304            let init_operator: Box<
305                dyn InitialOperator<Context = RefinementContext, Objective = GoalContext, Solution = InsertionContext>
306                    + Send
307                    + Sync,
308            > = wrap(recreate);
309
310            (init_operator, 1)
311        })
312        .collect::<InitialOperators<_, _, _>>();
313
314        if alternatives.is_empty() {
315            main
316        } else {
317            main.splice(1..1, alternatives);
318            main
319        }
320    }
321
322    /// Create default processing.
323    pub fn create_default_processing() -> ProcessingConfig<RefinementContext, GoalContext, InsertionContext> {
324        ProcessingConfig {
325            context: vec![Box::<VicinityClustering>::default()],
326            solution: vec![
327                Box::new(AdvanceDeparture::default()),
328                Box::<RescheduleReservedTime>::default(),
329                Box::<UnassignmentReason>::default(),
330                Box::<VicinityClustering>::default(),
331            ],
332        }
333    }
334}
335
336fn create_diversify_operators(
337    problem: Arc<Problem>,
338    environment: Arc<Environment>,
339) -> HeuristicDiversifyOperators<RefinementContext, GoalContext, InsertionContext> {
340    let random = environment.random.clone();
341
342    let recreates: Vec<(Arc<dyn Recreate>, usize)> = vec![
343        (Arc::new(RecreateWithSkipBest::new(1, 2, random.clone())), 1),
344        (Arc::new(RecreateWithRegret::new(1, 3, random.clone())), 1),
345        (Arc::new(RecreateWithPerturbation::new_with_defaults(random.clone())), 1),
346        (Arc::new(RecreateWithGaps::new(2, 20, random.clone())), 1),
347        (Arc::new(RecreateWithNearestNeighbor::new(random.clone())), 1),
348        (Arc::new(RecreateWithSlice::new(random.clone())), 1),
349    ];
350
351    let redistribute_search = Arc::new(RedistributeSearch::new(Arc::new(WeightedRecreate::new(recreates))));
352    let infeasible_search = Arc::new(InfeasibleSearch::new(
353        Arc::new(WeightedHeuristicOperator::new(
354            vec![
355                dynamic::create_default_inner_ruin_recreate(problem, environment.clone()),
356                dynamic::create_default_local_search(random.clone()),
357            ],
358            vec![10, 1],
359        )),
360        Arc::new(RecreateWithCheapest::new(random)),
361        4,
362        (0.05, 0.2),
363        (0.33, 0.75),
364    ));
365    let local_search = Arc::new(LocalSearch::new(Arc::new(CompositeLocalOperator::new(
366        vec![(Arc::new(ExchangeSequence::new(8, 0.5, 0.1)), 1)],
367        2,
368        4,
369    ))));
370
371    vec![Arc::new(WeightedHeuristicOperator::new(
372        vec![redistribute_search, local_search, infeasible_search],
373        vec![10, 2, 1],
374    ))]
375}
376
377mod statik {
378    use super::*;
379
380    /// Creates default heuristic operator (ruin and recreate) with default parameters.
381    pub fn create_default_heuristic_operator(
382        problem: Arc<Problem>,
383        environment: Arc<Environment>,
384    ) -> TargetSearchOperator {
385        let (normal_limits, small_limits) = get_limits(problem.as_ref());
386        let random = environment.random.clone();
387
388        // initialize recreate
389        let recreate = Arc::new(WeightedRecreate::new(vec![
390            (Arc::new(RecreateWithSkipBest::new(1, 2, random.clone())), 50),
391            (Arc::new(RecreateWithRegret::new(2, 3, random.clone())), 20),
392            (Arc::new(RecreateWithCheapest::new(random.clone())), 20),
393            (Arc::new(RecreateWithPerturbation::new_with_defaults(random.clone())), 10),
394            (Arc::new(RecreateWithSkipBest::new(3, 4, random.clone())), 5),
395            (Arc::new(RecreateWithGaps::new(2, 20, random.clone())), 5),
396            (Arc::new(RecreateWithBlinks::new_with_defaults(random.clone())), 5),
397            (Arc::new(RecreateWithFarthest::new(random.clone())), 2),
398            (Arc::new(RecreateWithSkipBest::new(4, 8, random.clone())), 2),
399            (Arc::new(RecreateWithNearestNeighbor::new(random.clone())), 1),
400            (Arc::new(RecreateWithSlice::new(random.clone())), 1),
401            (
402                Arc::new(RecreateWithSkipRandom::default_explorative_phased(
403                    Arc::new(RecreateWithCheapest::new(random.clone())),
404                    random.clone(),
405                )),
406                1,
407            ),
408        ]));
409
410        // initialize ruin
411        let close_route = Arc::new(CloseRouteRemoval::new(normal_limits.clone()));
412        let worst_route = Arc::new(WorstRouteRemoval::new(normal_limits.clone()));
413        let random_route = Arc::new(RandomRouteRemoval::new(normal_limits.clone()));
414
415        let random_job = Arc::new(RandomJobRemoval::new(normal_limits.clone()));
416        let extra_random_job = Arc::new(RandomJobRemoval::new(small_limits));
417
418        let ruin = Arc::new(WeightedRuin::new(vec![
419            (
420                vec![
421                    (Arc::new(AdjustedStringRemoval::new_with_defaults(normal_limits.clone())), 1.),
422                    (extra_random_job.clone(), 0.1),
423                ],
424                100,
425            ),
426            (vec![(Arc::new(NeighbourRemoval::new(normal_limits.clone())), 1.), (extra_random_job.clone(), 0.1)], 10),
427            (vec![(Arc::new(WorstJobRemoval::new(4, normal_limits)), 1.), (extra_random_job.clone(), 0.1)], 10),
428            (
429                vec![
430                    // TODO avoid unwrap
431                    (Arc::new(ClusterRemoval::new_with_defaults(problem.clone()).unwrap()), 1.),
432                    (extra_random_job.clone(), 0.1),
433                ],
434                5,
435            ),
436            (vec![(close_route, 1.), (extra_random_job.clone(), 0.1)], 2),
437            (vec![(worst_route, 1.), (extra_random_job.clone(), 0.1)], 1),
438            (vec![(random_route, 1.), (extra_random_job.clone(), 0.1)], 1),
439            (vec![(random_job, 1.), (extra_random_job, 0.1)], 1),
440        ]));
441
442        Arc::new(WeightedHeuristicOperator::new(
443            vec![
444                Arc::new(RuinAndRecreate::new(ruin, recreate)),
445                create_default_local_search(environment.random.clone()),
446            ],
447            vec![100, 10],
448        ))
449    }
450
451    /// Creates default local search operator.
452    pub fn create_default_local_search(random: Arc<dyn Random>) -> TargetSearchOperator {
453        Arc::new(LocalSearch::new(Arc::new(CompositeLocalOperator::new(
454            vec![
455                (Arc::new(ExchangeSwapStar::new(random, SINGLE_HEURISTIC_QUOTA_LIMIT)), 200),
456                (Arc::new(ExchangeInterRouteBest::default()), 100),
457                (Arc::new(ExchangeSequence::default()), 100),
458                (Arc::new(ExchangeInterRouteRandom::default()), 30),
459                (Arc::new(ExchangeIntraRouteRandom::default()), 30),
460                (Arc::new(RescheduleDeparture::default()), 20),
461            ],
462            1,
463            2,
464        ))))
465    }
466}
467
468mod dynamic {
469    use super::*;
470
471    fn get_recreates(problem: &Problem, random: Arc<dyn Random>) -> Vec<(Arc<dyn Recreate>, String)> {
472        let cheapest: Arc<dyn Recreate> = Arc::new(RecreateWithCheapest::new(random.clone()));
473        vec![
474            (cheapest.clone(), "cheapest".to_string()),
475            (Arc::new(RecreateWithSkipBest::new(1, 2, random.clone())), "skip_best".to_string()),
476            (Arc::new(RecreateWithRegret::new(1, 3, random.clone())), "regret".to_string()),
477            (Arc::new(RecreateWithPerturbation::new_with_defaults(random.clone())), "perturbation".to_string()),
478            (Arc::new(RecreateWithGaps::new(2, 20, random.clone())), "gaps".to_string()),
479            (Arc::new(RecreateWithBlinks::new_with_defaults(random.clone())), "blinks".to_string()),
480            (Arc::new(RecreateWithFarthest::new(random.clone())), "farthest".to_string()),
481            (Arc::new(RecreateWithNearestNeighbor::new(random.clone())), "nearest".to_string()),
482            (
483                Arc::new(RecreateWithSkipRandom::default_explorative_phased(cheapest.clone(), random.clone())),
484                "skip_random".to_string(),
485            ),
486            (Arc::new(RecreateWithSlice::new(random.clone())), "slice".to_string()),
487        ]
488        .into_iter()
489        .chain(
490            get_recreate_with_alternative_goal(problem.goal.as_ref(), {
491                let random = random.clone();
492                move || RecreateWithCheapest::new(random.clone())
493            })
494            .enumerate()
495            .map(|(idx, recreate)| (recreate, format!("alternative_{idx}"))),
496        )
497        .collect()
498    }
499
500    fn get_ruins_with_limits(limits: RemovalLimits, prefix: &str) -> Vec<(Arc<dyn Ruin>, String, Float)> {
501        vec![
502            (Arc::new(AdjustedStringRemoval::new_with_defaults(limits.clone())), format!("{prefix}_asr"), 2.),
503            (Arc::new(NeighbourRemoval::new(limits.clone())), format!("{prefix}_neighbour_removal"), 5.),
504            (Arc::new(WorstJobRemoval::new(4, limits.clone())), format!("{prefix}_worst_job"), 4.),
505            (Arc::new(RandomJobRemoval::new(limits.clone())), format!("{prefix}_random_job_removal"), 4.),
506            (Arc::new(RandomRouteRemoval::new(limits.clone())), format!("{prefix}_random_route_removal"), 2.),
507            (Arc::new(CloseRouteRemoval::new(limits.clone())), format!("{prefix}_close_route_removal"), 4.),
508            (Arc::new(WorstRouteRemoval::new(limits)), format!("{prefix}_worst_route_removal"), 5.),
509        ]
510    }
511
512    fn get_ruins(problem: Arc<Problem>) -> Vec<(Arc<dyn Ruin>, String, Float)> {
513        vec![(
514            // TODO avoid unwrap
515            Arc::new(ClusterRemoval::new_with_defaults(problem.clone()).unwrap()),
516            "cluster_removal".to_string(),
517            4.,
518        )]
519    }
520
521    fn get_mutations(
522        problem: Arc<Problem>,
523        environment: Arc<Environment>,
524    ) -> Vec<(TargetSearchOperator, String, Float)> {
525        vec![
526            (
527                Arc::new(LocalSearch::new(Arc::new(ExchangeInterRouteBest::default()))),
528                "local_exch_inter_route_best".to_string(),
529                1.,
530            ),
531            (
532                Arc::new(LocalSearch::new(Arc::new(ExchangeInterRouteRandom::default()))),
533                "local_exch_inter_route_random".to_string(),
534                1.,
535            ),
536            (
537                Arc::new(LocalSearch::new(Arc::new(ExchangeIntraRouteRandom::default()))),
538                "local_exch_intra_route_random".to_string(),
539                1.,
540            ),
541            (
542                Arc::new(LocalSearch::new(Arc::new(RescheduleDeparture::default()))),
543                "local_reschedule_departure".to_string(),
544                1.,
545            ),
546            (
547                Arc::new(LocalSearch::new(Arc::new(ExchangeSwapStar::new(
548                    environment.random.clone(),
549                    SINGLE_HEURISTIC_QUOTA_LIMIT,
550                )))),
551                "local_swap_star".to_string(),
552                10.,
553            ),
554            // decompose search methods with different inner heuristic
555            (
556                create_variable_search_decompose_search(problem.clone(), environment.clone()),
557                "decompose_search_var".to_string(),
558                25.,
559            ),
560            (create_composite_decompose_search(problem, environment), "decompose_search_com".to_string(), 25.),
561        ]
562    }
563
564    pub fn get_operators(
565        problem: Arc<Problem>,
566        environment: Arc<Environment>,
567    ) -> Vec<(TargetSearchOperator, String, Float)> {
568        let (normal_limits, small_limits) = get_limits(problem.as_ref());
569        let random = environment.random.clone();
570
571        // NOTE: consider checking usage of names within heuristic filter before changing them
572
573        let recreates = get_recreates(problem.as_ref(), random.clone());
574
575        let ruins = get_ruins_with_limits(normal_limits.clone(), "normal")
576            .into_iter()
577            .chain(get_ruins_with_limits(small_limits.clone(), "small"))
578            .chain(get_ruins(problem.clone()))
579            .collect::<Vec<_>>();
580
581        let extra_random_job = Arc::new(RandomJobRemoval::new(small_limits));
582
583        // NOTE we need to wrap any of ruin methods in composite which calls restore context before recreate
584        let ruins = ruins
585            .into_iter()
586            .map::<(Arc<dyn Ruin>, String, Float), _>(|(ruin, name, weight)| {
587                (Arc::new(CompositeRuin::new(vec![(ruin, 1.), (extra_random_job.clone(), 0.1)])), name, weight)
588            })
589            .collect::<Vec<_>>();
590
591        let mutations = get_mutations(problem.clone(), environment.clone());
592
593        let heuristic_filter = problem.extras.get_heuristic_filter();
594
595        recreates
596            .iter()
597            .flat_map(|(recreate, recreate_name)| {
598                ruins.iter().map::<(TargetSearchOperator, String, Float), _>(move |(ruin, ruin_name, weight)| {
599                    (
600                        Arc::new(RuinAndRecreate::new(ruin.clone(), recreate.clone())),
601                        format!("{ruin_name}+{recreate_name}"),
602                        *weight,
603                    )
604                })
605            })
606            .chain(mutations)
607            .filter(|(_, name, _)| heuristic_filter.as_ref().map_or(true, |filter| (filter)(name.as_str())))
608            .collect::<Vec<_>>()
609    }
610
611    pub fn create_default_inner_ruin_recreate(
612        problem: Arc<Problem>,
613        environment: Arc<Environment>,
614    ) -> Arc<RuinAndRecreate> {
615        let (_, small_limits) = get_limits(problem.as_ref());
616        let random = environment.random.clone();
617
618        // initialize recreate
619        let cheapest = Arc::new(RecreateWithCheapest::new(random.clone()));
620        let recreate = Arc::new(WeightedRecreate::new(vec![
621            (cheapest.clone(), 1),
622            (Arc::new(RecreateWithSkipBest::new(1, 2, random.clone())), 1),
623            (Arc::new(RecreateWithPerturbation::new_with_defaults(random.clone())), 1),
624            (Arc::new(RecreateWithSkipBest::new(3, 4, random.clone())), 1),
625            (Arc::new(RecreateWithGaps::new(2, 20, random.clone())), 1),
626            (Arc::new(RecreateWithBlinks::new_with_defaults(random.clone())), 1),
627            (Arc::new(RecreateWithFarthest::new(random.clone())), 1),
628            (Arc::new(RecreateWithSlice::new(random.clone())), 1),
629            (Arc::new(RecreateWithSkipRandom::default_explorative_phased(cheapest, random.clone())), 1),
630        ]));
631
632        // initialize ruin
633        let random_route = Arc::new(RandomRouteRemoval::new(small_limits.clone()));
634        let random_job = Arc::new(RandomJobRemoval::new(small_limits.clone()));
635        let random_ruin = Arc::new(WeightedRuin::new(vec![
636            (vec![(random_job.clone(), 1.)], 10),
637            (vec![(random_route.clone(), 1.)], 1),
638        ]));
639
640        let ruin = Arc::new(WeightedRuin::new(vec![
641            (
642                vec![
643                    (Arc::new(AdjustedStringRemoval::new_with_defaults(small_limits.clone())), 1.),
644                    (random_ruin.clone(), 0.1),
645                ],
646                1,
647            ),
648            (vec![(Arc::new(NeighbourRemoval::new(small_limits.clone())), 1.), (random_ruin.clone(), 0.1)], 1),
649            (vec![(Arc::new(WorstJobRemoval::new(4, small_limits)), 1.), (random_ruin, 0.1)], 1),
650            (vec![(random_job, 1.), (random_route, 0.1)], 1),
651        ]));
652
653        Arc::new(RuinAndRecreate::new(ruin, recreate))
654    }
655
656    pub fn create_default_local_search(random: Arc<dyn Random>) -> Arc<LocalSearch> {
657        Arc::new(LocalSearch::new(Arc::new(CompositeLocalOperator::new(
658            vec![
659                (Arc::new(ExchangeSwapStar::new(random, SINGLE_HEURISTIC_QUOTA_LIMIT / 4)), 2),
660                (Arc::new(ExchangeInterRouteBest::default()), 1),
661                (Arc::new(ExchangeInterRouteRandom::default()), 1),
662                (Arc::new(ExchangeIntraRouteRandom::default()), 1),
663                (Arc::new(ExchangeSequence::default()), 1),
664            ],
665            1,
666            1,
667        ))))
668    }
669
670    fn create_variable_search_decompose_search(
671        problem: Arc<Problem>,
672        environment: Arc<Environment>,
673    ) -> TargetSearchOperator {
674        Arc::new(DecomposeSearch::new(
675            Arc::new(WeightedHeuristicOperator::new(
676                vec![
677                    create_default_inner_ruin_recreate(problem.clone(), environment.clone()),
678                    create_default_local_search(environment.random.clone()),
679                ],
680                vec![10, 1],
681            )),
682            (2, 4),
683            2,
684            SINGLE_HEURISTIC_QUOTA_LIMIT,
685        ))
686    }
687
688    fn create_composite_decompose_search(problem: Arc<Problem>, environment: Arc<Environment>) -> TargetSearchOperator {
689        let limits = RemovalLimits { removed_activities_range: (10..100), affected_routes_range: 1..1 };
690        let route_removal_operator =
691            Arc::new(RuinAndRecreate::new(Arc::new(RandomRouteRemoval::new(limits)), Arc::new(DummyRecreate)));
692
693        Arc::new(DecomposeSearch::new(
694            Arc::new(CompositeHeuristicOperator::new(vec![
695                (route_removal_operator, 1.),
696                (create_default_inner_ruin_recreate(problem.clone(), environment.clone()), 1.),
697            ])),
698            (2, 4),
699            2,
700            SINGLE_HEURISTIC_QUOTA_LIMIT,
701        ))
702    }
703}
704
705fn get_recreate_with_alternative_goal<T, F>(
706    original_goal: &GoalContext,
707    recreate_fn: F,
708) -> impl Iterator<Item = Arc<dyn Recreate>> + '_
709where
710    T: Recreate + Send + Sync + 'static,
711    F: Fn() -> T + 'static,
712{
713    original_goal
714        .get_alternatives()
715        .map::<Arc<dyn Recreate>, _>(move |goal| Arc::new(RecreateWithGoal::new(Arc::new(goal), recreate_fn())))
716}
vrp_core/solver/heuristic.rs

vrp_core/solver/
heuristic.rs
