pdptw/
pdptw.rs

1//! This example shows how to model Pickup and Delivery with Time Windows (PDPTW) variant where
2//! each job is represented by pickup and delivery tasks and has time window constraints.
3//!
4//! The code below looks almost the same as CVPR example and differs only in jobs/vehicle construction
5//! and time constraint configuration.
6//!
7//! Key points here:
8//! - how to create PUDO (pickup and drop off) jobs
9//! - how to set time window constraints on jobs and vehicles
10//!
11
12#[path = "./common/routing.rs"]
13mod common;
14use crate::common::define_routing_data;
15
16use std::iter::once;
17use std::sync::Arc;
18use vrp_core::models::common::TimeWindow;
19use vrp_core::prelude::*;
20
21/// Specifies a PDPTW problem variant: two PUDO (pick up/drop off) jobs with demand=1 and 1 vehicle with capacity 1
22fn define_problem(goal: GoalContext, transport: Arc<dyn TransportCost>) -> GenericResult<Problem> {
23    // build two PUDO (pick up/drop off) jobs with demand=1 and permissive time windows (just to show API usage)
24    let pudos = (1..=2)
25        .map(|idx| {
26            let location_idx = if idx == 1 { 1 } else { 3 };
27            MultiBuilder::default()
28                .id(format!("pudo{idx}").as_str())
29                .add_job(
30                    SingleBuilder::default()
31                        .demand(Demand::pudo_pickup(1))
32                        .times(vec![TimeWindow::new(0., 1000.)])?
33                        .duration(10.)?
34                        .location(location_idx)?
35                        .build()?,
36                )
37                .add_job(
38                    SingleBuilder::default()
39                        .demand(Demand::pudo_delivery(1))
40                        .times(vec![TimeWindow::new(0., 1000.)])?
41                        .duration(10.)?
42                        .location(location_idx + 1)?
43                        .build()?,
44                )
45                .build_as_job()
46        })
47        .collect::<Result<Vec<_>, _>>()?;
48
49    // define a single vehicle with limited capacity
50    let vehicle = VehicleBuilder::default()
51        .id("v1".to_string().as_str())
52        .add_detail(
53            VehicleDetailBuilder::default()
54                // vehicle starts at location with index 0 in routing matrix
55                .set_start_location(0)
56                .set_start_time(0.)
57                // vehicle should return to location with index 0
58                .set_end_location(0)
59                .set_end_time(10000.)
60                .build()?,
61        )
62        // the vehicle has capacity=1, so it is forced to do delivery after each pickup
63        .capacity(SingleDimLoad::new(1))
64        .build()?;
65
66    ProblemBuilder::default()
67        .add_jobs(pudos.into_iter())
68        .add_vehicles(once(vehicle))
69        .with_goal(goal)
70        .with_transport_cost(transport)
71        .build()
72}
73
74/// Defines PDPTW variant as a goal of optimization.
75fn define_goal(transport: Arc<dyn TransportCost>) -> GenericResult<GoalContext> {
76    // configure features needed to model PDPTW
77    let minimize_unassigned = MinimizeUnassignedBuilder::new("min-unassigned").build()?;
78    let capacity_feature = CapacityFeatureBuilder::<SingleDimLoad>::new("capacity").build()?;
79    let transport_feature = TransportFeatureBuilder::new("min-distance")
80        .set_transport_cost(transport)
81        // enable time constraint (not necessary, default behavior, here for demonstration purpose only)
82        .set_time_constrained(true)
83        .build_minimize_distance()?;
84
85    // configure goal of optimization
86    GoalContextBuilder::with_features(&[minimize_unassigned, transport_feature, capacity_feature])?.build()
87}
88
89fn main() -> GenericResult<()> {
90    // get routing data, see `./common/routing.rs` for details
91    let transport = Arc::new(define_routing_data()?);
92
93    // specify PDPTW variant as problem definition and the goal of optimization
94    let goal = define_goal(transport.clone())?;
95    let problem = Arc::new(define_problem(goal, transport)?);
96
97    // build a solver config with the predefined settings to run 5 secs or 10 generations at most
98    let config = VrpConfigBuilder::new(problem.clone())
99        .prebuild()?
100        .with_max_time(Some(5))
101        .with_max_generations(Some(10))
102        .build()?;
103
104    // run the VRP solver and get the best known solution
105    let solution = Solver::new(problem, config).solve()?;
106
107    assert!(solution.unassigned.is_empty(), "has unassigned jobs, but all jobs must be assigned");
108    assert_eq!(solution.routes.len(), 1, "one tour should be there");
109    assert_eq!(solution.cost, 1105., "unexpected cost (total distance traveled)");
110
111    // simple way to explore the solution, more advanced are available too
112    println!(
113        "\nIn solution, locations are visited in the following order:\n{:?}\n",
114        solution.get_locations().map(Iterator::collect::<Vec<_>>).collect::<Vec<_>>()
115    );
116
117    Ok(())
118}
pdptw/pdptw.rs

pdptw/
pdptw.rs
