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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#[cfg(test)]
#[path = "../../../tests/unit/construction/heuristics/metrics_test.rs"]
mod metrics_test;

use super::InsertionContext;
use crate::algorithms::statistics::{get_mean, get_stdev, get_variance};
use crate::construction::constraints::{MAX_LOAD_KEY, TOTAL_DISTANCE_KEY, TOTAL_DURATION_KEY, WAITING_KEY};
use crate::construction::heuristics::RouteContext;
use crate::models::problem::TransportCost;
use crate::utils::compare_floats;
use std::cmp::Ordering;

/// Gets max load variance in tours.
pub fn get_max_load_variance(insertion_ctx: &InsertionContext) -> f64 {
    get_variance(get_values_from_route_state(insertion_ctx, MAX_LOAD_KEY).as_slice())
}

/// Gets standard deviation of the number of customer per tour.
pub fn get_customers_deviation(insertion_ctx: &InsertionContext) -> f64 {
    let values =
        insertion_ctx.solution.routes.iter().map(|route| route.route.tour.job_count() as f64).collect::<Vec<_>>();

    get_stdev(values.as_slice())
}

/// Gets mean of route durations.
pub fn get_duration_mean(insertion_ctx: &InsertionContext) -> f64 {
    get_mean(get_values_from_route_state(insertion_ctx, TOTAL_DURATION_KEY).as_slice())
}

/// Gets mean of route distances.
pub fn get_distance_mean(insertion_ctx: &InsertionContext) -> f64 {
    get_mean(get_values_from_route_state(insertion_ctx, TOTAL_DISTANCE_KEY).as_slice())
}

/// Gets mean of future waiting time.
pub fn get_waiting_mean(insertion_ctx: &InsertionContext) -> f64 {
    get_mean(
        insertion_ctx
            .solution
            .routes
            .iter()
            .filter_map(|route_ctx| route_ctx.route.tour.get(1).map(|a| (route_ctx, a)))
            .map(|(route_ctx, activity)| {
                route_ctx.state.get_activity_state::<f64>(WAITING_KEY, activity).cloned().unwrap_or(0.)
            })
            .collect::<Vec<_>>()
            .as_slice(),
    )
}

/// Gets average distance between routes using medoids.
pub fn get_distance_gravity_mean(insertion_ctx: &InsertionContext) -> f64 {
    let transport = insertion_ctx.problem.transport.as_ref();
    let profile = insertion_ctx.solution.routes.first().map(|route_ctx| &route_ctx.route.actor.vehicle.profile);

    if let Some(profile) = profile {
        let medoids = insertion_ctx
            .solution
            .routes
            .iter()
            .filter_map(|route_ctx| get_medoid(route_ctx, transport))
            .collect::<Vec<_>>();

        let mut distances = Vec::with_capacity(medoids.len() * 2);

        for i in 0..medoids.len() {
            for j in (i + 1)..medoids.len() {
                let distance = transport.distance(&profile, medoids[i], medoids[j], Default::default());
                // NOTE assume that negative distance is used between unroutable locations
                distances.push(distance.max(0.));
            }
        }

        get_mean(distances.as_slice())
    } else {
        0.
    }
}

/// Gets medoid location of given route context.
pub fn get_medoid(route_ctx: &RouteContext, transport: &(dyn TransportCost + Send + Sync)) -> Option<usize> {
    let locations = route_ctx.route.tour.all_activities().map(|activity| activity.place.location).collect::<Vec<_>>();
    locations
        .iter()
        .map(|outer_loc| {
            let sum = locations
                .iter()
                .map(|inner_loc| {
                    transport.distance(
                        &route_ctx.route.actor.vehicle.profile,
                        *outer_loc,
                        *inner_loc,
                        Default::default(),
                    )
                })
                .sum::<f64>();
            (sum, *outer_loc)
        })
        .min_by(|(sum_a, _), (sum_b, _)| compare_floats(*sum_a, *sum_b))
        .map(|(_, location)| location)
}

/// A type which represents routes grouped by their proximity.
pub type RouteProximityGroup = Option<Vec<Vec<(usize, Option<f64>)>>>;

/// Estimates distances between all routes using their medoids and returns the sorted groups.
pub fn group_routes_by_proximity(insertion_ctx: &InsertionContext) -> RouteProximityGroup {
    let solution = &insertion_ctx.solution;
    let profile = &solution.routes.first().map(|route_ctx| &route_ctx.route.actor.vehicle.profile)?;
    let transport = insertion_ctx.problem.transport.as_ref();

    let indexed_medoids = solution
        .routes
        .iter()
        .enumerate()
        .map(|(idx, route_ctx)| (idx, get_medoid(route_ctx, transport)))
        .collect::<Vec<_>>();

    Some(
        indexed_medoids
            .iter()
            .map(|(outer_idx, outer_medoid)| {
                let mut route_distances = indexed_medoids
                    .iter()
                    .filter(move |(inner_idx, _)| *outer_idx != *inner_idx)
                    .map(move |(inner_idx, inner_medoid)| {
                        let distance = match (outer_medoid, inner_medoid) {
                            (Some(outer_medoid), Some(inner_medoid)) => {
                                let distance =
                                    transport.distance(profile, *outer_medoid, *inner_medoid, Default::default());
                                if distance < 0. {
                                    None
                                } else {
                                    Some(distance)
                                }
                            }
                            _ => None,
                        };
                        (*inner_idx, distance)
                    })
                    .collect::<Vec<_>>();

                route_distances.sort_by(|(_, a_distance), (_, b_distance)| match (a_distance, b_distance) {
                    (Some(a_distance), Some(b_distance)) => compare_floats(*a_distance, *b_distance),
                    (Some(_), None) => Ordering::Less,
                    _ => Ordering::Greater,
                });

                route_distances
            })
            .collect::<Vec<_>>(),
    )
}

fn get_values_from_route_state(insertion_ctx: &InsertionContext, state_key: i32) -> Vec<f64> {
    insertion_ctx
        .solution
        .routes
        .iter()
        .map(|route| route.state.get_route_state::<f64>(state_key).cloned().unwrap_or(0.))
        .collect()
}