Package org.ddolib.examples.tsptw

Class TSPTWDominance

java.lang.Object
org.ddolib.examples.tsptw.TSPTWDominance
All Implemented Interfaces:
Dominance<TSPTWState>
public class TSPTWDominance extends Object implements Dominance<TSPTWState>
Dominance relation for the Traveling Salesman Problem with Time Windows (TSPTW).

This class defines a dominance rule between two TSPTWState instances. Two states are comparable if they share the same current position and the same set of remaining locations to visit (mustVisit). Among such comparable states, the state with the lower current time dominates the other.

Dominance is used to prune the search space: if a state is dominated by another, it can be safely discarded without losing optimality.

  • Constructor Details

    • TSPTWDominance

      public TSPTWDominance()

  • Method Details

    • getKey

      public TSPTWDominanceKey getKey(TSPTWState state)
      Returns the dominance key for a given state, based on its current position and the set of locations that still must be visited.
      Specified by:
      getKey in interface Dominance<TSPTWState>
      Parameters:
      state - The state for which to compute the dominance key.
      Returns:
      The TSPTWDominanceKey representing the key of this state.

    • isDominatedOrEqual

      public boolean isDominatedOrEqual(TSPTWState state1, TSPTWState state2)
      Checks whether state1 is dominated by or equal to state2.

      state1 is considered dominated or equal to state2 if it has the same position and mustVisit set, and its current time is greater than or equal to that of state2.

      Specified by:
      isDominatedOrEqual in interface Dominance<TSPTWState>
      Parameters:
      state1 - The state being tested for dominance.
      state2 - The state to compare against.
      Returns:
      true if state1 is dominated by or equal to state2, false otherwise.