vrp_core/construction/features/
tour_compactness.rs

1#[cfg(test)]
2#[path = "../../../tests/unit/construction/features/tour_compactness_test.rs"]
3mod tour_compactness_test;
4
5use super::*;
6
7custom_solution_state!(TourCompactness typeof Cost);
8
9/// Creates a feature which tries to keep routes compact by reducing amount of jobs in their
10/// neighbourhood served by different routes.
11///
12/// `job_radius` controls amount of jobs checked in neighbourhood of a tested one.
13pub fn create_tour_compactness_feature(
14    name: &str,
15    jobs: Arc<Jobs>,
16    job_radius: usize,
17) -> Result<Feature, GenericError> {
18    if job_radius < 1 {
19        return Err("Tour compactness: job radius should be at least 1".into());
20    }
21
22    FeatureBuilder::default()
23        .with_name(name)
24        .with_objective(TourCompactnessObjective { jobs: jobs.clone(), job_radius })
25        .with_state(TourCompactnessState { jobs, job_radius })
26        .build()
27}
28
29struct TourCompactnessObjective {
30    jobs: Arc<Jobs>,
31    job_radius: usize,
32}
33
34impl FeatureObjective for TourCompactnessObjective {
35    fn fitness(&self, solution: &InsertionContext) -> Cost {
36        solution.solution.state.get_tour_compactness().copied().unwrap_or_default()
37    }
38
39    fn estimate(&self, move_ctx: &MoveContext<'_>) -> Cost {
40        match move_ctx {
41            MoveContext::Route { solution_ctx, route_ctx, job } => {
42                count_shared_neighbours((solution_ctx, route_ctx, job), &self.jobs, self.job_radius) as Cost
43            }
44            MoveContext::Activity { .. } => Cost::default(),
45        }
46    }
47}
48
49struct TourCompactnessState {
50    jobs: Arc<Jobs>,
51    job_radius: usize,
52}
53
54impl FeatureState for TourCompactnessState {
55    fn accept_insertion(&self, _: &mut SolutionContext, _: usize, _: &Job) {}
56
57    fn accept_route_state(&self, _: &mut RouteContext) {}
58
59    fn accept_solution_state(&self, solution_ctx: &mut SolutionContext) {
60        let fitness = solution_ctx.routes.iter().fold(Cost::default(), |acc, route_ctx| {
61            acc + route_ctx
62                .route()
63                .tour
64                .jobs()
65                .map(|job| count_shared_neighbours((solution_ctx, route_ctx, job), &self.jobs, self.job_radius))
66                .sum::<usize>() as Cost
67        }) / 2.;
68
69        solution_ctx.state.set_tour_compactness(fitness);
70    }
71}
72
73fn count_shared_neighbours(item: (&SolutionContext, &RouteContext, &Job), jobs: &Jobs, job_radius: usize) -> usize {
74    let (solution_ctx, route_ctx, job) = item;
75
76    let route = route_ctx.route();
77    let departure = route.tour.start().map_or(Timestamp::default(), |s| s.schedule.departure);
78
79    jobs.neighbors(&route.actor.vehicle.profile, job, departure)
80        .take(job_radius)
81        .filter(|(j, _)| {
82            let not_current = !route.tour.has_job(j);
83            let is_assigned = !solution_ctx.required.contains(j);
84
85            not_current && is_assigned
86        })
87        .count()
88}
vrp_core/construction/features/tour_compactness.rs

vrp_core/construction/features/
tour_compactness.rs
