solverforge_solver/heuristic/move/
k_opt.rs

1/* K-opt move for tour optimization.
2
3K-opt removes k edges from a tour and reconnects the resulting segments
4in a different order, potentially reversing some segments. This is a
5fundamental move for TSP and VRP optimization.
6
7# Zero-Erasure Design
8
9- Fixed arrays for cut points (no SmallVec for static data)
10- Reconnection pattern stored by value (`KOptReconnection` is `Copy`)
11- Concrete function pointers for all list operations
12
13# Example
14
15```
16use solverforge_solver::heuristic::r#move::{KOptMove, CutPoint};
17use solverforge_solver::heuristic::r#move::k_opt_reconnection::THREE_OPT_RECONNECTIONS;
18use solverforge_core::domain::PlanningSolution;
19use solverforge_core::score::SoftScore;
20
21#[derive(Clone, Debug)]
22struct Tour { cities: Vec<i32>, score: Option<SoftScore> }
23
24impl PlanningSolution for Tour {
25type Score = SoftScore;
26fn score(&self) -> Option<Self::Score> { self.score }
27fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
28}
29
30fn list_len(s: &Tour, _: usize) -> usize { s.cities.len() }
31fn sublist_remove(s: &mut Tour, _: usize, start: usize, end: usize) -> Vec<i32> {
32s.cities.drain(start..end).collect()
33}
34fn sublist_insert(s: &mut Tour, _: usize, pos: usize, items: Vec<i32>) {
35for (i, item) in items.into_iter().enumerate() {
36s.cities.insert(pos + i, item);
37}
38}
39
40// Create a 3-opt move with cuts at positions 2, 4, 6
41// This creates 4 segments: [0..2), [2..4), [4..6), [6..)
42let cuts = [
43CutPoint::new(0, 2),
44CutPoint::new(0, 4),
45CutPoint::new(0, 6),
46];
47let reconnection = &THREE_OPT_RECONNECTIONS[3]; // Swap middle segments
48
49let m = KOptMove::<Tour, i32>::new(
50&cuts,
51reconnection,
52list_len,
53sublist_remove,
54sublist_insert,
55"cities",
560,
57);
58```
59*/
60
61use std::borrow::Cow;
62use std::fmt::Debug;
63use std::marker::PhantomData;
64
65use solverforge_core::domain::PlanningSolution;
66use solverforge_scoring::Director;
67
68use super::k_opt_reconnection::KOptReconnection;
69use super::list_kernel::{
70    k_opt_do_move, k_opt_do_move_into, k_opt_is_doable, k_opt_tabu_signature, k_opt_undo_move,
71    StaticListWindowAccess,
72};
73use super::metadata::hash_str;
74use super::ListUndoJournal;
75use super::{Move, MoveTabuSignature};
76
77/* A cut point in a route, defining where an edge is removed.
78
79For k-opt, we have k cut points which divide the route into k+1 segments.
80
81# Example
82
83```
84use solverforge_solver::heuristic::r#move::CutPoint;
85
86// Cut at position 5 in entity 0
87let cut = CutPoint::new(0, 5);
88assert_eq!(cut.entity_index(), 0);
89assert_eq!(cut.position(), 5);
90```
91*/
92#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
93pub struct CutPoint {
94    // Entity (route/vehicle) index.
95    entity_index: usize,
96    // Position in the route where the cut occurs.
97    // The edge between position-1 and position is removed.
98    position: usize,
99}
100
101impl CutPoint {
102    #[inline]
103    pub const fn new(entity_index: usize, position: usize) -> Self {
104        Self {
105            entity_index,
106            position,
107        }
108    }
109
110    #[inline]
111    pub const fn entity_index(&self) -> usize {
112        self.entity_index
113    }
114
115    #[inline]
116    pub const fn position(&self) -> usize {
117        self.position
118    }
119}
120
121/// A k-opt move that removes k edges and reconnects segments.
122///
123/// This is the generalized k-opt move supporting k=2,3,4,5.
124/// For k=2, this is equivalent to a 2-opt (segment reversal).
125///
126/// # Zero-Erasure Design
127///
128/// - Fixed array `[CutPoint; 5]` for up to 5 cuts (5-opt)
129/// - `KOptReconnection` stored by value (`Copy` type, no heap allocation)
130/// - Concrete function pointers for list operations
131///
132/// # Type Parameters
133///
134/// * `S` - The planning solution type
135/// * `V` - The list element value type
136pub struct KOptMove<S, V> {
137    // Cut points (up to 5 for 5-opt).
138    cuts: [CutPoint; 5],
139    // Number of actual cuts (k value).
140    cut_count: u8,
141    // Reconnection pattern to apply (stored by value — `KOptReconnection` is `Copy`).
142    reconnection: KOptReconnection,
143    list_len: fn(&S, usize) -> usize,
144    list_get: fn(&S, usize, usize) -> Option<V>,
145    // Remove sublist [start, end), returns removed elements.
146    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
147    // Insert elements at position.
148    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
149    // Variable name.
150    variable_name: &'static str,
151    variable_id: u64,
152    // Descriptor index.
153    descriptor_index: usize,
154    // Entity index (for intra-route moves).
155    entity_index: usize,
156    _phantom: PhantomData<fn() -> V>,
157}
158
159impl<S, V: Debug> Debug for KOptMove<S, V> {
160    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
161        let cuts: Vec<_> = self.cuts[..self.cut_count as usize]
162            .iter()
163            .map(|c| c.position)
164            .collect();
165        f.debug_struct("KOptMove")
166            .field("k", &self.cut_count)
167            .field("entity", &self.entity_index)
168            .field("cuts", &cuts)
169            .field("reconnection", &self.reconnection)
170            .field("variable_name", &self.variable_name)
171            .finish()
172    }
173}
174
175impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static> KOptMove<S, V> {
176    /* Creates a new k-opt move.
177
178    # Arguments
179
180    * `cuts` - Slice of cut points (must be sorted by position for intra-route)
181    * `reconnection` - How to reconnect the segments
182    * `list_len` - Function to get list length
183    * `sublist_remove` - Function to remove a range
184    * `sublist_insert` - Function to insert elements
185    * `variable_name` - Name of the list variable
186    * `descriptor_index` - Entity descriptor index
187
188    # Panics
189
190    Panics if cuts is empty or has more than 5 elements.
191    */
192    #[allow(clippy::too_many_arguments)]
193    pub fn new(
194        cuts: &[CutPoint],
195        reconnection: &KOptReconnection,
196        list_len: fn(&S, usize) -> usize,
197        list_get: fn(&S, usize, usize) -> Option<V>,
198        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
199        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
200        variable_name: &'static str,
201        descriptor_index: usize,
202    ) -> Self {
203        Self::new_with_variable_id(
204            cuts,
205            reconnection,
206            list_len,
207            list_get,
208            sublist_remove,
209            sublist_insert,
210            variable_name,
211            hash_str(variable_name),
212            descriptor_index,
213        )
214    }
215
216    #[allow(clippy::too_many_arguments)]
217    pub(crate) fn new_with_variable_id(
218        cuts: &[CutPoint],
219        reconnection: &KOptReconnection,
220        list_len: fn(&S, usize) -> usize,
221        list_get: fn(&S, usize, usize) -> Option<V>,
222        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
223        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
224        variable_name: &'static str,
225        variable_id: u64,
226        descriptor_index: usize,
227    ) -> Self {
228        assert!(!cuts.is_empty() && cuts.len() <= 5, "k must be 1-5");
229
230        let mut cut_array = [CutPoint::default(); 5];
231        for (i, cut) in cuts.iter().enumerate() {
232            cut_array[i] = *cut;
233        }
234
235        // For now, assume intra-route (all cuts on same entity)
236        let entity_index = cuts[0].entity_index;
237
238        Self {
239            cuts: cut_array,
240            cut_count: cuts.len() as u8,
241            reconnection: *reconnection,
242            list_len,
243            list_get,
244            sublist_remove,
245            sublist_insert,
246            variable_name,
247            variable_id,
248            descriptor_index,
249            entity_index,
250            _phantom: PhantomData,
251        }
252    }
253
254    #[inline]
255    pub fn k(&self) -> usize {
256        self.cut_count as usize
257    }
258
259    #[inline]
260    pub fn cuts(&self) -> &[CutPoint] {
261        &self.cuts[..self.cut_count as usize]
262    }
263
264    pub fn is_intra_route(&self) -> bool {
265        let first = self.cuts[0].entity_index;
266        self.cuts[..self.cut_count as usize]
267            .iter()
268            .all(|c| c.entity_index == first)
269    }
270
271    fn access(&self) -> StaticListWindowAccess<S, V> {
272        StaticListWindowAccess {
273            list_len: self.list_len,
274            list_get: self.list_get,
275            sublist_remove: self.sublist_remove,
276            sublist_insert: self.sublist_insert,
277            variable_name: self.variable_name,
278            descriptor_index: self.descriptor_index,
279        }
280    }
281
282    /// Scratch-carrying do: the pre-kopt route is returned through the
283    /// caller-owned journal so its inlined capacity is reused across trials.
284    pub(crate) fn do_move_into_journal<D: Director<S>>(
285        &self,
286        score_director: &mut D,
287        journal: &mut ListUndoJournal<V>,
288    ) {
289        k_opt_do_move_into(
290            &self.access(),
291            self.cuts(),
292            &self.reconnection,
293            self.entity_index,
294            score_director,
295            journal,
296        );
297    }
298}
299
300impl<S, V> Move<S> for KOptMove<S, V>
301where
302    S: PlanningSolution,
303    V: Clone + Send + Sync + Debug + 'static,
304{
305    type Undo = ListUndoJournal<V>;
306
307    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
308        k_opt_is_doable(
309            &self.access(),
310            self.cuts(),
311            &self.reconnection,
312            self.entity_index,
313            score_director,
314        )
315    }
316
317    fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
318        k_opt_do_move(
319            &self.access(),
320            self.cuts(),
321            &self.reconnection,
322            self.entity_index,
323            score_director,
324        )
325    }
326
327    fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
328        k_opt_undo_move(&self.access(), self.entity_index, undo, score_director);
329    }
330
331    fn do_move_with_scratch<D: Director<S>>(
332        &self,
333        score_director: &mut D,
334        journal_pool: &mut Vec<Self::Undo>,
335    ) -> Self::Undo {
336        let mut journal = journal_pool.pop().unwrap_or_default();
337        k_opt_do_move_into(
338            &self.access(),
339            self.cuts(),
340            &self.reconnection,
341            self.entity_index,
342            score_director,
343            &mut journal,
344        );
345        journal
346    }
347
348    fn undo_move_with_scratch<D: Director<S>>(
349        &self,
350        score_director: &mut D,
351        undo: Self::Undo,
352        journal_pool: &mut Vec<Self::Undo>,
353    ) {
354        k_opt_undo_move(&self.access(), self.entity_index, undo, score_director);
355        journal_pool.push(ListUndoJournal::new());
356    }
357
358    fn descriptor_index(&self) -> usize {
359        self.descriptor_index
360    }
361
362    fn entity_indices(&self) -> &[usize] {
363        std::slice::from_ref(&self.entity_index)
364    }
365
366    fn variable_name(&self) -> &str {
367        self.variable_name
368    }
369
370    fn telemetry_label(&self) -> &'static str {
371        "k_opt"
372    }
373
374    fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> Cow<'_, MoveTabuSignature> {
375        Cow::Owned(k_opt_tabu_signature(
376            &self.access(),
377            self.cuts(),
378            &self.reconnection,
379            self.variable_id,
380            self.entity_index,
381            score_director,
382        ))
383    }
384}
solverforge_solver/heuristic/move/k_opt.rs

solverforge_solver/heuristic/move/
k_opt.rs
