use async_trait::async_trait;
use converge_pack::Provenance;
use converge_pack::ProvenanceSource;
use converge_pack::{
AgentEffect, Context, ContextKey, DiagnosticPayload, FactPayload, ProposedFact, Suggestor,
};
use serde::{Deserialize, Serialize};
use std::time::Instant;
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct VrptwCustomer {
pub id: usize,
pub name: String,
pub x: f64,
pub y: f64,
pub window_open: i64,
pub window_close: i64,
pub service_time: i64,
}
impl VrptwCustomer {
pub fn travel_to(&self, other: &Self) -> f64 {
euclidean((self.x, self.y), (other.x, other.y))
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct VrptwDepot {
pub x: f64,
pub y: f64,
pub ready_time: i64,
pub due_time: i64,
}
impl VrptwDepot {
pub fn travel_to_customer(&self, customer: &VrptwCustomer) -> f64 {
euclidean((self.x, self.y), (customer.x, customer.y))
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct VrptwRequest {
pub id: String,
pub depot: VrptwDepot,
pub customers: Vec<VrptwCustomer>,
#[serde(default = "default_time_limit")]
pub time_limit_seconds: f64,
}
impl FactPayload for VrptwRequest {
const FAMILY: &'static str = "converge.optimization.vrptw.request";
const VERSION: u16 = 1;
}
fn default_time_limit() -> f64 {
30.0
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct RouteStop {
pub customer_id: usize,
pub customer_name: String,
pub arrival: i64,
pub departure: i64,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub struct VrptwPlan {
pub request_id: String,
pub route: Vec<RouteStop>,
pub customers_total: usize,
pub customers_visited: usize,
pub total_distance: f64,
pub return_time: i64,
pub solver: String,
pub status: String,
pub wall_time_seconds: f64,
}
impl FactPayload for VrptwPlan {
const FAMILY: &'static str = "converge.optimization.vrptw.plan";
const VERSION: u16 = 1;
}
impl VrptwPlan {
#[allow(clippy::cast_precision_loss)]
pub fn visit_ratio(&self) -> f64 {
if self.customers_total == 0 {
return 0.0;
}
self.customers_visited as f64 / self.customers_total as f64
}
}
const REQUEST_PREFIX: &str = "vrptw-request:";
const PLAN_PREFIX: &str = "vrptw-plan-greedy:";
const ERROR_PREFIX: &str = "vrptw-request-error:";
pub struct NearestNeighborTimeWindowRoutingSuggestor;
#[async_trait]
impl Suggestor for NearestNeighborTimeWindowRoutingSuggestor {
fn name(&self) -> &str {
"NearestNeighborTimeWindowRoutingSuggestor"
}
fn dependencies(&self) -> &[ContextKey] {
&[ContextKey::Seeds]
}
fn complexity_hint(&self) -> Option<&'static str> {
Some("O(n^2) nearest-neighbor with time-window feasibility")
}
fn accepts(&self, ctx: &dyn Context) -> bool {
ctx.get(ContextKey::Seeds).iter().any(|f| {
f.id().as_str().starts_with(REQUEST_PREFIX)
&& match f.payload::<VrptwRequest>() {
Some(_) => !plan_exists(ctx, req_id(f.id().as_str())),
None => !error_exists(ctx, f.id().as_str()),
}
})
}
async fn execute(&self, ctx: &dyn Context) -> AgentEffect {
let mut proposals = Vec::new();
for fact in ctx
.get(ContextKey::Seeds)
.iter()
.filter(|f| f.id().as_str().starts_with(REQUEST_PREFIX))
{
match fact.payload::<VrptwRequest>() {
Some(req) => {
if plan_exists(ctx, req_id(fact.id().as_str())) {
continue;
}
let plan = solve_nearest_neighbor_time_windows(req);
let confidence = (plan.visit_ratio() * 0.60).min(0.60);
proposals.push(
ProposedFact::new(
ContextKey::Strategies,
format!("{}{}", PLAN_PREFIX, plan.request_id),
plan.clone(),
self.provenance(),
)
.with_confidence(confidence),
);
}
None => {
if error_exists(ctx, fact.id().as_str()) {
continue;
}
proposals.push(
ProposedFact::new(
ContextKey::Diagnostic,
format!("{}{}", ERROR_PREFIX, fact.id()),
DiagnosticPayload::new(
self.name(),
format!(
"malformed vrptw request '{}': expected {} v{} payload",
fact.id(),
VrptwRequest::FAMILY,
VrptwRequest::VERSION
),
),
self.provenance(),
)
.with_confidence(1.0),
);
}
}
}
if proposals.is_empty() {
AgentEffect::empty()
} else {
AgentEffect::with_proposals(proposals)
}
}
fn provenance(&self) -> Provenance {
crate::suggestors::CONVERGE_OPTIMIZATION_PROVENANCE.provenance()
}
}
pub fn solve_nearest_neighbor_time_windows(req: &VrptwRequest) -> VrptwPlan {
let t0 = Instant::now();
let n = req.customers.len();
let mut visited = vec![false; n];
let mut route = Vec::new();
let mut cur_x = req.depot.x;
let mut cur_y = req.depot.y;
let mut cur_t = req.depot.ready_time;
let mut total_distance = 0.0_f64;
loop {
let best = (0..n)
.filter(|&i| !visited[i])
.filter_map(|i| {
let customer = &req.customers[i];
if customer.service_time < 0 || customer.window_close < customer.window_open {
return None;
}
let distance = euclidean((cur_x, cur_y), (customer.x, customer.y));
#[allow(clippy::cast_possible_truncation)]
let travel_time = distance.ceil() as i64;
let arrival = cur_t + travel_time;
let departure = arrival.max(customer.window_open) + customer.service_time;
let return_distance =
euclidean((customer.x, customer.y), (req.depot.x, req.depot.y));
#[allow(clippy::cast_possible_truncation)]
let return_time = return_distance.ceil() as i64;
if arrival <= customer.window_close && departure + return_time <= req.depot.due_time
{
Some((i, distance, arrival, departure))
} else {
None
}
})
.min_by(|a, b| a.1.total_cmp(&b.1));
match best {
Some((i, distance, arrival, departure)) => {
let customer = &req.customers[i];
visited[i] = true;
total_distance += distance;
cur_x = customer.x;
cur_y = customer.y;
cur_t = departure;
route.push(RouteStop {
customer_id: customer.id,
customer_name: customer.name.clone(),
arrival: arrival.max(customer.window_open),
departure,
});
}
None => break,
}
}
let return_distance = euclidean((cur_x, cur_y), (req.depot.x, req.depot.y));
total_distance += return_distance;
#[allow(clippy::cast_possible_truncation)]
let return_time = cur_t + return_distance.ceil() as i64;
let customers_visited = route.len();
let status = if n == 0 || customers_visited > 0 {
"feasible"
} else {
"infeasible"
};
VrptwPlan {
request_id: req.id.clone(),
route,
customers_total: n,
customers_visited,
total_distance,
return_time,
solver: "nearest-neighbor-tw".to_string(),
status: status.to_string(),
wall_time_seconds: t0.elapsed().as_secs_f64(),
}
}
fn euclidean(a: (f64, f64), b: (f64, f64)) -> f64 {
let dx = a.0 - b.0;
let dy = a.1 - b.1;
(dx * dx + dy * dy).sqrt()
}
fn req_id(fact_id: &str) -> &str {
fact_id.trim_start_matches(REQUEST_PREFIX)
}
fn plan_exists(ctx: &dyn Context, request_id: &str) -> bool {
let id = format!("{}{}", PLAN_PREFIX, request_id);
ctx.get(ContextKey::Strategies)
.iter()
.any(|f| f.id().as_str() == id)
}
fn error_exists(ctx: &dyn Context, fact_id: &str) -> bool {
let id = format!("{}{}", ERROR_PREFIX, fact_id);
ctx.get(ContextKey::Diagnostic)
.iter()
.any(|f| f.id().as_str() == id)
}
#[cfg(test)]
mod tests {
use super::*;
use converge_core::{ContextState, Engine};
use converge_pack::TextPayload;
use proptest::prelude::*;
use std::collections::BTreeSet;
fn depot(due_time: i64) -> VrptwDepot {
VrptwDepot {
x: 0.0,
y: 0.0,
ready_time: 0,
due_time,
}
}
fn customer(id: usize, x: f64, open: i64, close: i64) -> VrptwCustomer {
VrptwCustomer {
id,
name: format!("customer-{id}"),
x,
y: 0.0,
window_open: open,
window_close: close,
service_time: 1,
}
}
fn req(customers: Vec<VrptwCustomer>, due_time: i64) -> VrptwRequest {
VrptwRequest {
id: "route-1".to_string(),
depot: depot(due_time),
customers,
time_limit_seconds: 1.0,
}
}
#[tokio::test]
async fn suggestor_emits_time_window_route() {
let request = req(
vec![customer(1, 1.0, 0, 100), customer(2, 2.0, 0, 100)],
1000,
);
let mut engine = Engine::new();
engine.register_suggestor(NearestNeighborTimeWindowRoutingSuggestor);
let mut ctx = ContextState::new();
ctx.add_proposal(ProposedFact::new(
ContextKey::Seeds,
"vrptw-request:route-1",
request,
converge_pack::ProvenanceSource::provenance(
crate::suggestors::CONVERGE_OPTIMIZATION_PROVENANCE,
),
))
.unwrap();
let result = engine.run(ctx).await.unwrap();
let facts = result.context.get(ContextKey::Strategies);
assert_eq!(facts.len(), 1);
assert_eq!(facts[0].id().as_str(), "vrptw-plan-greedy:route-1");
let plan = facts[0].require_payload::<VrptwPlan>().unwrap();
assert_eq!(plan.customers_visited, 2);
}
#[tokio::test]
async fn malformed_request_emits_diagnostic() {
let mut engine = Engine::new();
engine.register_suggestor(NearestNeighborTimeWindowRoutingSuggestor);
let mut ctx = ContextState::new();
ctx.add_proposal(ProposedFact::new(
ContextKey::Seeds,
"vrptw-request:bad",
TextPayload::new("not a vrptw request"),
converge_pack::ProvenanceSource::provenance(
crate::suggestors::CONVERGE_OPTIMIZATION_PROVENANCE,
),
))
.unwrap();
let result = engine.run(ctx).await.unwrap();
assert!(result.context.get(ContextKey::Strategies).is_empty());
assert_eq!(result.context.get(ContextKey::Diagnostic).len(), 1);
}
#[test]
fn unreachable_customer_is_not_visited() {
let plan =
solve_nearest_neighbor_time_windows(&req(vec![customer(1, 1000.0, 0, 1)], 10_000));
assert_eq!(plan.customers_visited, 0);
assert_eq!(plan.status, "infeasible");
}
proptest! {
#[test]
fn route_has_unique_feasible_stops(customer_count in 0usize..30) {
let customers: Vec<_> = (0..customer_count)
.map(|i| customer(i, (i + 1) as f64, 0, 10_000))
.collect();
let request = req(customers.clone(), 100_000);
let plan = solve_nearest_neighbor_time_windows(&request);
let mut seen = BTreeSet::new();
for stop in &plan.route {
prop_assert!(seen.insert(stop.customer_id));
let customer = customers
.iter()
.find(|customer| customer.id == stop.customer_id)
.expect("route stop must refer to a known customer");
prop_assert!(stop.arrival >= customer.window_open);
prop_assert!(stop.arrival <= customer.window_close);
prop_assert_eq!(stop.departure, stop.arrival + customer.service_time);
}
prop_assert!(plan.customers_visited <= plan.customers_total);
prop_assert!(plan.return_time <= request.depot.due_time);
}
}
}