solverforge_solver/heuristic/selector/k_opt/mod.rs
1/* K-opt move selector for tour optimization.
2
3Generates k-opt moves by enumerating all valid cut point combinations
4within selected entities and applying reconnection patterns.
5
6# Complexity
7
8For a route of length n and k-opt:
9- Full enumeration: O(n^k) cut combinations × reconnection patterns
10- Use `NearbyKOptMoveSelector` to reduce to O(n × m^(k-1)) with nearby selection
11
12# Example
13
14```
15use solverforge_solver::heuristic::selector::k_opt::{KOptMoveSelector, KOptConfig};
16use solverforge_solver::heuristic::selector::entity::FromSolutionEntitySelector;
17use solverforge_core::domain::PlanningSolution;
18use solverforge_core::score::SoftScore;
19
20#[derive(Clone, Debug)]
21struct Tour { cities: Vec<i32>, score: Option<SoftScore> }
22
23impl PlanningSolution for Tour {
24type Score = SoftScore;
25fn score(&self) -> Option<Self::Score> { self.score }
26fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
27}
28
29fn list_len(s: &Tour, _: usize) -> usize { s.cities.len() }
30fn sublist_remove(s: &mut Tour, _: usize, start: usize, end: usize) -> Vec<i32> {
31s.cities.drain(start..end).collect()
32}
33fn sublist_insert(s: &mut Tour, _: usize, pos: usize, items: Vec<i32>) {
34for (i, item) in items.into_iter().enumerate() {
35s.cities.insert(pos + i, item);
36}
37}
38
39let config = KOptConfig::new(3); // 3-opt
40
41let selector = KOptMoveSelector::<Tour, i32, _>::new(
42FromSolutionEntitySelector::new(0),
43config,
44list_len,
45sublist_remove,
46sublist_insert,
47"cities",
480,
49);
50```
51*/
52
53mod config;
54mod distance_meter;
55mod iterators;
56mod nearby;
57mod selector;
58#[cfg(test)]
59mod tests;
60
61pub use config::KOptConfig;
62pub use distance_meter::{DefaultDistanceMeter, ListPositionDistanceMeter};
63pub use iterators::{binomial, count_cut_combinations, CutCombinationIterator};
64pub use nearby::NearbyKOptMoveSelector;
65pub use selector::KOptMoveSelector;