vrp_core/solver/processing/
vicinity_clustering.rs

1#[cfg(test)]
2#[path = "../../../tests/unit/solver/processing/vicinity_clustering_test.rs"]
3mod vicinity_clustering_test;
4
5use super::*;
6use crate::construction::clustering::vicinity::*;
7use crate::models::common::Schedule;
8use crate::models::problem::Jobs;
9use crate::models::solution::{Activity, Place};
10use crate::models::{Extras, GoalContext, Problem};
11use crate::solver::RefinementContext;
12use std::collections::HashSet;
13use std::sync::Arc;
14
15custom_extra_property!(ClusterConfig typeof ClusterConfig);
16custom_extra_property!(OriginalProblem typeof Problem);
17
18/// Provides a way to change problem definition by reducing total job count using clustering.
19#[derive(Default)]
20pub struct VicinityClustering {}
21
22impl HeuristicContextProcessing for VicinityClustering {
23    type Context = RefinementContext;
24    type Objective = GoalContext;
25    type Solution = InsertionContext;
26
27    fn pre_process(&self, context: Self::Context) -> Self::Context {
28        let problem = context.problem.clone();
29        let environment = context.environment.clone();
30        let logger = environment.logger.clone();
31
32        let config = if let Some(config) = problem.extras.get_cluster_config() { config } else { return context };
33
34        let clusters = create_job_clusters(problem.clone(), environment, &config);
35
36        if clusters.is_empty() {
37            context
38        } else {
39            let (clusters, clustered_jobs) = clusters.into_iter().fold(
40                (Vec::new(), HashSet::new()),
41                |(mut clusters, mut clustered_jobs), (cluster, cluster_jobs)| {
42                    clusters.push(cluster);
43                    clustered_jobs.extend(cluster_jobs);
44
45                    (clusters, clustered_jobs)
46                },
47            );
48
49            let jobs = problem
50                .jobs
51                .all()
52                .iter()
53                .filter(|job| !clustered_jobs.contains(job))
54                .cloned()
55                .chain(clusters)
56                .collect();
57
58            let mut extras: Extras = problem.extras.as_ref().clone();
59            extras.set_original_problem(problem.clone());
60
61            let problem = Arc::new(Problem {
62                fleet: problem.fleet.clone(),
63                jobs: Arc::new(Jobs::new(problem.fleet.as_ref(), jobs, problem.transport.as_ref(), &logger).unwrap()),
64                locks: problem.locks.clone(),
65                goal: problem.goal.clone(),
66                activity: problem.activity.clone(),
67                transport: problem.transport.clone(),
68                extras: Arc::new(extras),
69            });
70
71            RefinementContext { problem, ..context }
72        }
73    }
74}
75
76impl HeuristicSolutionProcessing for VicinityClustering {
77    type Solution = InsertionContext;
78
79    fn post_process(&self, solution: Self::Solution) -> Self::Solution {
80        let mut insertion_ctx = solution;
81
82        let config = insertion_ctx.problem.extras.get_cluster_config();
83        let orig_problem = insertion_ctx.problem.extras.get_original_problem();
84
85        let (config, orig_problem) = if let Some((config, orig_problem)) = config.zip(orig_problem) {
86            (config, orig_problem)
87        } else {
88            return insertion_ctx;
89        };
90
91        insertion_ctx.solution.routes.iter_mut().for_each(|route_ctx| {
92            #[allow(clippy::needless_collect)]
93            let clusters = route_ctx
94                .route()
95                .tour
96                .all_activities()
97                .enumerate()
98                .filter_map(|(idx, activity)| {
99                    activity
100                        .retrieve_job()
101                        .and_then(|job| job.dimens().get_cluster_info().cloned())
102                        .map(|cluster| (idx, cluster))
103                })
104                .collect::<Vec<_>>();
105
106            clusters.into_iter().rev().for_each(|(activity_idx, cluster)| {
107                let cluster_activity = route_ctx.route().tour.get(activity_idx).unwrap();
108                let cluster_time = cluster_activity.place.time.clone();
109                let cluster_arrival = cluster_activity.schedule.arrival;
110                let last_job = cluster.last().unwrap().job.clone();
111
112                let (_, activities) =
113                    cluster.into_iter().fold((cluster_arrival, Vec::new()), |(arrival, mut activities), info| {
114                        // NOTE assumption: no waiting time possible in between of clustered jobs
115                        let job = info.job.to_single().clone();
116                        let place_idx = 0;
117                        let place = &job.places[place_idx];
118
119                        let backward = match config.visiting {
120                            VisitPolicy::Return => info.commute.backward.duration,
121                            VisitPolicy::ClosedContinuation if info.job == last_job => info.commute.backward.duration,
122                            _ => 0.,
123                        };
124
125                        let service_time = info.service_time;
126                        let service_start = (arrival + info.commute.forward.duration).max(cluster_time.start);
127                        let departure = service_start + service_time + backward;
128
129                        activities.push(Activity {
130                            place: Place {
131                                idx: place_idx,
132                                location: place.location.unwrap(),
133                                duration: info.service_time,
134                                time: cluster_time.clone(),
135                            },
136                            schedule: Schedule::new(arrival, departure),
137                            job: Some(job),
138                            commute: Some(info.commute),
139                        });
140
141                        (departure, activities)
142                    });
143
144                route_ctx.route_mut().tour.remove_activity_at(activity_idx);
145                activities.into_iter().enumerate().for_each(|(seq_idx, activity)| {
146                    route_ctx.route_mut().tour.insert_at(activity, activity_idx + seq_idx);
147                });
148            });
149        });
150
151        insertion_ctx.solution.unassigned = insertion_ctx
152            .solution
153            .unassigned
154            .iter()
155            .flat_map(|(job, code)| {
156                job.dimens()
157                    .get_cluster_info()
158                    .map(|clusters| clusters.iter().map(|info| (info.job.clone(), code.clone())).collect::<Vec<_>>())
159                    .unwrap_or_else(|| vec![(job.clone(), code.clone())])
160                    .into_iter()
161            })
162            .collect();
163
164        insertion_ctx.problem = orig_problem.clone();
165
166        insertion_ctx
167    }
168}
vrp_core/solver/processing/vicinity_clustering.rs

vrp_core/solver/processing/
vicinity_clustering.rs
