Skip to main content

benchmark/
benchmark.rs

1//! Benchmark of the routing solver on TSPLIB (EUC_2D, single tour) and
2//! CVRPLIB set A (Augerat et al., capacity) instances.
3//!
4//! ```text
5//! cargo run --release --example benchmark -- <dir with .tsp/.vrp files> [iterations] [time limit in seconds]
6//! ```
7//! Distances are rounded to the nearest integer as the libraries do, so the
8//! costs compare directly with the published optima (the `Optimal value`
9//! comment of the .vrp files, or the table below for TSPLIB).
10
11use fieldopt_core::distance::Matrix;
12use fieldopt_core::routing::{solve_routes, GraspOptions, RouteLimits};
13use std::time::Instant;
14
15const TSPLIB_OPTIMA: &[(&str, f64)] = &[
16    ("eil51", 426.0),
17    ("berlin52", 7542.0),
18    ("st70", 675.0),
19    ("eil76", 538.0),
20    ("rat99", 1211.0),
21    ("kroA100", 21282.0),
22    ("eil101", 629.0),
23];
24
25struct Parsed {
26    name: String,
27    coords: Vec<(f64, f64)>,
28    demand: Vec<f64>,
29    capacity: f64,
30    depot: usize,
31    optimum: Option<f64>,
32}
33
34fn parse(path: &std::path::Path) -> Parsed {
35    let text = std::fs::read_to_string(path).expect("read instance");
36    let mut name = path.file_stem().unwrap().to_string_lossy().to_string();
37    let mut coords = Vec::new();
38    let mut demand = Vec::new();
39    let mut capacity = f64::INFINITY;
40    let mut depot = 0usize;
41    let mut optimum = None;
42    let mut section = "";
43    for line in text.lines() {
44        let l = line.trim();
45        if l.is_empty() {
46            continue;
47        }
48        if let Some(v) = l.strip_prefix("NAME") {
49            name = v.trim_start_matches([':', ' ']).trim().to_string();
50        } else if l.starts_with("COMMENT") {
51            if let Some(i) = l.find("Optimal value:") {
52                let rest: String = l[i + 14..]
53                    .chars()
54                    .filter(|c| c.is_ascii_digit() || *c == '.')
55                    .collect();
56                optimum = rest.parse().ok();
57            }
58        } else if let Some(v) = l.strip_prefix("CAPACITY") {
59            capacity = v.trim_start_matches([':', ' ']).trim().parse().unwrap();
60        } else if l.starts_with("NODE_COORD_SECTION") {
61            section = "coord";
62        } else if l.starts_with("DEMAND_SECTION") {
63            section = "demand";
64        } else if l.starts_with("DEPOT_SECTION") {
65            section = "depot";
66        } else if l.starts_with("EOF") {
67            break;
68        } else if l.contains(':') {
69            continue;
70        } else {
71            let nums: Vec<f64> = l
72                .split_whitespace()
73                .filter_map(|t| t.parse().ok())
74                .collect();
75            match section {
76                "coord" if nums.len() >= 3 => coords.push((nums[1], nums[2])),
77                "demand" if nums.len() >= 2 => demand.push(nums[1]),
78                "depot" if nums.len() == 1 && nums[0] >= 1.0 => depot = nums[0] as usize - 1,
79                _ => {}
80            }
81        }
82    }
83    if demand.is_empty() {
84        demand = vec![0.0; coords.len()];
85    }
86    if optimum.is_none() {
87        optimum = TSPLIB_OPTIMA
88            .iter()
89            .find(|(n, _)| *n == name)
90            .map(|(_, v)| *v);
91    }
92    Parsed {
93        name,
94        coords,
95        demand,
96        capacity,
97        depot,
98        optimum,
99    }
100}
101
102fn main() {
103    let args: Vec<String> = std::env::args().collect();
104    let dir = args.get(1).expect("directory with instances");
105    let iterations: usize = args.get(2).and_then(|v| v.parse().ok()).unwrap_or(2000);
106    let time_limit: f64 = args
107        .get(3)
108        .and_then(|v| v.parse().ok())
109        .unwrap_or(f64::INFINITY);
110    let mut files: Vec<_> = std::fs::read_dir(dir)
111        .expect("read dir")
112        .filter_map(|e| e.ok().map(|e| e.path()))
113        .filter(|p| {
114            matches!(
115                p.extension().and_then(|e| e.to_str()),
116                Some("tsp") | Some("vrp")
117            )
118        })
119        .collect();
120    files.sort();
121    println!(
122        "{:<12} {:>5} {:>7} {:>9} {:>9} {:>7} {:>8} {:>6}",
123        "instance", "n", "routes", "cost", "optimum", "gap%", "bound%", "sec"
124    );
125    for f in files {
126        let p = parse(&f);
127        let n = p.coords.len();
128        let mut data = vec![0.0; n * n];
129        for i in 0..n {
130            for j in 0..n {
131                let d = ((p.coords[i].0 - p.coords[j].0).powi(2)
132                    + (p.coords[i].1 - p.coords[j].1).powi(2))
133                .sqrt();
134                data[i * n + j] = d.round();
135            }
136        }
137        let m = Matrix::from_vec(n, data).unwrap();
138        let units: Vec<usize> = (0..n).filter(|&i| i != p.depot).collect();
139        let limits = RouteLimits {
140            max_length: f64::INFINITY,
141            max_stops: usize::MAX,
142            capacity: p.capacity,
143        };
144        let options = GraspOptions {
145            iterations,
146            time_limit,
147            alpha: 0.3,
148            seed: 1,
149        };
150        let start = Instant::now();
151        let sol = solve_routes(&m, p.depot, &units, &[], &p.demand, limits, options).unwrap();
152        let secs = start.elapsed().as_secs_f64();
153        let gap = p.optimum.map(|o| 100.0 * (sol.total - o) / o);
154        let bound_gap = 100.0 * (sol.total - sol.lower_bound) / sol.total;
155        println!(
156            "{:<12} {:>5} {:>7} {:>9.0} {:>9} {:>7} {:>8.2} {:>6.1}",
157            p.name,
158            units.len(),
159            sol.routes.len(),
160            sol.total,
161            p.optimum.map_or("?".to_string(), |o| format!("{o:.0}")),
162            gap.map_or("?".to_string(), |g| format!("{g:.2}")),
163            bound_gap,
164            secs
165        );
166    }
167}