vrp_core/construction/enablers/
reserved_time.rs

1#[cfg(test)]
2#[path = "../../../tests/unit/construction/enablers/reserved_time_test.rs"]
3mod reserved_time_test;
4
5use crate::models::common::*;
6use crate::models::problem::{ActivityCost, Actor, TransportCost, TravelTime};
7use crate::models::solution::{Activity, Route};
8use rosomaxa::prelude::{Float, GenericError};
9use std::collections::HashMap;
10use std::sync::Arc;
11
12/// Represent a reserved time span entity.
13#[derive(Clone, Debug)]
14pub struct ReservedTimeSpan {
15    /// A specific time span when an extra reserved duration should be applied.
16    pub time: TimeSpan,
17    /// An extra duration to be applied at given time.
18    pub duration: Duration,
19}
20
21impl ReservedTimeSpan {
22    /// Converts `ReservedTimeSpan` to `ReservedTimeWindow`.
23    pub fn to_reserved_time_window(&self, offset: Timestamp) -> ReservedTimeWindow {
24        ReservedTimeWindow { time: self.time.to_time_window(offset), duration: self.duration }
25    }
26}
27
28/// Represent a reserved time window entity.
29#[derive(Clone, Debug)]
30pub struct ReservedTimeWindow {
31    /// A specific time window when an extra reserved duration should be applied.
32    pub time: TimeWindow,
33    /// An extra duration to be applied at given time.
34    pub duration: Duration,
35}
36
37/// Specifies reserved time index type.
38pub type ReservedTimesIndex = HashMap<Arc<Actor>, Vec<ReservedTimeSpan>>;
39
40/// Specifies a function which returns an extra reserved time window for given actor. This reserved
41/// time should be considered for planning.
42pub(crate) type ReservedTimesFn = Arc<dyn Fn(&Route, &TimeWindow) -> Option<ReservedTimeWindow> + Send + Sync>;
43
44/// Provides way to calculate activity costs which might contain reserved time.
45pub struct DynamicActivityCost {
46    reserved_times_fn: ReservedTimesFn,
47}
48
49impl DynamicActivityCost {
50    /// Creates a new instance of `DynamicActivityCost` with given reserved time function.
51    pub fn new(reserved_times_index: ReservedTimesIndex) -> Result<Self, GenericError> {
52        Ok(Self { reserved_times_fn: create_reserved_times_fn(reserved_times_index)? })
53    }
54}
55
56impl ActivityCost for DynamicActivityCost {
57    fn estimate_departure(&self, route: &Route, activity: &Activity, arrival: Timestamp) -> Timestamp {
58        let activity_start = arrival.max(activity.place.time.start);
59        let departure = activity_start + activity.place.duration;
60        let schedule = TimeWindow::new(arrival, departure);
61
62        (self.reserved_times_fn)(route, &schedule).map_or(departure, |reserved_time| {
63            // NOTE we ignore reserved_time.time.start and consider the latest possible time only
64            let reserved_tw = &reserved_time.time;
65            let reserved_tw = TimeWindow::new(reserved_tw.end, reserved_tw.end + reserved_time.duration);
66
67            assert!(reserved_tw.intersects(&schedule));
68
69            let activity_tw = &activity.place.time;
70
71            let extra_duration = if reserved_tw.start < activity_tw.start {
72                let waiting_time = TimeWindow::new(arrival, activity_tw.start);
73                let overlapping = waiting_time.overlapping(&reserved_tw).map(|tw| tw.duration()).unwrap_or(0.);
74
75                reserved_time.duration - overlapping
76            } else {
77                reserved_time.duration
78            };
79
80            // NOTE: do not allow to start or restart work after break finished
81            if activity_start + extra_duration > activity.place.time.end {
82                // TODO this branch is the reason why departure rescheduling is disabled.
83                //      theoretically, rescheduling should be aware somehow about dynamic costs
84                Float::MAX
85            } else {
86                departure + extra_duration
87            }
88        })
89    }
90
91    fn estimate_arrival(&self, route: &Route, activity: &Activity, departure: Timestamp) -> Timestamp {
92        let arrival = activity.place.time.end.min(departure - activity.place.duration);
93        let schedule = TimeWindow::new(arrival, departure);
94
95        (self.reserved_times_fn)(route, &schedule)
96            .map_or(arrival, |reserved_time| (arrival - reserved_time.duration).max(activity.place.time.start))
97    }
98}
99
100/// Provides way to calculate transport costs which might contain reserved time.
101pub struct DynamicTransportCost {
102    reserved_times_fn: ReservedTimesFn,
103    inner: Arc<dyn TransportCost>,
104}
105
106impl DynamicTransportCost {
107    /// Creates a new instance of `DynamicTransportCost`.
108    pub fn new(reserved_times_index: ReservedTimesIndex, inner: Arc<dyn TransportCost>) -> Result<Self, GenericError> {
109        Ok(Self { reserved_times_fn: create_reserved_times_fn(reserved_times_index)?, inner })
110    }
111}
112
113impl TransportCost for DynamicTransportCost {
114    fn duration_approx(&self, profile: &Profile, from: Location, to: Location) -> Duration {
115        self.inner.duration_approx(profile, from, to)
116    }
117
118    fn distance_approx(&self, profile: &Profile, from: Location, to: Location) -> Distance {
119        self.inner.distance_approx(profile, from, to)
120    }
121
122    fn duration(&self, route: &Route, from: Location, to: Location, travel_time: TravelTime) -> Duration {
123        let duration = self.inner.duration(route, from, to, travel_time);
124
125        let time_window = match travel_time {
126            TravelTime::Arrival(arrival) => TimeWindow::new(arrival - duration, arrival),
127            TravelTime::Departure(departure) => TimeWindow::new(departure, departure + duration),
128        };
129
130        (self.reserved_times_fn)(route, &time_window)
131            .map_or(duration, |reserved_time| duration + reserved_time.duration)
132    }
133
134    fn distance(&self, route: &Route, from: Location, to: Location, travel_time: TravelTime) -> Distance {
135        self.inner.distance(route, from, to, travel_time)
136    }
137}
138
139/// Optimizes reserved time schedules by rescheduling it to earlier time (e.g. to avoid transit stops,
140/// reduce waiting time).
141pub(crate) fn optimize_reserved_times_schedule(route: &mut Route, reserved_times_fn: &ReservedTimesFn) {
142    // NOTE run in this order as reducing waiting time can be also applied on top of avoiding travel time
143    avoid_reserved_time_when_driving(route, reserved_times_fn);
144    reduce_waiting_by_reserved_time(route, reserved_times_fn);
145}
146
147fn avoid_reserved_time_when_driving(route: &mut Route, reserved_times_fn: &ReservedTimesFn) {
148    // NOTE assume reserved times has no intersection
149    let schedule_shifts = route
150        .tour
151        .legs()
152        .filter_map(|(leg, idx)| match &leg {
153            &[from, to] => Some((from, to, idx)),
154            _ => None,
155        })
156        .filter_map(|(from, to, idx)| {
157            let travel_tw = TimeWindow::new(from.schedule.departure, to.schedule.arrival);
158            reserved_times_fn(route, &travel_tw).map(|reserved_time| (idx, from, reserved_time))
159        })
160        .filter(|(_, from, reserved_time)| from.schedule.departure > reserved_time.time.start)
161        .map(|(idx, _, reserved_time)| (idx, reserved_time.duration))
162        .collect::<Vec<_>>();
163
164    schedule_shifts.into_iter().for_each(|(idx, duration)| {
165        route.tour.get_mut(idx).unwrap().schedule.departure += duration;
166    });
167}
168
169fn reduce_waiting_by_reserved_time(_route: &mut Route, _reserved_times_fn: &ReservedTimesFn) {
170    // TODO: could be added if necessary, but it should be thought carefully to keep solution feasibility
171}
172
173/// Creates a reserved time function from reserved time index.
174pub(crate) fn create_reserved_times_fn(
175    reserved_times_index: ReservedTimesIndex,
176) -> Result<ReservedTimesFn, GenericError> {
177    if reserved_times_index.is_empty() {
178        return Ok(Arc::new(|_, _| None));
179    }
180
181    let reserved_times = reserved_times_index.into_iter().try_fold(
182        HashMap::<_, (Vec<_>, Vec<_>)>::new(),
183        |mut acc, (actor, mut times)| {
184            // NOTE do not allow different types to simplify interval searching
185            let are_same_types = times.windows(2).all(|pair| {
186                if let [ReservedTimeSpan { time: a, .. }, ReservedTimeSpan { time: b, .. }] = pair {
187                    matches!(
188                        (a, b),
189                        (TimeSpan::Window(_), TimeSpan::Window(_)) | (TimeSpan::Offset(_), TimeSpan::Offset(_))
190                    )
191                } else {
192                    false
193                }
194            });
195
196            if !are_same_types {
197                return Err("has reserved types of different time span types".to_string());
198            }
199
200            times.sort_by(|ReservedTimeSpan { time: a, .. }, ReservedTimeSpan { time: b, .. }| {
201                let (a, b) = match (a, b) {
202                    (TimeSpan::Window(a), TimeSpan::Window(b)) => (a.start, b.start),
203                    (TimeSpan::Offset(a), TimeSpan::Offset(b)) => (a.start, b.start),
204                    _ => unreachable!(),
205                };
206                a.total_cmp(&b)
207            });
208            let has_no_intersections = times.windows(2).all(|pair| {
209                if let [ReservedTimeSpan { time: a, .. }, ReservedTimeSpan { time: b, .. }] = pair {
210                    !a.intersects(0., &b.to_time_window(0.))
211                } else {
212                    false
213                }
214            });
215
216            if has_no_intersections {
217                let (indices, intervals): (Vec<_>, Vec<_>) = times
218                    .into_iter()
219                    .map(|span| {
220                        let start = match &span.time {
221                            TimeSpan::Window(time) => time.end,
222                            TimeSpan::Offset(time) => time.end,
223                        };
224
225                        (start as u64, span)
226                    })
227                    .unzip();
228                acc.insert(actor, (indices, intervals));
229
230                Ok(acc)
231            } else {
232                Err("reserved times have intersections".to_string())
233            }
234        },
235    )?;
236
237    // NOTE: this function considers only latest time from reserved time
238    //       reserved_time.time.start is ignored and should be handled by post processing
239    Ok(Arc::new(move |route: &Route, time_window: &TimeWindow| {
240        reserved_times.get(&route.actor).and_then(|(indices, intervals)| {
241            let offset = route.tour.start().map(|a| a.schedule.departure).unwrap_or(0.);
242
243            // NOTE map external absolute time window to time span's start/end
244            let (interval_start, interval_end) = match intervals.first().map(|rt| &rt.time) {
245                Some(TimeSpan::Offset(_)) => (time_window.start - offset, time_window.end - offset),
246                Some(TimeSpan::Window(_)) => (time_window.start, time_window.end),
247                _ => unreachable!(),
248            };
249
250            match indices.binary_search(&(interval_start as u64)) {
251                Ok(idx) => intervals.get(idx),
252                Err(idx) => (idx.max(1) - 1..=idx) // NOTE left (earliest) wins
253                    .map(|idx| intervals.get(idx))
254                    .find(|reserved_time| {
255                        reserved_time.map_or(false, |reserved_time| {
256                            let (reserved_start, reserved_end) = match &reserved_time.time {
257                                TimeSpan::Offset(to) => (to.end, to.end + reserved_time.duration),
258                                TimeSpan::Window(tw) => (tw.end, tw.end + reserved_time.duration),
259                            };
260
261                            // NOTE use exclusive intersection
262                            interval_start < reserved_end && reserved_start < interval_end
263                        })
264                    })
265                    .flatten(),
266            }
267            .map(|reserved_time| reserved_time.to_reserved_time_window(offset))
268        })
269    }))
270}
vrp_core/construction/enablers/reserved_time.rs

vrp_core/construction/enablers/
reserved_time.rs
