Package org.ddolib.examples.alp

Class ALPFastLowerBound

java.lang.Object
org.ddolib.examples.alp.ALPFastLowerBound
All Implemented Interfaces:
FastLowerBound<ALPState>
public class ALPFastLowerBound extends Object implements FastLowerBound<ALPState>
Fast lower bound computation for the Aircraft Landing Problem (ALP).

This class implements the FastLowerBound interface for ALPState. It provides a heuristic estimation of the minimum total tardiness that can be achieved from a given state, considering only unassigned aircraft and ignoring conflicts that may arise from simultaneous assignments.

The heuristic works as follows:

  • For each aircraft class, it iterates over the remaining aircraft.
  • For each aircraft, it computes the estimated tardiness for each runway.
  • The minimum estimated tardiness across all runways is selected.
  • If an aircraft cannot be assigned to any runway without missing its deadline, the function returns Integer.MAX_VALUE to indicate an infeasible state.
  • The sum of these minimum tardiness values over all remaining aircraft is returned as the fast lower bound.
See Also:

  • Constructor Details

    • ALPFastLowerBound

      public ALPFastLowerBound(ALPProblem problem)
      Constructs a new fast lower bound evaluator for the given ALP problem.
      Parameters:
      problem - the ALP problem instance

  • Method Details

    • fastLowerBound

      public double fastLowerBound(ALPState state, Set<Integer> variables)
      Computes a heuristic lower bound of total tardiness from the given state.
      Specified by:
      fastLowerBound in interface FastLowerBound<ALPState>
      Parameters:
      state - the current state containing remaining aircraft and runway assignments
      variables - the set of variables (aircraft indices) that can still be assigned
      Returns:
      the estimated lower bound of total tardiness; Integer.MAX_VALUE if infeasible