Package org.ddolib.examples.tsptw

Class TSPTWFastLowerBound

java.lang.Object
org.ddolib.examples.tsptw.TSPTWFastLowerBound
All Implemented Interfaces:
FastLowerBound<TSPTWState>
public class TSPTWFastLowerBound extends Object implements FastLowerBound<TSPTWState>
Implementation of a fast lower bound for the Traveling Salesman Problem with Time Windows (TSPTW).

This class provides a heuristic lower bound on the total tour cost starting from a given TSPTWState. The lower bound is computed by summing the shortest available edges from the current position, including all mandatory nodes that must be visited and a selection of optional nodes if needed to complete the tour. The bound also considers returning to the depot and respects time window constraints.

If any mandatory node is unreachable from the current state, or if completing the tour is impossible within the time windows, the bound returns Integer.MAX_VALUE to indicate infeasibility.

Precomputes the cheapest outgoing edge for each node to speed up repeated lower bound calculations.

  • Constructor Details

    • TSPTWFastLowerBound

      public TSPTWFastLowerBound(TSPTWProblem problem)
      Constructs a fast lower bound calculator for a given TSPTW problem instance.
      Parameters:
      problem - The TSPTW problem instance.

  • Method Details

    • fastLowerBound

      public double fastLowerBound(TSPTWState state, Set<Integer> variables)
      Computes a fast lower bound on the remaining tour cost from the given state.

      The bound includes:

      • Distance to the closest next node from the current position
      • Distance covering all mandatory nodes to be visited
      • Distance covering optional nodes if necessary to complete the tour
      • Distance returning to the depot
      The calculation respects the time window constraints; if a tour is infeasible, INFINITY is returned.
      Specified by:
      fastLowerBound in interface FastLowerBound<TSPTWState>
      Parameters:
      state - The current state in the TSPTW problem.
      variables - The set of unassigned variables (nodes) to consider for the lower bound.
      Returns:
      A fast lower bound on the tour cost from the current state, or Integer.MAX_VALUE if infeasible.