ferrox/vrptw/
greedy.rs

1use async_trait::async_trait;
2use converge_pack::{AgentEffect, Context, ContextKey, ProposedFact, Suggestor};
3use std::time::Instant;
4use tracing::warn;
5
6use super::problem::{RouteStop, VrptwPlan, VrptwRequest};
7
8pub(super) const REQUEST_PREFIX: &str = "vrptw-request:";
9const PLAN_PREFIX: &str = "vrptw-plan-greedy:";
10
11/// Routes a vehicle via Nearest-Neighbour heuristic with time-window feasibility check.
12///
13/// **Algorithm:** O(n²) — at each stop, visit the nearest unvisited customer
14/// whose time window is still reachable.  Backtracks to depot when no further
15/// customer is reachable.
16///
17/// **Confidence:** capped at 0.60 — nearest-neighbour can be 20-25% worse
18/// than optimal on real instances.
19pub struct NearestNeighborSuggestor;
20
21#[async_trait]
22impl Suggestor for NearestNeighborSuggestor {
23    fn name(&self) -> &str {
24        "NearestNeighborSuggestor"
25    }
26
27    fn dependencies(&self) -> &[ContextKey] {
28        &[ContextKey::Seeds]
29    }
30
31    fn complexity_hint(&self) -> Option<&'static str> {
32        Some("O(n²) — nearest-neighbour with TW feasibility; deterministic, sub-ms for n ≤ 10 000")
33    }
34
35    fn accepts(&self, ctx: &dyn Context) -> bool {
36        ctx.get(ContextKey::Seeds)
37            .iter()
38            .any(|f| f.id.starts_with(REQUEST_PREFIX) && !own_plan_exists(ctx, request_id(&f.id)))
39    }
40
41    async fn execute(&self, ctx: &dyn Context) -> AgentEffect {
42        let mut proposals = Vec::new();
43
44        for fact in ctx
45            .get(ContextKey::Seeds)
46            .iter()
47            .filter(|f| f.id.starts_with(REQUEST_PREFIX))
48        {
49            let rid = request_id(&fact.id);
50            if own_plan_exists(ctx, rid) {
51                continue;
52            }
53
54            match serde_json::from_str::<VrptwRequest>(&fact.content) {
55                Ok(req) => {
56                    let plan = solve_nn(&req);
57                    let confidence = (plan.visit_ratio() * 0.60).min(0.60);
58                    proposals.push(
59                        ProposedFact::new(
60                            ContextKey::Strategies,
61                            format!("{PLAN_PREFIX}{rid}"),
62                            serde_json::to_string(&plan).unwrap_or_default(),
63                            self.name(),
64                        )
65                        .with_confidence(confidence),
66                    );
67                }
68                Err(e) => {
69                    warn!(id = %fact.id, error = %e, "malformed vrptw-request");
70                }
71            }
72        }
73
74        if proposals.is_empty() {
75            AgentEffect::empty()
76        } else {
77            AgentEffect::with_proposals(proposals)
78        }
79    }
80}
81
82fn request_id(fact_id: &str) -> &str {
83    fact_id.trim_start_matches(REQUEST_PREFIX)
84}
85
86fn own_plan_exists(ctx: &dyn Context, request_id: &str) -> bool {
87    let plan_id = format!("{PLAN_PREFIX}{request_id}");
88    ctx.get(ContextKey::Strategies)
89        .iter()
90        .any(|f| f.id == plan_id)
91}
92
93/// Nearest-neighbour TSP with time-window feasibility.
94pub fn solve_nn(req: &VrptwRequest) -> VrptwPlan {
95    let t0 = Instant::now();
96    let n = req.customers.len();
97    let mut visited = vec![false; n];
98    let mut route: Vec<RouteStop> = Vec::new();
99
100    let mut cur_x = req.depot.x;
101    let mut cur_y = req.depot.y;
102    let mut cur_t = req.depot.ready_time;
103    let mut total_dist = 0.0_f64;
104
105    loop {
106        // Find nearest reachable unvisited customer.
107        let best = (0..n)
108            .filter(|&i| !visited[i])
109            .filter_map(|i| {
110                let c = &req.customers[i];
111                let dx = cur_x - c.x;
112                let dy = cur_y - c.y;
113                let dist = (dx * dx + dy * dy).sqrt();
114                #[allow(clippy::cast_possible_truncation)]
115                let travel = dist.ceil() as i64;
116                let arrival = cur_t + travel;
117                // Must arrive before window closes, and vehicle returns in time.
118                let depart = arrival.max(c.window_open) + c.service_time;
119                let depot_dx = c.x - req.depot.x;
120                let depot_dy = c.y - req.depot.y;
121                #[allow(clippy::cast_possible_truncation)]
122                let return_dist = ((depot_dx * depot_dx + depot_dy * depot_dy).sqrt().ceil()) as i64;
123                if arrival <= c.window_close && depart + return_dist <= req.depot.due_time {
124                    Some((i, dist, travel, arrival, depart))
125                } else {
126                    None
127                }
128            })
129            .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
130
131        match best {
132            Some((i, dist, travel, arrival, depart)) => {
133                let c = &req.customers[i];
134                visited[i] = true;
135                total_dist += dist;
136                cur_x = c.x;
137                cur_y = c.y;
138                cur_t = depart;
139                let _ = travel;
140                let _ = arrival;
141                route.push(RouteStop {
142                    customer_id: c.id,
143                    customer_name: c.name.clone(),
144                    arrival: depart - c.service_time,
145                    departure: depart,
146                });
147            }
148            None => break,
149        }
150    }
151
152    // Return to depot.
153    let depot_dx = cur_x - req.depot.x;
154    let depot_dy = cur_y - req.depot.y;
155    let return_dist = (depot_dx * depot_dx + depot_dy * depot_dy).sqrt();
156    total_dist += return_dist;
157    #[allow(clippy::cast_possible_truncation)]
158    let return_time = cur_t + return_dist.ceil() as i64;
159
160    VrptwPlan {
161        request_id: req.id.clone(),
162        customers_visited: route.len(),
163        customers_total: n,
164        route,
165        total_distance: total_dist,
166        return_time,
167        solver: "nearest-neighbour".to_string(),
168        status: "feasible".to_string(),
169        wall_time_seconds: t0.elapsed().as_secs_f64(),
170    }
171}
ferrox/vrptw/greedy.rs

ferrox/vrptw/
greedy.rs
