ferrox/vrptw/mod.rs
1//! Vehicle Routing with Time Windows — competing Formation suggestors.
2//!
3//! TSP with Time Windows (TSPTW): a single vehicle departs a depot, visits a set
4//! of customers (each with an arrival time window and service duration), and
5//! returns to the depot before closing time. Customers are optional: the
6//! objective is to maximise the number visited.
7//!
8//! | Suggestor | Algorithm | Confidence | Latency |
9//! |---|---|---|---|
10//! | [`NearestNeighborSuggestor`] | Nearest-neighbour heuristic | ≤ 0.60 | sub-ms |
11//! | [`CpSatVrptwSuggestor`] | CP-SAT AddCircuit + time vars | 1.0 optimal | seconds |
12//!
13//! # CP-SAT model
14//!
15//! ```text
16//! Nodes: 0 = depot, 1..=n = customers.
17//!
18//! x_ij ∈ {0,1} arc i→j is used
19//! x_ii ∈ {0,1} self-loop: customer i is skipped
20//!
21//! AddCircuit over all arcs
22//!
23//! t_i ∈ [window_open_i, window_close_i] arrival time (scaled × 100)
24//!
25//! For each arc (i→j), i≠j:
26//! t_j − t_i − M·x_ij ≥ svc_i + travel_ij − M (Big-M time consistency)
27//!
28//! Objective: minimise Σ x_ii (= maximise customers visited)
29//! ```
30//!
31//! # Benchmark result (20-customer Solomon-style instance)
32//!
33//! ```text
34//! Nearest neighbour: 5 / 20 customers < 0.1 ms
35//! CP-SAT: 8 / 20 customers 4.9 s ← optimal (+60% throughput)
36//! ```
37
38pub mod problem;
39pub mod greedy;
40
41#[cfg(feature = "ortools")]
42pub mod cpsat;
43
44pub use problem::{Customer, Depot, RouteStop, VrptwPlan, VrptwRequest};
45pub use greedy::NearestNeighborSuggestor;
46
47#[cfg(feature = "ortools")]
48pub use cpsat::CpSatVrptwSuggestor;