use super::super::types::*;
use super::super::utils::{matrix_get_dist, matrix_get_time};
fn solve(matrix: &DistMatrix, num_vehicles: usize) -> SolveResult {
let n = matrix.len();
if n <= 1 {
return SolveResult {
routes: vec![vec![0]],
total_distance: 0.0,
total_time: 0.0,
};
}
let max_intermediate = ((n - 1) as f64 / num_vehicles as f64).ceil() as usize;
let cap = max_intermediate + 1;
let mut savings: Vec<(usize, usize, f64)> = Vec::new();
for i in 1..n {
for j in (i + 1)..n {
let s = matrix_get_dist(matrix, 0, i) + matrix_get_dist(matrix, 0, j)
- matrix_get_dist(matrix, i, j);
savings.push((i, j, s));
}
}
savings.sort_by(|a, b| b.2.partial_cmp(&a.2).unwrap_or(std::cmp::Ordering::Equal));
let mut routes: Vec<Vec<usize>> = (1..n).map(|i| vec![0, i, 0]).collect();
let find_route = |node: usize, routes: &[Vec<usize>]| -> Option<usize> {
routes.iter().position(|r| r.contains(&node))
};
let intermediate_count = |r: &[usize]| -> usize {
if r.len() > 2 {
r.len() - 2
} else {
0
}
};
for &(i, j, _) in &savings {
if routes.len() <= num_vehicles {
break;
}
let ri = match find_route(i, &routes) {
Some(idx) => idx,
None => continue,
};
let rj = match find_route(j, &routes) {
Some(idx) => idx,
None => continue,
};
if ri == rj {
continue;
}
let ra = &routes[ri];
let rb = &routes[rj];
let end_of_a = ra[ra.len() - 2];
let start_of_b = rb[1];
let merged = if (end_of_a == i && start_of_b == j) || (end_of_a == j && start_of_b == i) {
let mut m = ra[..ra.len() - 1].to_vec();
m.extend_from_slice(&rb[1..]);
Some(m)
} else {
let ra_rev: Vec<usize> = ra.iter().copied().rev().collect();
let rb_rev: Vec<usize> = rb.iter().copied().rev().collect();
let end_rev_a = ra_rev[ra_rev.len() - 2];
let start_rev_b = rb_rev[1];
if (end_rev_a == i && start_rev_b == j) || (end_rev_a == j && start_rev_b == i) {
let mut m = ra_rev[..ra_rev.len() - 1].to_vec();
m.extend_from_slice(&rb_rev[1..]);
Some(m)
} else {
None
}
};
let merged = match merged {
Some(m) => m,
None => continue,
};
if intermediate_count(&merged) > cap {
continue;
}
let mut new_routes: Vec<Vec<usize>> = routes
.iter()
.enumerate()
.filter(|(idx, _)| *idx != ri && *idx != rj)
.map(|(_, r)| r.clone())
.collect();
new_routes.push(merged);
routes = new_routes;
}
while routes.len() > num_vehicles {
let mut best_i = 0;
let mut best_j = 1;
let mut best_merged: Option<Vec<usize>> = None;
let mut best_cost = f64::INFINITY;
for i in 0..routes.len() {
for j in (i + 1)..routes.len() {
let ra = &routes[i];
let rb = &routes[j];
let candidates: Vec<Vec<usize>> = vec![
{
let mut m = ra[..ra.len() - 1].to_vec();
m.extend_from_slice(&rb[1..]);
m
},
{
let mut m = ra[..ra.len() - 1].to_vec();
m.extend(rb[1..rb.len() - 1].iter().rev());
m.push(0);
m
},
{
let mut m = vec![0];
m.extend(rb[1..rb.len() - 1].iter().rev());
m.extend_from_slice(&ra[1..]);
m
},
{
let mut m = vec![0];
m.extend_from_slice(&rb[1..]);
m.extend_from_slice(&ra[1..]);
m
},
];
for merged in &candidates {
if merged.len() < 3 {
continue;
}
let cost: f64 = (0..merged.len() - 1)
.map(|k| matrix_get_dist(matrix, merged[k], merged[k + 1]))
.sum();
if cost < best_cost {
best_cost = cost;
best_i = i;
best_j = j;
best_merged = Some(merged.clone());
}
}
}
}
match best_merged {
Some(merged) => {
let mut new_routes: Vec<Vec<usize>> = routes
.iter()
.enumerate()
.filter(|(idx, _)| *idx != best_i && *idx != best_j)
.map(|(_, r)| r.clone())
.collect();
new_routes.push(merged);
routes = new_routes;
}
None => break,
}
}
let mut total_distance = 0.0;
let mut total_time = 0.0;
for r in &routes {
for k in 0..r.len() - 1 {
total_distance += matrix_get_dist(matrix, r[k], r[k + 1]);
total_time += matrix_get_time(matrix, r[k], r[k + 1]);
}
}
SolveResult {
routes,
total_distance,
total_time,
}
}
pub struct ClarkeWrightSolver;
#[async_trait::async_trait]
impl VRPSolver for ClarkeWrightSolver {
fn id(&self) -> &str {
"clarke_wright"
}
fn label(&self) -> &str {
"Clarke-Wright Savings"
}
fn requires_matrix(&self) -> bool {
true
}
async fn solve(&self, input: &VRPSolverInput) -> Result<VRPSolverOutput, String> {
let matrix = input
.matrix
.as_ref()
.ok_or("Clarke-Wright solver requires a distance matrix")?;
let result = solve(matrix, input.num_vehicles);
Ok(result.into_output(input))
}
fn clone_box(&self) -> Box<dyn VRPSolver> {
Box::new(ClarkeWrightSolver)
}
}
#[cfg(test)]
mod tests {
use crate::core::vrp::test_utils::{make_input, make_stop};
use super::*;
#[tokio::test]
async fn test_clarke_wright_single_depot() {
let stops = vec![make_stop(0.0, 0.0, "depot")];
let input = make_input(stops, 1);
let solver = ClarkeWrightSolver;
let output = solver.solve(&input).await.unwrap();
assert!(output.routes.is_none());
assert_eq!(output.stops.len(), 1);
}
#[tokio::test]
async fn test_clarke_wright_requires_matrix() {
let solver = ClarkeWrightSolver;
assert!(solver.requires_matrix());
}
#[tokio::test]
async fn test_clarke_wright_id_and_label() {
let solver = ClarkeWrightSolver;
assert_eq!(solver.id(), "clarke_wright");
assert!(!solver.label().is_empty());
}
#[tokio::test]
async fn test_clarke_wright_no_matrix_error() {
let stops = vec![make_stop(0.0, 0.0, "depot"), make_stop(1.0, 1.0, "a")];
let input = VRPSolverInput {
locations: stops,
num_vehicles: 1,
vehicle_capacity: 100.0,
objective: VrpObjective::MinDistance,
matrix: None,
service_time_secs: None,
use_time_windows: false,
window_open: None,
window_close: None,
};
let solver = ClarkeWrightSolver;
let err = solver.solve(&input).await.unwrap_err();
assert!(err.contains("requires a distance matrix"));
}
#[tokio::test]
async fn test_clarke_wright_two_stops_one_vehicle() {
let stops = vec![make_stop(0.0, 0.0, "depot"), make_stop(1.0, 0.0, "a")];
let input = make_input(stops, 1);
let solver = ClarkeWrightSolver;
let output = solver.solve(&input).await.unwrap();
assert!(output.stops.iter().any(|s| s.label == "a"));
}
#[tokio::test]
async fn test_clarke_wright_multiple_stops() {
let stops = vec![
make_stop(0.0, 0.0, "depot"),
make_stop(1.0, 0.0, "a"),
make_stop(2.0, 0.0, "b"),
make_stop(3.0, 0.0, "c"),
make_stop(4.0, 0.0, "d"),
];
let input = make_input(stops, 2);
let solver = ClarkeWrightSolver;
let output = solver.solve(&input).await.unwrap();
assert!(output.unassigned.is_none());
assert!(output.routes.is_some());
}
#[tokio::test]
async fn test_clarke_wright_positive_total_distance() {
let stops = vec![
make_stop(0.0, 0.0, "depot"),
make_stop(1.0, 0.0, "a"),
make_stop(0.0, 1.0, "b"),
];
let input = make_input(stops, 1);
let solver = ClarkeWrightSolver;
let output = solver.solve(&input).await.unwrap();
let dist: f64 = output.total_distance_km.parse().unwrap();
assert!(dist > 0.0);
}
}