Package org.ddolib.examples.tsptw

Class TSPTWProblem

java.lang.Object
org.ddolib.examples.tsptw.TSPTWProblem
All Implemented Interfaces:
Problem<TSPTWState>
public class TSPTWProblem extends Object implements Problem<TSPTWState>
Class representing an instance of the Traveling Salesman Problem with Time Windows (TSPTW).

Each node has a time window during which it must be visited, and travel between nodes is defined by a distance matrix. This class implements the Problem interface for use in decision diagram solvers.

The problem instance can optionally provide the known optimal solution.

Data file format

  • First line: number of nodes (variables). Optionally, a second value may be provided for the optimal objective.
  • Next lines: the distance matrix, one row per node.
  • Following lines: time windows for each node, specified as two integers (start and end) per line.

The distance matrix defines the travel times between nodes, and the TimeWindow array defines the allowed visit times for each node.

  • Field Details

    • distance

      public final int[][] distance
      Distance matrix between nodes. distance[i][j] is the travel time from node i to node j.

    • timeWindows

      public final TimeWindow[] timeWindows
      Time windows for each node.

    • optimal

      public final Optional<Double> optimal
      Optional known optimal value for the instance.

  • Constructor Details

    • TSPTWProblem

      public TSPTWProblem(String fname) throws IOException
      Constructs a TSPTW problem instance from a data file.
      Parameters:
      fname - Path to the input file containing the TSPTW instance.
      Throws:
      IOException - If an error occurs while reading the file.

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nbVars

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

    • initialState

      public TSPTWState initialState()
      Description copied from interface: Problem
      Returns the initial state of the problem.
      Specified by:
      initialState in interface Problem<TSPTWState>
      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<TSPTWState>
      Returns:
      the starting value of the objective function

    • domain

      public Iterator<Integer> domain(TSPTWState 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<TSPTWState>
      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 TSPTWState transition(TSPTWState 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<TSPTWState>
      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(TSPTWState 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<TSPTWState>
      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<TSPTWState>
      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<TSPTWState>
      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.