Analysis: Shaw Removal with Distance+Time Relatedness
Type
operator
Literature Context
Shaw (1998) introduced the concept of relatedness-based removal in LNS, where customers similar to a seed customer are removed together. The original formulation uses distance as the primary relatedness measure. Ropke & Pisinger (2006) extended this with time-window relatedness, showing that combined measures improve destroy operator effectiveness by 15-25% on CVRPTW instances.
Codebase Assessment
The routing-solver currently has 9 destroy operators in src/operators/destroy/. The existing RandomRemoval and WorstRemoval operators do not consider relatedness between customers. The operator pool at src/operators/operator_pool.rs uses adaptive weight selection (Ropke-Pisinger weights) — a new operator will be automatically incorporated.
The Route struct provides distance_between(i, j) and the Savelsbergh timing arrays provide earliest[i] and latest[i] for time-window relatedness computation. Delta evaluation for removal is already implemented via removal_cost_delta().
Expected Impact
Based on literature: 1.5-3% gap improvement on CVRPTW, smaller on pure CVRP (distance-only relatedness is already partially captured by worst removal). Solomon R1 instances expected to benefit most due to tight time windows.
Risks
The relatedness computation is O(n) per customer. With a removal size of ~30% of route length, the total cost is O(n * 0.3n) = O(n²). For 1000-customer instances this could slow the destroy phase. Mitigation: use k-nearest precomputation to limit the search space.
Design: Shaw Removal
Summary
Add a ShawRemoval destroy operator that scores customer relatedness using a weighted combination of distance (φ=0.4), time-window overlap (φ=0.3), and demand similarity (φ=0.3). Uses randomized selection with a determinism parameter p∈[0,1] controlling the balance between greedy and random removal.
Files to Modify
src/operators/destroy/shaw_removal.rs — new filesrc/operators/destroy/mod.rs — register operatorsrc/operators/operator_pool.rs — add to destroy pooltests/property_tests.rs — delta evaluation test
Algorithm
fn shaw_removal(solution, rng, count):
seed = rng.choose(solution.all_customers())
removed = {seed}
while removed.len() < count:
reference = rng.choose(&removed)
candidates = solution.customers() - removed
scored = candidates.map(|c| {
let dist = distance(reference, c) / max_distance
let time = |tw_start(ref) - tw_start(c)| / max_time_span
let demand = |demand(ref) - demand(c)| / max_demand
0.4 * dist + 0.3 * time + 0.3 * demand
})
scored.sort()
// Determinism: pick top-p% with randomization
let idx = (rng.random() ^ p) * scored.len()
removed.insert(scored[idx])
remove_all(solution, removed)
diff --git a/src/operators/destroy/shaw_removal.rs b/src/operators/destroy/shaw_removal.rs
new file mode 100644
index 0000000..a3f2b1c
@@ -0,0 +1,67 @@
+use crate::core::{Solution, Customer};
+use crate::operators::DestroyOperator;
+use rand::Rng;
+
+/// Shaw removal: relatedness-based customer removal.
+/// Combines distance, time-window, and demand similarity.
+pub struct ShawRemoval {
+ phi_distance: f64,
+ phi_time: f64,
+ phi_demand: f64,
+ determinism: f64,
+}
+
+impl ShawRemoval {
+ pub fn new() -> Self {
+ Self {
+ phi_distance: 0.4,
+ phi_time: 0.3,
+ phi_demand: 0.3,
+ determinism: 0.6,
+ }
+ }
+}
@@ -0,0 +25,42 @@
+impl DestroyOperator for ShawRemoval {
+ fn destroy(&self, solution: &mut Solution, rng: &mut impl Rng, count: usize) {
+ let seed = solution.random_customer(rng);
+ let mut removed = vec![seed];
+
+ while removed.len() < count {
+ let reference = removed[rng.gen_range(0..removed.len())];
+ let mut scored: Vec<(usize, f64)> = solution
+ .unremoved_customers()
+ .filter(|c| !removed.contains(c))
+ .map(|c| (c, self.relatedness(solution, reference, c)))
+ .collect();
+
+ scored.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
+ let idx = (rng.gen::().powf(self.determinism)
+ * scored.len() as f64) as usize;
+ removed.push(scored[idx.min(scored.len() - 1)].0);
+ }
+
+ for c in &removed {
+ solution.remove_customer(*c);
+ }
+ }
+}