Package org.ddolib.examples.pdp

Class PDPProblem

java.lang.Object
org.ddolib.examples.pdp.PDPProblem
All Implemented Interfaces:
Problem<PDPState>
public class PDPProblem extends Object implements Problem<PDPState>
Represents a Pickup and Delivery Problem (PDP) instance with a single vehicle.

In this problem:

  • Nodes may be grouped into pickup-delivery pairs, where a pickup node must be visited before its associated delivery node.
  • There may also be unrelated nodes that are not part of any pair.
  • The vehicle has a capacity limit that restricts how many pickups can be carried simultaneously.
  • The problem is represented as a TSP-like graph with distances between nodes.

The class implements the Problem interface, providing methods for:

States are represented by PDPState, including:

  • The set of currently visited nodes
  • The set of nodes still to visit
  • The current vehicle load

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final double[][]
    distanceMatrix
    Distance matrix between all nodes.
    final int
    maxCapa
    Maximum capacity of the vehicle.
    int
    n
    Number of nodes in the problem.
    HashMap<Integer,Integer>
    pickupToAssociatedDelivery
    Map of pickup nodes to their associated delivery nodes.
    Set<Integer>
    unrelatedNodes
    Set of nodes that are not part of any pickup-delivery pair.

  • Constructor Summary

    Constructors
    Constructor
    Description
    PDPProblem(double[][] distanceMatrix, HashMap<Integer,Integer> pickupToAssociatedDelivery, int maxCapa)
    Constructs a PDPProblem from a distance matrix, a map of pickup-delivery pairs, and a maximum vehicle capacity.
    PDPProblem(String fname)
    Constructs a PDPProblem by reading an instance from a file.

  • Method Summary

    Modifier and Type
    Method
    Description
    Iterator<Integer>
    domain(PDPState state, int var)
    Returns the domain of possible decisions (nodes to visit) from a given state and variable index.
    double
    eval(int[] solution)
    Evaluates a solution represented as an array of node indices.
    double
    evaluate(int[] solution)
    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.
    PDPState
    initialState()
    Returns the initial state of the problem.
    double
    initialValue()
    Returns the initial value of the problem.
    int
    nbVars()
    Returns the number of variables (decisions) in the problem.
    Optional<Double>
    optimalValue()
    Returns the known optimal value of the problem, if available.
    BitSet
    singleton(int singletonValue)
     
    String
    toString()
    Returns a string representation of the PDP instance.
    PDPState
    transition(PDPState state, Decision decision)
    Computes the next state given a current state and a decision.
    double
    transitionCost(PDPState state, Decision decision)
    Computes the cost of transitioning from a state via a decision.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • distanceMatrix

      public final double[][] distanceMatrix
      Distance matrix between all nodes.

    • maxCapa

      public final int maxCapa
      Maximum capacity of the vehicle.

    • n

      public int n
      Number of nodes in the problem.

    • pickupToAssociatedDelivery

      public HashMap<Integer,Integer> pickupToAssociatedDelivery
      Map of pickup nodes to their associated delivery nodes.

    • unrelatedNodes

      public Set<Integer> unrelatedNodes
      Set of nodes that are not part of any pickup-delivery pair.

  • Constructor Details

    • PDPProblem

      public PDPProblem(double[][] distanceMatrix, HashMap<Integer,Integer> pickupToAssociatedDelivery, int maxCapa)
      Constructs a PDPProblem from a distance matrix, a map of pickup-delivery pairs, and a maximum vehicle capacity.
      Parameters:
      distanceMatrix - distance matrix between all nodes
      pickupToAssociatedDelivery - mapping from pickup nodes to delivery nodes
      maxCapa - maximum capacity of the vehicle

    • PDPProblem

      public PDPProblem(String fname) throws IOException
      Constructs a PDPProblem by reading an instance from a file.

      The file format should include:

      • The number of nodes and optionally the optimal value.
      • The distance matrix between nodes.
      • The pickup-delivery pairs.
      Parameters:
      fname - path to the instance file
      Throws:
      IOException - if the file cannot be read

  • Method Details

    • nbVars

      public int nbVars()
      Returns the number of variables (decisions) in the problem.

      Note: the last decision corresponds to returning to the depot (node 0).

      Specified by:
      nbVars in interface Problem<PDPState>
      Returns:
      number of variables

    • initialState

      public PDPState initialState()
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<PDPState>
      Returns:
      initial PDPState with vehicle at the depot and all other nodes unvisited

    • initialValue

      public double initialValue()
      Returns the initial value of the problem.
      Specified by:
      initialValue in interface Problem<PDPState>
      Returns:
      0

    • domain

      public Iterator<Integer> domain(PDPState state, int var)
      Returns the domain of possible decisions (nodes to visit) from a given state and variable index.
      Specified by:
      domain in interface Problem<PDPState>
      Parameters:
      state - current PDPState
      var - index of the decision variable
      Returns:
      iterator over possible node indices for the decision

    • transition

      public PDPState transition(PDPState state, Decision decision)
      Computes the next state given a current state and a decision.
      Specified by:
      transition in interface Problem<PDPState>
      Parameters:
      state - current PDPState
      decision - the Decision made
      Returns:
      new PDPState after applying the decision

    • transitionCost

      public double transitionCost(PDPState state, Decision decision)
      Computes the cost of transitioning from a state via a decision.

      Typically corresponds to the travel distance from the current node to the chosen node.

      Specified by:
      transitionCost in interface Problem<PDPState>
      Parameters:
      state - current PDPState
      decision - the Decision made
      Returns:
      cost of the transition

    • optimalValue

      public Optional<Double> optimalValue()
      Returns the known optimal value of the problem, if available.
      Specified by:
      optimalValue in interface Problem<PDPState>
      Returns:
      optional optimal value

    • 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<PDPState>
      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.

    • singleton

      public BitSet singleton(int singletonValue)

    • toString

      public String toString()
      Returns a string representation of the PDP instance.
      Overrides:
      toString in class Object
      Returns:
      string describing the PDP instance

    • eval

      public double eval(int[] solution)
      Evaluates a solution represented as an array of node indices.
      Parameters:
      solution - array of node indices representing the route
      Returns:
      total distance of the solution, or -1 if it violates vehicle capacity