Package org.ddolib.examples.alp

Class ALPProblem

java.lang.Object
org.ddolib.examples.alp.ALPProblem
All Implemented Interfaces:
Problem<ALPState>
public class ALPProblem extends Object implements Problem<ALPState>
Represents the Aircraft Landing Problem (ALP).

The ALP consists in scheduling the landing of a fleet of aircraft on one or multiple runways. Each aircraft has a target landing time and a deadline. The objective is to minimize the total deviation from target times (tardiness) while respecting deadlines and runway separation constraints.

Landing times are constrained by:

  • The previous aircraft landed on the same runway;
  • The minimum separation time between aircraft classes;
  • The aircraft’s target and deadline times.

This class implements the Problem interface for states of type ALPState. It defines the state space, the feasible domain of decisions, the transition function, and the cost function.

Fields:

  • nbClasses: Number of aircraft classes.
  • nbAircraft: Total number of aircraft.
  • nbRunways: Number of runways available.
  • aircraftClass: Array mapping each aircraft to its class.
  • aircraftTarget: Target landing time of each aircraft.
  • aircraftDeadline: Deadline for each aircraft.
  • classTransitionCost: Minimum separation times between classes.
  • optimal: Optional optimal value if known.
See Also:

  • Field Details

    • DUMMY

      public static final int DUMMY
      See Also:

    • nbClasses

      public final int nbClasses
      Number of aircraft classes.

    • nbAircraft

      public final int nbAircraft
      Total number of aircraft.

    • nbRunways

      public final int nbRunways
      Number of available runways.

    • aircraftClass

      public final int[] aircraftClass
      Mapping of each aircraft to its class.

    • aircraftTarget

      public final int[] aircraftTarget
      Target landing time for each aircraft.

    • aircraftDeadline

      public final int[] aircraftDeadline
      Deadline for each aircraft.

    • classTransitionCost

      public final int[][] classTransitionCost
      Minimum separation times between aircraft classes.

    • optimal

      public final Optional<Double> optimal
      Known optimal value, if available.

    • latestToEarliestAircraftByClass

      public ArrayList<ArrayList<Integer>> latestToEarliestAircraftByClass
      Used to know which aircraft of each class will be next to land.

  • Constructor Details

    • ALPProblem

      public ALPProblem(int nbClasses, int nbAircraft, int nbRunways, int[] aircraftClass, int[] aircraftTarget, int[] aircraftDeadline, int[][] classTransitionCost, Optional<Double> optimal)
      Constructs an ALP problem with the specified parameters.
      Parameters:
      nbClasses - Number of aircraft classes
      nbAircraft - Total number of aircraft
      nbRunways - Number of runways
      aircraftClass - Array mapping aircraft to class
      aircraftTarget - Target landing times
      aircraftDeadline - Deadline times
      classTransitionCost - Minimum separation times between classes
      optimal - Optional optimal value

    • ALPProblem

      public ALPProblem(int nbClasses, int nbAircraft, int nbRunways, int[] aircraftClass, int[] aircraftTarget, int[] aircraftDeadline, int[][] classTransitionCost)
      Constructs an ALP problem without specifying an optimal value.
      Parameters:
      nbClasses - Number of aircraft classes
      nbAircraft - Total number of aircraft
      nbRunways - Number of runways
      aircraftClass - Array mapping aircraft to class
      aircraftTarget - Target landing times
      aircraftDeadline - Deadline times
      classTransitionCost - Minimum separation times between classes

    • ALPProblem

      public ALPProblem(String fname) throws IOException
      Constructs an ALP problem by reading from a file.

      The file format is expected to provide the number of aircraft, classes, runways, optionally the known optimal value, aircraft target and deadline times, and class separation costs.

      Parameters:
      fname - Path to the input file
      Throws:
      IOException - if the file cannot be read

  • Method Details

    • getArrivalTime

      public int getArrivalTime(RunwayState[] runwayStates, int aircraft, int runway)
      Computes the arrival time of an aircraft on a given runway.
      Parameters:
      runwayStates - The current state of each runway
      aircraft - The aircraft to land
      runway - The runway index
      Returns:
      The computed landing time

    • toDecision

      public int toDecision(ALPDecision decision)
      Converts an ALPDecision to its integer representation.
      Parameters:
      decision - The decision
      Returns:
      The integer encoding of the decision

    • fromDecision

      public ALPDecision fromDecision(int value)
      Restores an ALPDecision from its integer representation.
      Parameters:
      value - The integer encoding
      Returns:
      The decoded decision

    • nbVars

      public int nbVars()
      Specified by:
      nbVars in interface Problem<ALPState>
      Returns:
      the total number of decision variables in this problem

    • initialState

      public ALPState initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<ALPState>
      Returns:
      the state representing the starting point of the optimization

    • initialValue

      public double initialValue()
      Description copied from interface: Problem
      Returns the initial objective value associated with the initial state.
      Specified by:
      initialValue in interface Problem<ALPState>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(ALPState state, int var)
      Description copied from interface: Problem
      Returns the domain of possible values for a given variable when applied to a specific state.
      Specified by:
      domain in interface Problem<ALPState>
      Parameters:
      state - the current state
      var - the variable index whose domain is queried
      Returns:
      an iterator over all feasible values for the variable in this state

    • transition

      public ALPState transition(ALPState state, Decision decision)
      Description copied from interface: Problem
      Applies a decision to a state, computing the next state according to the problem's transition function.
      Specified by:
      transition in interface Problem<ALPState>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the resulting state after applying the decision

    • transitionCost

      public double transitionCost(ALPState state, Decision decision)
      Description copied from interface: Problem
      Computes the change in objective value resulting from applying a decision to a given state.
      Specified by:
      transitionCost in interface Problem<ALPState>
      Parameters:
      state - the state from which the transition originates
      decision - the decision to apply
      Returns:
      the incremental objective cost/value associated with this decision

    • optimalValue

      public Optional<Double> optimalValue()
      Description copied from interface: Problem
      Returns the known optimal value of the problem, if available.

      Note: This value should correspond to the expected output of the solver. For maximization problems, be careful with negative values.

      Specified by:
      optimalValue in interface Problem<ALPState>
      Returns:
      an Optional containing the known optimal value, or empty if unknown

    • evaluate

      public double evaluate(int[] solution) throws InvalidSolutionException
      Description copied from interface: Problem
      Given a solution such that solution[i] is the value of the variable x_i, returns the value of this solution and checks if the solution respects the problem's constraints.

      Note: For maximization problems, the returned value is minus the computed value.

      Specified by:
      evaluate in interface Problem<ALPState>
      Parameters:
      solution - A solution of the problem.
      Returns:
      The value of the input solution
      Throws:
      InvalidSolutionException - If the solution does not respect problem's constraints.

    • toString

      public String toString()
      Overrides:
      toString in class Object