Struct ListRegretInsertionPhase 

pub struct ListRegretInsertionPhase<S, E>
where
    S: PlanningSolution,
    E: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
{ /* private fields */ }

List construction phase using regret-based insertion.

Extends cheapest insertion by selecting the element with the highest regret at each step. Regret is defined as the score difference between the best and second-best insertion positions for an element.

Inserting high-regret elements first prevents “greedy theft” where easy elements consume the best slots before harder-to-place elements are considered.

Algorithm

while there are unassigned elements:
    for each unassigned element e:
        find best insertion (score_1, position_1)
        find second-best insertion (score_2, position_2)
        regret(e) = score_1 - score_2   (higher = more urgent)
    select element e* with maximum regret
    permanently insert e* at position_1(e*)

Complexity: O(E² × N × M) — quadratic in elements because we re-evaluate all remaining elements each step. This is more expensive than cheapest insertion but produces better solutions.

Example

use solverforge_solver::ListRegretInsertionPhase;
use solverforge_core::domain::PlanningSolution;
use solverforge_core::score::SimpleScore;

#[derive(Clone)]
struct Vehicle { visits: Vec<usize> }

#[derive(Clone)]
struct Plan { vehicles: Vec<Vehicle>, n_visits: usize, score: Option<SimpleScore> }

impl PlanningSolution for Plan {
    type Score = SimpleScore;
    fn score(&self) -> Option<Self::Score> { self.score }
    fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
}

fn list_len(s: &Plan, e: usize) -> usize {
    s.vehicles.get(e).map_or(0, |v| v.visits.len())
}
fn list_insert(s: &mut Plan, e: usize, pos: usize, val: usize) {
    if let Some(v) = s.vehicles.get_mut(e) { v.visits.insert(pos, val); }
}
fn list_remove(s: &mut Plan, e: usize, pos: usize) -> usize {
    s.vehicles.get_mut(e).map(|v| v.visits.remove(pos)).unwrap_or(0)
}

let phase = ListRegretInsertionPhase::<Plan, usize>::new(
    |p| p.n_visits,
    |p| p.vehicles.iter().flat_map(|v| v.visits.iter().copied()).collect(),
    |p| p.vehicles.len(),
    list_len,
    list_insert,
    list_remove,
    |idx| idx,
    "visits",
    0,
);

Implementations

impl<S, E> ListRegretInsertionPhase<S, E>

where S: PlanningSolution, E: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,

pub fn new( element_count: fn(&S) -> usize, get_assigned: fn(&S) -> Vec<E>, entity_count: fn(&S) -> usize, list_len: fn(&S, usize) -> usize, list_insert: fn(&mut S, usize, usize, E), list_remove: fn(&mut S, usize, usize) -> E, index_to_element: fn(usize) -> E, variable_name: &'static str, descriptor_index: usize, ) -> Self

Creates a new regret insertion phase.

Arguments

• element_count - Total number of elements to assign
• get_assigned - Returns currently assigned elements
• entity_count - Total number of entities (routes/vehicles)
• list_len - Length of entity’s list
• list_insert - Insert element at position (shifts right)
• list_remove - Remove element at position (used for undo), returns removed element
• index_to_element - Converts element index to element value
• variable_name - Name of the list variable
• descriptor_index - Entity descriptor index

Trait Implementations

impl<S, E> Debug for ListRegretInsertionPhase<S, E>

where S: PlanningSolution, E: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<S, E, D> Phase<S, D> for ListRegretInsertionPhase<S, E>

where S: PlanningSolution, E: Copy + PartialEq + Eq + Hash + Send + Sync + 'static, D: ScoreDirector<S>,

fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D>)

Executes this phase.

fn phase_type_name(&self) -> &'static str

Returns the name of this phase type.