vrp_core/construction/features/
tour_order.rs

1//! Provides way to enforce job activity ordering in the tour.
2
3#[cfg(test)]
4#[path = "../../../tests/unit/construction/features/tour_order_test.rs"]
5mod tour_order_test;
6
7use super::*;
8use crate::models::problem::{Actor, Single};
9use crate::models::solution::Activity;
10use crate::utils::Either;
11use std::cmp::Ordering;
12use std::ops::ControlFlow;
13
14custom_solution_state!(TourOrderViolations typeof usize);
15
16/// Creates a tour order feature as hard constraint.
17pub fn create_tour_order_hard_feature(
18    name: &str,
19    code: ViolationCode,
20    order_fn: TourOrderFn,
21) -> Result<Feature, GenericError> {
22    FeatureBuilder::default().with_name(name).with_constraint(TourOrderConstraint { code, order_fn }).build()
23}
24
25/// Creates a tour order as soft constraint.
26pub fn create_tour_order_soft_feature(name: &str, order_fn: TourOrderFn) -> Result<Feature, GenericError> {
27    FeatureBuilder::default()
28        .with_name(name)
29        .with_objective(TourOrderObjective { order_fn: order_fn.clone() })
30        .with_state(TourOrderState { order_fn })
31        .build()
32}
33
34/// Specifies order result.
35#[derive(Copy, Clone)]
36pub enum OrderResult {
37    /// Returns a specified value.
38    Value(Float),
39    /// No value specified.
40    Default,
41    /// No value specified, but constraint should be ignored
42    Ignored,
43}
44
45/// Specifies an activity order function which takes into an account actor and single job.
46pub type ActorTourOrderFn = Arc<dyn Fn(&Actor, &Single) -> OrderResult + Send + Sync>;
47
48/// Specifies an activity order function which takes into account only a single job.
49pub type SingleTourOrderFn = Arc<dyn Fn(&Single) -> OrderResult + Send + Sync>;
50
51/// Specifies an order func as a variant of two functions.
52pub type TourOrderFn = Either<SingleTourOrderFn, ActorTourOrderFn>;
53
54struct TourOrderConstraint {
55    code: ViolationCode,
56    order_fn: TourOrderFn,
57}
58
59impl FeatureConstraint for TourOrderConstraint {
60    fn evaluate(&self, move_ctx: &MoveContext<'_>) -> Option<ConstraintViolation> {
61        match move_ctx {
62            MoveContext::Activity { route_ctx, activity_ctx } => {
63                evaluate_result(route_ctx, activity_ctx, &self.order_fn, &|first, second, stopped| {
64                    if compare_order_results(first, second) == Ordering::Greater {
65                        Some(ConstraintViolation { code: self.code, stopped })
66                    } else {
67                        None
68                    }
69                })
70            }
71            MoveContext::Route { .. } => None,
72        }
73    }
74
75    fn merge(&self, source: Job, candidate: Job) -> Result<Job, ViolationCode> {
76        match &self.order_fn {
77            Either::Left(order_fn) => {
78                let order_fn_cmp = |source: &Single, candidate: &Single| {
79                    let source = (order_fn)(source);
80                    let candidate = (order_fn)(candidate);
81                    match (source, candidate) {
82                        (OrderResult::Value(s), OrderResult::Value(c)) => s == c,
83                        (OrderResult::Default, OrderResult::Default) | (OrderResult::Ignored, OrderResult::Ignored) => {
84                            true
85                        }
86                        _ => false,
87                    }
88                };
89
90                match (&source, &candidate) {
91                    (Job::Single(s_source), Job::Single(s_candidate)) if order_fn_cmp(s_source, s_candidate) => {
92                        Ok(source)
93                    }
94                    _ => Err(self.code),
95                }
96            }
97            Either::Right(_) => Err(self.code),
98        }
99    }
100}
101
102struct TourOrderObjective {
103    order_fn: TourOrderFn,
104}
105
106impl FeatureObjective for TourOrderObjective {
107    fn fitness(&self, solution: &InsertionContext) -> Cost {
108        let solution = &solution.solution;
109
110        solution
111            .state
112            .get_tour_order_violations()
113            .copied()
114            .unwrap_or_else(|| get_violations(solution.routes.as_slice(), &self.order_fn)) as Float
115    }
116
117    fn estimate(&self, move_ctx: &MoveContext<'_>) -> Cost {
118        match move_ctx {
119            MoveContext::Activity { route_ctx, activity_ctx } => {
120                evaluate_result(route_ctx, activity_ctx, &self.order_fn, &|first, second, _| {
121                    if compare_order_results(first, second) == Ordering::Greater {
122                        let value = match (first, second) {
123                            (OrderResult::Value(first), OrderResult::Value(second)) => first - second,
124                            (OrderResult::Default, OrderResult::Value(value)) => -value,
125                            (OrderResult::Value(value), OrderResult::Default) => value,
126                            _ => Cost::default(),
127                        };
128
129                        Some(value)
130                    } else {
131                        None
132                    }
133                })
134                .unwrap_or_default()
135            }
136            MoveContext::Route { .. } => Cost::default(),
137        }
138    }
139}
140
141struct TourOrderState {
142    order_fn: TourOrderFn,
143}
144
145impl FeatureState for TourOrderState {
146    fn accept_insertion(&self, _: &mut SolutionContext, _: usize, _: &Job) {}
147
148    fn accept_route_state(&self, _: &mut RouteContext) {}
149
150    fn accept_solution_state(&self, solution_ctx: &mut SolutionContext) {
151        let violations = get_violations(solution_ctx.routes.as_slice(), &self.order_fn);
152        solution_ctx.state.set_tour_order_violations(violations);
153    }
154}
155
156fn evaluate_result<T>(
157    route_ctx: &RouteContext,
158    activity_ctx: &ActivityContext,
159    order_fn: &TourOrderFn,
160    check_order: &(dyn Fn(OrderResult, OrderResult, bool) -> Option<T>),
161) -> Option<T> {
162    let get_order = |single: &Single| match &order_fn {
163        Either::Left(left) => (left)(single),
164        Either::Right(right) => (right)(route_ctx.route().actor.as_ref(), single),
165    };
166
167    let target_order = activity_ctx.target.job.as_ref().map(|single| get_order(single)).unwrap_or(OrderResult::Ignored);
168
169    let get_order_by_idx = |idx: usize| {
170        route_ctx.route().tour.get(idx).and_then(get_single).map(get_order).unwrap_or(OrderResult::Ignored)
171    };
172
173    (0..=activity_ctx.index)
174        .map(get_order_by_idx)
175        .map(|early| (early, target_order, true))
176        .chain(
177            (activity_ctx.index + 1..route_ctx.route().tour.total())
178                .map(get_order_by_idx)
179                .map(|late| (target_order, late, false)),
180        )
181        .try_fold(None, |_, (left, right, stopped)| {
182            let result = (check_order)(left, right, stopped);
183            if result.is_some() {
184                ControlFlow::Break(result)
185            } else {
186                ControlFlow::Continue(None)
187            }
188        })
189        .unwrap_value()
190}
191
192fn get_violations(routes: &[RouteContext], order_fn: &TourOrderFn) -> usize {
193    routes
194        .iter()
195        .map(|route_ctx| {
196            let orders = route_ctx
197                .route()
198                .tour
199                .all_activities()
200                .filter_map(|activity| activity.job.as_ref())
201                .map(|single| match order_fn {
202                    Either::Left(left) => (left)(single.as_ref()),
203                    Either::Right(right) => (right)(route_ctx.route().actor.as_ref(), single.as_ref()),
204                })
205                .filter(|order| !matches!(order, OrderResult::Ignored))
206                .collect::<Vec<OrderResult>>();
207
208            orders.windows(2).fold(0_usize, |acc, pair| {
209                let value = match *pair {
210                    [prev, next] => match compare_order_results(prev, next) {
211                        Ordering::Greater => 1,
212                        _ => 0,
213                    },
214                    _ => unreachable!(),
215                };
216
217                acc + value
218            })
219        })
220        .sum::<usize>()
221}
222
223fn get_single(activity: &Activity) -> Option<&Single> {
224    activity.job.as_ref().map(|single| single.as_ref())
225}
226
227fn compare_order_results(left: OrderResult, right: OrderResult) -> Ordering {
228    match (left, right) {
229        (OrderResult::Value(left), OrderResult::Value(right)) => left.total_cmp(&right),
230        (OrderResult::Value(_), OrderResult::Default) => Ordering::Less,
231        (OrderResult::Default, OrderResult::Value(_)) => Ordering::Greater,
232        _ => Ordering::Equal,
233    }
234}
vrp_core/construction/features/tour_order.rs

vrp_core/construction/features/
tour_order.rs
