use crate::distance::Matrix;
use crate::rng::Rng;
#[derive(Clone, Copy, Debug)]
pub struct RouteLimits {
pub max_length: f64,
pub max_stops: usize,
}
impl Default for RouteLimits {
fn default() -> Self {
RouteLimits {
max_length: f64::INFINITY,
max_stops: usize::MAX,
}
}
}
#[derive(Clone, Copy, Debug)]
pub struct GraspOptions {
pub iterations: usize,
pub alpha: f64,
pub seed: u64,
}
impl Default for GraspOptions {
fn default() -> Self {
GraspOptions {
iterations: 200,
alpha: 0.3,
seed: 1,
}
}
}
#[derive(Clone, Debug)]
pub struct Solution {
pub routes: Vec<Vec<usize>>,
pub lengths: Vec<f64>,
pub total: f64,
pub lower_bound: f64,
pub best_iteration: usize,
}
impl Solution {
pub fn gap_to_bound(&self) -> f64 {
if self.lower_bound <= 0.0 {
return f64::NAN;
}
(self.total - self.lower_bound) / self.lower_bound
}
}
fn validate(m: &Matrix, depot: usize, units: &[usize]) -> Result<(), String> {
let n = m.len();
if depot >= n {
return Err(format!("depot index {depot} is out of range for {n} units"));
}
if units.is_empty() {
return Err("no units to route".into());
}
let mut seen = vec![false; n];
for &u in units {
if u >= n {
return Err(format!("unit index {u} is out of range for {n} units"));
}
if u == depot {
return Err("the depot cannot be one of the units to visit".into());
}
if seen[u] {
return Err(format!("unit {u} appears twice"));
}
seen[u] = true;
}
Ok(())
}
pub fn route_length(m: &Matrix, depot: usize, route: &[usize]) -> f64 {
if route.is_empty() {
return 0.0;
}
let mut total = m.get(depot, route[0]);
for w in route.windows(2) {
total += m.get(w[0], w[1]);
}
total + m.get(route[route.len() - 1], depot)
}
fn is_symmetric(m: &Matrix) -> bool {
let n = m.len();
(0..n).all(|i| (i + 1..n).all(|j| (m.get(i, j) - m.get(j, i)).abs() <= 1e-12))
}
fn in_out_bound(m: &Matrix, depot: usize, units: &[usize]) -> f64 {
let mut nodes: Vec<usize> = Vec::with_capacity(units.len() + 1);
nodes.push(depot);
nodes.extend_from_slice(units);
let mut sum = 0.0;
for &i in &nodes {
let (mut min_out, mut min_in) = (f64::INFINITY, f64::INFINITY);
for &j in &nodes {
if i != j {
min_out = min_out.min(m.get(i, j));
min_in = min_in.min(m.get(j, i));
}
}
sum += min_out + min_in;
}
sum / 2.0
}
fn lower_bound(
m: &Matrix,
depot: usize,
units: &[usize],
limits: &RouteLimits,
symmetric: bool,
) -> f64 {
let general = in_out_bound(m, depot, units);
let single_route = limits.max_length.is_infinite() && limits.max_stops >= units.len();
if symmetric && single_route {
general.max(two_edge_bound(m, depot, units))
} else {
general
}
}
fn two_edge_bound(m: &Matrix, depot: usize, units: &[usize]) -> f64 {
let mut nodes: Vec<usize> = Vec::with_capacity(units.len() + 1);
nodes.push(depot);
nodes.extend_from_slice(units);
if nodes.len() < 3 {
return if nodes.len() == 2 {
2.0 * m.get(nodes[0], nodes[1])
} else {
0.0
};
}
let mut sum = 0.0;
for &i in &nodes {
let mut best = [f64::INFINITY; 2];
for &j in &nodes {
if i == j {
continue;
}
let d = m.get(i, j);
if d < best[0] {
best[1] = best[0];
best[0] = d;
} else if d < best[1] {
best[1] = d;
}
}
sum += best[0] + best[1];
}
sum / 2.0
}
fn construct(m: &Matrix, depot: usize, units: &[usize], alpha: f64, rng: &mut Rng) -> Vec<usize> {
let mut remaining: Vec<usize> = units.to_vec();
let mut tour = Vec::with_capacity(units.len());
let mut current = depot;
while !remaining.is_empty() {
let costs: Vec<f64> = remaining.iter().map(|&u| m.get(current, u)).collect();
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for &c in &costs {
lo = lo.min(c);
hi = hi.max(c);
}
let threshold = lo + alpha * (hi - lo);
let candidates: Vec<usize> = (0..remaining.len())
.filter(|&k| costs[k] <= threshold)
.collect();
let pick = candidates[rng.below(candidates.len())];
current = remaining.swap_remove(pick);
tour.push(current);
}
tour
}
fn prefix_costs(m: &Matrix, tour: &[usize]) -> (Vec<f64>, Vec<f64>) {
let n = tour.len();
let mut fwd = vec![0.0; n];
let mut bwd = vec![0.0; n];
for k in 1..n {
fwd[k] = fwd[k - 1] + m.get(tour[k - 1], tour[k]);
bwd[k] = bwd[k - 1] + m.get(tour[k], tour[k - 1]);
}
(fwd, bwd)
}
fn two_opt(m: &Matrix, depot: usize, tour: &mut [usize], symmetric: bool) -> bool {
let n = tour.len();
if n < 3 {
return false;
}
let node = |tour: &[usize], k: isize| -> usize {
if k < 0 || k as usize >= tour.len() {
depot
} else {
tour[k as usize]
}
};
let mut improved_any = false;
let mut improved = true;
while improved {
improved = false;
let (fwd, bwd) = if symmetric {
(Vec::new(), Vec::new())
} else {
prefix_costs(m, tour)
};
'scan: for i in 0..n - 1 {
for j in (i + 1)..n {
let a = node(tour, i as isize - 1);
let b = tour[i];
let c = tour[j];
let d = node(tour, j as isize + 1);
let mut delta = m.get(a, c) + m.get(b, d) - m.get(a, b) - m.get(c, d);
if !symmetric {
delta += (bwd[j] - bwd[i]) - (fwd[j] - fwd[i]);
}
if delta < -1e-12 {
tour[i..=j].reverse();
improved = true;
improved_any = true;
if !symmetric {
break 'scan; }
}
}
}
}
improved_any
}
fn or_opt(m: &Matrix, depot: usize, tour: &mut Vec<usize>, symmetric: bool) -> bool {
let mut improved_any = false;
let mut improved = true;
while improved {
improved = false;
let n = tour.len();
'outer: for seg in 1..=3.min(n.saturating_sub(1)) {
for i in 0..=(n - seg) {
let prev = if i == 0 { depot } else { tour[i - 1] };
let next = if i + seg >= n { depot } else { tour[i + seg] };
let first = tour[i];
let last = tour[i + seg - 1];
let removal_gain = m.get(prev, first) + m.get(last, next) - m.get(prev, next);
let rest: Vec<usize> = tour
.iter()
.enumerate()
.filter(|(k, _)| *k < i || *k >= i + seg)
.map(|(_, &u)| u)
.collect();
for p in 0..=rest.len() {
let a = if p == 0 { depot } else { rest[p - 1] };
let b = if p >= rest.len() { depot } else { rest[p] };
for &reversed in &[false, true] {
let (f, l) = if reversed {
(last, first)
} else {
(first, last)
};
let mut insert_cost = m.get(a, f) + m.get(l, b) - m.get(a, b);
if reversed && !symmetric {
for w in tour[i..i + seg].windows(2) {
insert_cost += m.get(w[1], w[0]) - m.get(w[0], w[1]);
}
}
if insert_cost < removal_gain - 1e-12 {
let mut segment: Vec<usize> = tour[i..i + seg].to_vec();
if reversed {
segment.reverse();
}
let mut new_tour = rest.clone();
for (k, u) in segment.into_iter().enumerate() {
new_tour.insert(p + k, u);
}
*tour = new_tour;
improved = true;
improved_any = true;
continue 'outer;
}
}
}
}
}
}
improved_any
}
fn local_search(m: &Matrix, depot: usize, tour: &mut Vec<usize>, symmetric: bool) {
let mut length = route_length(m, depot, tour);
loop {
let a = two_opt(m, depot, tour, symmetric);
let b = or_opt(m, depot, tour, symmetric);
if !a && !b {
break;
}
let now = route_length(m, depot, tour);
if now >= length - 1e-12 {
break;
}
length = now;
}
}
fn split(
m: &Matrix,
depot: usize,
tour: &[usize],
limits: &RouteLimits,
) -> Option<Vec<Vec<usize>>> {
let n = tour.len();
let mut cost = vec![f64::INFINITY; n + 1];
let mut pred = vec![usize::MAX; n + 1];
cost[0] = 0.0;
for i in 0..n {
if !cost[i].is_finite() {
continue;
}
let mut len = 0.0;
for j in i..n {
if j - i + 1 > limits.max_stops {
break;
}
if j == i {
len = m.get(depot, tour[i]);
} else {
len += m.get(tour[j - 1], tour[j]);
}
let route_cost = len + m.get(tour[j], depot);
if route_cost > limits.max_length {
break;
}
if cost[i] + route_cost < cost[j + 1] {
cost[j + 1] = cost[i] + route_cost;
pred[j + 1] = i;
}
}
}
if !cost[n].is_finite() {
return None;
}
let mut routes = Vec::new();
let mut j = n;
while j > 0 {
let i = pred[j];
routes.push(tour[i..j].to_vec());
j = i;
}
routes.reverse();
Some(routes)
}
pub fn grasp_routes(
m: &Matrix,
depot: usize,
units: &[usize],
limits: RouteLimits,
options: GraspOptions,
) -> Result<Solution, String> {
validate(m, depot, units)?;
if !(0.0..=1.0).contains(&options.alpha) {
return Err("alpha must be in [0, 1]".into());
}
if options.iterations == 0 {
return Err("iterations must be at least 1".into());
}
if limits.max_stops == 0 || limits.max_length.is_nan() || limits.max_length <= 0.0 {
return Err("route limits must allow at least one stop".into());
}
let mut rng = Rng::new(options.seed);
let symmetric = is_symmetric(m);
let lower_bound = lower_bound(m, depot, units, &limits, symmetric);
let mut best: Option<Solution> = None;
for it in 0..options.iterations {
let mut tour = construct(m, depot, units, options.alpha, &mut rng);
local_search(m, depot, &mut tour, symmetric);
let mut routes = match split(m, depot, &tour, &limits) {
Some(r) => r,
None => return Err("some unit cannot be served within the route limits".into()),
};
if routes.len() > 1 {
for r in routes.iter_mut() {
local_search(m, depot, r, symmetric);
}
}
let lengths: Vec<f64> = routes.iter().map(|r| route_length(m, depot, r)).collect();
let total: f64 = lengths.iter().sum();
if best.as_ref().map_or(true, |b| total < b.total - 1e-12) {
best = Some(Solution {
routes,
lengths,
total,
lower_bound,
best_iteration: it + 1,
});
}
}
Ok(best.expect("at least one iteration"))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::distance::euclidean_matrix;
fn square_points() -> Matrix {
let x = [0.0, -1.0, 0.0, 1.0, 1.0, 1.0, 0.0, -1.0, -1.0];
let y = [0.0, 1.0, 1.0, 1.0, 0.0, -1.0, -1.0, -1.0, 0.0];
euclidean_matrix(&x, &y).unwrap()
}
#[test]
fn tsp_on_a_square_is_optimal() {
let m = square_points();
let units: Vec<usize> = (1..9).collect();
let s = grasp_routes(
&m,
0,
&units,
RouteLimits::default(),
GraspOptions {
iterations: 50,
alpha: 0.3,
seed: 3,
},
)
.unwrap();
assert_eq!(s.routes.len(), 1);
let optimum = 7.0 + 1.0 + 2f64.sqrt();
assert!((s.total - optimum).abs() < 1e-9, "total {}", s.total);
assert!(s.lower_bound <= s.total + 1e-9);
assert_eq!(route_length(&m, 0, &s.routes[0]), s.total);
}
#[test]
fn split_respects_limits() {
let m = square_points();
let units: Vec<usize> = (1..9).collect();
let limits = RouteLimits {
max_length: f64::INFINITY,
max_stops: 3,
};
let s = grasp_routes(&m, 0, &units, limits, GraspOptions::default()).unwrap();
assert!(s.routes.len() >= 3);
assert!(s.routes.iter().all(|r| r.len() <= 3));
let mut all: Vec<usize> = s.routes.concat();
all.sort();
assert_eq!(all, units);
let limits = RouteLimits {
max_length: 3.0,
max_stops: usize::MAX,
};
let s = grasp_routes(&m, 0, &units, limits, GraspOptions::default()).unwrap();
assert!(s.lengths.iter().all(|&l| l <= 3.0 + 1e-9));
let limits = RouteLimits {
max_length: 2.5,
max_stops: usize::MAX,
};
assert!(grasp_routes(&m, 0, &units, limits, GraspOptions::default()).is_err());
let limits = RouteLimits {
max_length: 1.0,
max_stops: usize::MAX,
};
assert!(grasp_routes(&m, 0, &units, limits, GraspOptions::default()).is_err());
}
#[test]
fn invalid_input_is_refused() {
let m = square_points();
assert!(grasp_routes(
&m,
0,
&[0, 1],
RouteLimits::default(),
GraspOptions::default()
)
.is_err());
assert!(grasp_routes(
&m,
0,
&[1, 1],
RouteLimits::default(),
GraspOptions::default()
)
.is_err());
assert!(
grasp_routes(&m, 9, &[1], RouteLimits::default(), GraspOptions::default()).is_err()
);
assert!(grasp_routes(&m, 0, &[], RouteLimits::default(), GraspOptions::default()).is_err());
}
#[test]
fn asymmetric_matrices_terminate_and_respect_the_bound() {
let n = 9;
let mut rng = Rng::new(0);
let data: Vec<f64> = (0..n * n)
.map(|k| {
if k % (n + 1) == 0 {
0.0
} else {
1.0 + 9.0 * rng.next_f64()
}
})
.collect();
let m = Matrix::from_vec(n, data).unwrap();
let units: Vec<usize> = (1..n).collect();
let o = GraspOptions {
iterations: 30,
alpha: 0.3,
seed: 1,
};
let s = grasp_routes(&m, 0, &units, RouteLimits::default(), o).unwrap();
assert!(s.total >= s.lower_bound - 1e-9);
assert!((route_length(&m, 0, &s.routes[0]) - s.total).abs() < 1e-9);
fn permutations(items: &[usize]) -> Vec<Vec<usize>> {
if items.len() <= 1 {
return vec![items.to_vec()];
}
let mut out = Vec::new();
for (k, &x) in items.iter().enumerate() {
let mut rest = items.to_vec();
rest.remove(k);
for mut p in permutations(&rest) {
p.insert(0, x);
out.push(p);
}
}
out
}
let opt = permutations(&units)
.iter()
.map(|p| route_length(&m, 0, p))
.fold(f64::INFINITY, f64::min);
assert!(
opt >= s.lower_bound - 1e-9,
"bound {} above optimum {opt}",
s.lower_bound
);
assert!(s.total <= opt * 1.15, "grasp {} vs optimum {opt}", s.total);
let data = vec![0.0, 1.0, 100.0, 100.0, 0.0, 1.0, 1.0, 100.0, 0.0];
let m = Matrix::from_vec(3, data).unwrap();
let s = grasp_routes(&m, 0, &[1, 2], RouteLimits::default(), o).unwrap();
assert!((s.total - 3.0).abs() < 1e-9);
assert!(s.lower_bound <= 3.0 + 1e-9);
}
#[test]
fn bound_is_valid_with_several_routes_without_triangle_inequality() {
let n = 4;
let data: Vec<f64> = (0..n * n)
.map(|k| {
let (i, j) = (k / n, k % n);
if i == j || i == 0 || j == 0 {
0.0
} else {
100.0
}
})
.collect();
let m = Matrix::from_vec(n, data).unwrap();
let limits = RouteLimits {
max_length: f64::INFINITY,
max_stops: 1,
};
let s = grasp_routes(&m, 0, &[1, 2, 3], limits, GraspOptions::default()).unwrap();
assert!(s.total.abs() < 1e-12);
assert!(s.lower_bound <= s.total + 1e-12);
}
#[test]
fn deterministic_for_a_seed() {
let m = square_points();
let units: Vec<usize> = (1..9).collect();
let o = GraspOptions {
iterations: 20,
alpha: 0.5,
seed: 11,
};
let a = grasp_routes(&m, 0, &units, RouteLimits::default(), o).unwrap();
let b = grasp_routes(&m, 0, &units, RouteLimits::default(), o).unwrap();
assert_eq!(a.routes, b.routes);
}
}