cvrp/
cvrp.rs

1//! This example shows how to model Capacitated Vehicle Routing Problem (CVRP) variant where multiple vehicles
2//! of the same type are constrained only be their capacity and job demand.
3//!
4//! Key points here:
5//! - how to create jobs, vehicles and define [Problem]
6//! - how to define a goal of optimization considering capacity/demand constraints and distance minimization
7//! - how to define routing matrix
8//! - how to compose all building blocks together
9//! - how to run the solver
10//!
11
12#[path = "./common/routing.rs"]
13mod common;
14use crate::common::define_routing_data;
15
16use std::sync::Arc;
17use vrp_core::prelude::*;
18
19/// Specifies a CVRP problem variant: 4 delivery jobs with demand=1 and 4 vehicles with capacity=2 in each.
20fn define_problem(goal: GoalContext, transport: Arc<dyn TransportCost>) -> GenericResult<Problem> {
21    // create 4 jobs with location indices from 1 to 4
22    let single_jobs = (1..=4)
23        .map(|idx| {
24            SingleBuilder::default()
25                .id(format!("job{idx}").as_str())
26                // each job is delivery job with demand=1
27                .demand(Demand::delivery(1))
28                // job has location, which is an index in routing matrix
29                .location(idx)?
30                .build_as_job()
31        })
32        .collect::<Result<Vec<_>, _>>()?;
33
34    // create 4 vehicles
35    let vehicles = (1..=4)
36        .map(|idx| {
37            VehicleBuilder::default()
38                .id(format!("v{idx}").as_str())
39                .add_detail(
40                    VehicleDetailBuilder::default()
41                        // vehicle starts at location with index 0 in routing matrix
42                        .set_start_location(0)
43                        // vehicle should return to location with index 0
44                        .set_end_location(0)
45                        .build()?,
46                )
47                // each vehicle has capacity=2, so it can serve at most 2 jobs
48                .capacity(SingleDimLoad::new(2))
49                .build()
50        })
51        .collect::<Result<Vec<_>, _>>()?;
52
53    ProblemBuilder::default()
54        .add_jobs(single_jobs.into_iter())
55        .add_vehicles(vehicles.into_iter())
56        .with_goal(goal)
57        .with_transport_cost(transport)
58        .build()
59}
60
61/// Defines CVRP variant as a goal of optimization.
62fn define_goal(transport: Arc<dyn TransportCost>) -> GenericResult<GoalContext> {
63    // configure features needed to model CVRP
64    let minimize_unassigned = MinimizeUnassignedBuilder::new("min-unassigned").build()?;
65    let capacity_feature = CapacityFeatureBuilder::<SingleDimLoad>::new("capacity").build()?;
66    let transport_feature = TransportFeatureBuilder::new("min-distance")
67        .set_transport_cost(transport)
68        // explicitly opt-out from time constraint on vehicles/jobs
69        .set_time_constrained(false)
70        .build_minimize_distance()?;
71
72    // configure goal of optimization: features with objectives are read from ordered feature list. Here we have:
73    //   1. minimum of unassigned jobs as the main objective
74    //   2. minimum distance traveled
75    GoalContextBuilder::with_features(&[minimize_unassigned, transport_feature, capacity_feature])?.build()
76}
77
78fn main() -> GenericResult<()> {
79    // get routing data, see `./common/routing.rs` for details
80    let transport = Arc::new(define_routing_data()?);
81
82    // specify CVRP variant as problem definition and the goal of optimization
83    let goal = define_goal(transport.clone())?;
84    let problem = Arc::new(define_problem(goal, transport)?);
85
86    // build a solver config with the predefined settings to run 5 secs or 10 generations at most
87    let config = VrpConfigBuilder::new(problem.clone())
88        .prebuild()?
89        .with_max_time(Some(5))
90        .with_max_generations(Some(10))
91        .build()?;
92
93    // run the VRP solver and get the best known solution
94    let solution = Solver::new(problem, config).solve()?;
95
96    assert!(solution.unassigned.is_empty(), "has unassigned jobs, but all jobs must be assigned");
97    assert_eq!(solution.routes.len(), 2, "two tours are expected");
98    assert_eq!(solution.cost, 2135., "unexpected cost (total distance traveled)");
99
100    // simple way to explore the solution, more advanced are available too
101    println!(
102        "\nIn solution, locations are visited in the following order:\n{:?}\n",
103        solution.get_locations().map(Iterator::collect::<Vec<_>>).collect::<Vec<_>>()
104    );
105
106    Ok(())
107}
cvrp/cvrp.rs

cvrp/
cvrp.rs
