vrp-core 1.25.0

A core algorithms to solve a Vehicle Routing Problem
Documentation 
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

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

use crate::construction::enablers::*;
use crate::construction::heuristics::RouteContext;
use crate::models::common::Timestamp;
use crate::models::problem::{ActivityCost, TransportCost, TravelTime};
use rosomaxa::prelude::Float;

/// Tries to move forward route's departure time.
pub fn advance_departure_time(
    route_ctx: &mut RouteContext,
    activity: &(dyn ActivityCost),
    transport: &(dyn TransportCost),
    consider_whole_tour: bool,
) {
    if let Some(new_departure_time) = try_advance_departure_time(route_ctx, transport, consider_whole_tour) {
        update_route_departure(route_ctx, activity, transport, new_departure_time);
    }
}

/// Tries to move backward route's departure time.
pub fn recede_departure_time(
    route_ctx: &mut RouteContext,
    activity: &(dyn ActivityCost),
    transport: &(dyn TransportCost),
) {
    if let Some(new_departure_time) = try_recede_departure_time(route_ctx) {
        update_route_departure(route_ctx, activity, transport, new_departure_time);
    }
}

fn try_advance_departure_time(
    route_ctx: &RouteContext,
    transport: &(dyn TransportCost),
    optimize_whole_tour: bool,
) -> Option<Timestamp> {
    let route = route_ctx.route();

    let first = route.tour.get(1)?;
    let start = route.tour.start()?;

    let latest_allowed_departure = route.actor.detail.start.as_ref().and_then(|s| s.time.latest).unwrap_or(Float::MAX);
    let last_departure_time = start.schedule.departure;

    let new_departure_time = if optimize_whole_tour {
        let (total_waiting_time, max_shift) =
            route.tour.all_activities().rev().fold((0., Float::MAX), |(total_waiting_time, max_shift), activity| {
                let waiting_time = (activity.place.time.start - activity.schedule.arrival).max(0.);
                let remaining_time = (activity.place.time.end - activity.schedule.arrival - waiting_time).max(0.);

                (total_waiting_time + waiting_time, waiting_time + remaining_time.min(max_shift))
            });
        let departure_shift = total_waiting_time.min(max_shift);

        (start.schedule.departure + departure_shift).min(latest_allowed_departure)
    } else {
        let start_to_first = transport.duration(
            route,
            start.place.location,
            first.place.location,
            TravelTime::Departure(last_departure_time),
        );

        #[allow(clippy::manual_clamp)]
        last_departure_time.max(first.place.time.start - start_to_first).min(latest_allowed_departure)
    };

    if new_departure_time > last_departure_time {
        Some(new_departure_time)
    } else {
        None
    }
}

fn try_recede_departure_time(route_ctx: &RouteContext) -> Option<Timestamp> {
    let first = route_ctx.route().tour.get(1)?;
    let start = route_ctx.route().tour.start()?;

    let max_change = *route_ctx.state().get_latest_arrival_at(1)? - first.schedule.arrival;

    let earliest_allowed_departure =
        route_ctx.route().actor.detail.start.as_ref().and_then(|s| s.time.earliest).unwrap_or(start.place.time.start);

    let max_change = (start.schedule.departure - earliest_allowed_departure).min(max_change);

    let max_change = route_ctx
        .state()
        .get_total_duration()
        .zip(route_ctx.state().get_limit_duration())
        .map(|(&total, &limit)| (limit - total).min(max_change))
        .unwrap_or(max_change);

    if max_change > 0. {
        Some(start.schedule.departure - max_change)
    } else {
        None
    }
}