Package org.ddolib.examples.pdp

Class PDPFastLowerBound

java.lang.Object
org.ddolib.examples.pdp.PDPFastLowerBound
All Implemented Interfaces:
FastLowerBound<PDPState>
public class PDPFastLowerBound extends Object implements FastLowerBound<PDPState>
Provides a fast lower bound estimation for the Pickup and Delivery Problem (PDP).

This class implements the FastLowerBound interface and computes a quick lower bound on the remaining cost of a PDP state. The lower bound is based on the minimum distance of incident edges for each unvisited node, providing a heuristic for pruning suboptimal branches in decision diagram optimization (DDO) or ACS search.

Key features:

  • Precomputes the smallest edge incident to each node in the problem instance.
  • For a given state and a set of variables to assign, sums the smallest edges associated with the unvisited nodes to estimate a lower bound of the remaining cost.
  • Includes the starting node (typically node 0) in the estimation to account for the return or depot cost in PDP instances.
  • Designed for efficiency: uses precomputed values and simple selection logic to quickly estimate the bound.

This fast lower bound is particularly useful in search algorithms such as ACS, A*, or DDO to prune infeasible or suboptimal states and accelerate the solution process.

See Also:

  • Constructor Details

    • PDPFastLowerBound

      public PDPFastLowerBound(PDPProblem problem)
      Constructs a new fast lower bound estimator for a given PDP problem instance.
      Parameters:
      problem - the PDP problem instance containing the distance matrix and number of nodes

  • Method Details

    • fastLowerBound

      public double fastLowerBound(PDPState state, Set<Integer> variables)
      Computes a fast lower bound for a given state and a set of unassigned variables.
      Specified by:
      fastLowerBound in interface FastLowerBound<PDPState>
      Parameters:
      state - the current PDP state
      variables - the set of variables (nodes) that remain to be assigned
      Returns:
      a lower bound on the cost to complete the PDP from the given state