custom_constraint/
custom_constraint.rs

1//! This example demonstrates how to add a custom hard constraint to a CVRP variant.
2//!
3//! Here, we introduce a hardware requirement of a job so that only vehicles with matching
4//! hardware capabilities can be used to serve it.
5//!
6//! Key points of implementation:
7//! - adding custom dimension (property) for a job and a vehicle with dedicated [custom_dimension] macro
8//! - assigning hardware requirements to the jobs and vehicles by setting custom properties accordingly
9//! - adding custom [FeatureConstraint] which reads custom properties from the job and the vehicle and checks whether they match
10//!
11
12#[path = "./common/routing.rs"]
13mod common;
14use crate::common::define_routing_data;
15
16use std::collections::HashSet;
17use std::iter::once;
18use std::sync::Arc;
19use vrp_core::prelude::*;
20
21// Specify two custom properties: one for a job and one for a vehicle
22custom_dimension!(JobHardware typeof String);
23custom_dimension!(VehicleHardware typeof HashSet<String>);
24
25/// Provides a way to put custom hard constraints on job/activity - vehicle assignment.
26struct HardwareConstraint {
27    code: ViolationCode,
28}
29
30impl FeatureConstraint for HardwareConstraint {
31    fn evaluate(&self, move_ctx: &MoveContext<'_>) -> Option<ConstraintViolation> {
32        match move_ctx {
33            // matching job to route is evaluated before activity matching, so use it to improve search procedure
34            MoveContext::Route { route_ctx, job, .. } => {
35                let hardware_vehicle = route_ctx.route().actor.vehicle.dimens.get_vehicle_hardware();
36                let hardware_job = job.dimens().get_job_hardware();
37
38                match (hardware_job, hardware_vehicle) {
39                    (None, _) => None,
40                    (Some(hw_job), Some(hw_vehicle)) if hw_vehicle.contains(hw_job) => None,
41                    _ => ConstraintViolation::fail(self.code),
42                }
43            }
44            // matching activity to route is called for every possible insertion point in the tour
45            // we don't need it here as hard constraint can be validated on route-job level
46            MoveContext::Activity { .. } => None,
47        }
48    }
49}
50
51/// Specifies a CVRP problem variant: 4 delivery jobs with demand=1 and 2 vehicles with capacity=2 in each.
52fn define_problem(goal: GoalContext, transport: Arc<dyn TransportCost>) -> GenericResult<Problem> {
53    // create 4 jobs when second and forth have fridge requirement
54    let single_jobs = (1..=4)
55        .map(|idx| {
56            SingleBuilder::default()
57                .id(format!("job{idx}").as_str())
58                .demand(Demand::delivery(1))
59                .dimension(|dimens| {
60                    // all jobs have fridge requirements, but only one vehicle will be allowed to serve them
61                    dimens.set_job_hardware("fridge".to_string());
62                })
63                .location(idx)?
64                .build_as_job()
65        })
66        .collect::<Result<Vec<_>, _>>()?;
67
68    // create 2 vehicles
69    let vehicles = (1..=2)
70        .map(|idx| {
71            VehicleBuilder::default()
72                .id(format!("v{idx}").as_str())
73                .add_detail(
74                    VehicleDetailBuilder::default()
75                        // vehicle starts at location with index 0 in routing matrix
76                        .set_start_location(0)
77                        // vehicle should return to location with index 0
78                        .set_end_location(0)
79                        .build()?,
80                )
81                .dimension(|dimens| {
82                    if idx % 2 == 0 {
83                        // only one vehicle has a hardware requirement set to 'fridge'
84                        dimens.set_vehicle_hardware(once("fridge".to_string()).collect());
85                    }
86                })
87                // each vehicle has capacity=2, so it can serve at most 2 jobs
88                .capacity(SingleDimLoad::new(2))
89                .build()
90        })
91        .collect::<Result<Vec<_>, _>>()?;
92
93    ProblemBuilder::default()
94        .add_jobs(single_jobs.into_iter())
95        .add_vehicles(vehicles.into_iter())
96        .with_goal(goal)
97        .with_transport_cost(transport)
98        .build()
99}
100
101/// Defines CVRP variant with a custom constraint as a goal of optimization.
102fn define_goal(transport: Arc<dyn TransportCost>) -> GenericResult<GoalContext> {
103    let minimize_unassigned = MinimizeUnassignedBuilder::new("min-unassigned").build()?;
104    let capacity_feature = CapacityFeatureBuilder::<SingleDimLoad>::new("capacity").build()?;
105    let transport_feature = TransportFeatureBuilder::new("min-distance")
106        .set_transport_cost(transport)
107        .set_time_constrained(false)
108        .build_minimize_distance()?;
109    // create our custom feature
110    let hardware_feature = FeatureBuilder::default()
111        .with_name("hardware")
112        .with_constraint(HardwareConstraint { code: ViolationCode::default() })
113        .build()?;
114
115    // configure goal of optimization
116    GoalContextBuilder::with_features(&[minimize_unassigned, transport_feature, capacity_feature, hardware_feature])?
117        .build()
118}
119
120fn main() -> GenericResult<()> {
121    let transport = Arc::new(define_routing_data()?);
122
123    let goal = define_goal(transport.clone())?;
124    let problem = Arc::new(define_problem(goal, transport)?);
125
126    let config = VrpConfigBuilder::new(problem.clone()).prebuild()?.with_max_generations(Some(10)).build()?;
127
128    // run the VRP solver and get the best known solution
129    let solution = Solver::new(problem, config).solve()?;
130
131    assert_eq!(
132        solution.unassigned.len(),
133        2,
134        "expected two assigned jobs due to hardware requirement and capacity constraints"
135    );
136    assert_eq!(solution.routes.len(), 1, "only one tour should be there: second vehicle cannot serve hardware jobs");
137    assert_eq!(solution.cost, 1050., "unexpected cost - closest to depot jobs should be assigned");
138
139    // simple way to explore the solution, more advanced are available too
140    println!(
141        "\nIn solution, locations are visited in the following order:\n{:?}\n",
142        solution.get_locations().map(Iterator::collect::<Vec<_>>).collect::<Vec<_>>()
143    );
144
145    Ok(())
146}
custom_constraint/custom_constraint.rs

custom_constraint/
custom_constraint.rs
