1use 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}