Module org.cicirello.chips_n_salsa
Package org.cicirello.search.problems.tsp

Class RandomTSPMatrix.Double

java.lang.Object
org.cicirello.search.problems.tsp.BaseTSP
org.cicirello.search.problems.tsp.RandomTSPMatrix
org.cicirello.search.problems.tsp.RandomTSPMatrix.Double
All Implemented Interfaces:
OptimizationProblem<Permutation>, Problem<Permutation>
Enclosing class:
RandomTSPMatrix
public static final class RandomTSPMatrix.Double extends RandomTSPMatrix implements OptimizationProblem<Permutation>
This class implements the Traveling Salesperson Problem (TSP), and its variant, the Asymmetric Traveling Salesperson Problem (ATSP), by generating a random distance matrix, with floating-point cost edges. It supports both the TSP and ATSP, and also provides the option to control whether or not the distance matrix satisfies the triangle inequality.

The random distance matrix is generated via an approach based on that of the paper: Cirasella J., Johnson D.S., McGeoch L.A., Zhang W. (2001) The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests. In Algorithm Engineering and Experimentation (ALENEX 2001). There are some minor differences between the approach described in that paper and the approach of this class. This class generates random floating-point distances, whereas the approach described in that paper uses integer valued distances.

  • Nested Class Summary

    Nested classes/interfaces inherited from class org.cicirello.search.problems.tsp.RandomTSPMatrix

    RandomTSPMatrix.Double, RandomTSPMatrix.Integer

  • Constructor Summary

    Constructors
    Constructor
    Description
    Double(double[][] distance)
    Although the focus of this class is generating random TSP and ATSP instances, this constructor enables specifying the distance matrix directly.
    Double(int n, double maxDistance)
    Generates a random instance of either the TSP.
    Double(int n, double maxDistance, boolean symmetric)
    Generates a random instance of either the TSP or ATSP.
    Double(int n, double maxDistance, boolean symmetric, boolean triangleInequality)
    Generates a random instance of either the TSP or ATSP.
    Double(int n, double maxDistance, boolean symmetric, boolean triangleInequality, long seed)
    Generates a random instance of either the TSP or ATSP.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    cost(Permutation candidate)
    Computes the cost of a candidate solution to the problem instance.
    final double
    getDistance(int i, int j)
    Gets the distance (i.e., cost) of an edge.
    final int
    length()
    Gets the number of cities in the TSP instance.
    double
    minCost()
    A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution.
    double
    value(Permutation candidate)
    Computes the value of the candidate solution within the usual constraints and interpretation of the problem.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface org.cicirello.search.problems.OptimizationProblem

    costAsDouble, getSolutionCostPair, isMinCost

  • Constructor Details

    • Double

      public Double(int n, double maxDistance)
      Generates a random instance of either the TSP. The instances generated by this constructor may not satisfy the triangle inequality. If you desire an instance that satisfies the triangle inequality, see the other constructors. The distance matrix generated by this constructor is symmetric. See the other constructors for the ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [0, maxDistance].
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 0.0.

    • Double

      public Double(int n, double maxDistance, boolean symmetric)
      Generates a random instance of either the TSP or ATSP. The instances generated by this constructor may not satisfy the triangle inequality. If you desire an instance that satisfies the triangle inequality, see the other constructors.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [0, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 0.0.

    • Double

      public Double(int n, double maxDistance, boolean symmetric, boolean triangleInequality)
      Generates a random instance of either the TSP or ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [0, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      triangleInequality - Pass true if you want the generated distance matrix to respect the triangle inequality, or false for purely random distances.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 0.0.

    • Double

      public Double(int n, double maxDistance, boolean symmetric, boolean triangleInequality, long seed)
      Generates a random instance of either the TSP or ATSP.
      Parameters:
      n - The number of cities.
      maxDistance - The maximum distance between cities. The edge costs between pairs of cities are uniform in the interval [0, maxDistance].
      symmetric - Pass true for the TSP, or false for the ATSP.
      triangleInequality - Pass true if you want the generated distance matrix to respect the triangle inequality, or false for purely random distances.
      seed - The seed for the random number generator to enable reproducing the same instance for experiment reproducibility.
      Throws:
      IllegalArgumentException - if n < 2.
      IllegalArgumentException - if maxDistance < 0.0.

    • Double

      public Double(double[][] distance)
      Although the focus of this class is generating random TSP and ATSP instances, this constructor enables specifying the distance matrix directly.
      Parameters:
      distance - The distance matrix, such that distance[i][j] is the distance from city i to city j. The distance matrix must be square, with same number of rows as columns, and whose dimension determines number of cities. Dimensions must be at least 2 by 2.
      Throws:
      IllegalArgumentException - if distance is not at least a 2 by 2 array.
      IllegalArgumentException - if number of rows is not same as number of columns, or if rows don't all have same length.

  • Method Details

    • getDistance

      public final double getDistance(int i, int j)
      Gets the distance (i.e., cost) of an edge.
      Parameters:
      i - The source city.
      j - The destination city.
      Returns:
      The distance from i to j

    • length

      public final int length()
      Gets the number of cities in the TSP instance.
      Specified by:
      length in class BaseTSP
      Returns:
      number of cities

    • cost

      public double cost(Permutation candidate)
      Description copied from interface: OptimizationProblem
      Computes the cost of a candidate solution to the problem instance. The lower the cost, the more optimal the candidate solution.
      Specified by:
      cost in interface OptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The cost of the candidate solution. Lower cost means better solution.

    • value

      public double value(Permutation candidate)
      Description copied from interface: OptimizationProblem
      Computes the value of the candidate solution within the usual constraints and interpretation of the problem.
      Specified by:
      value in interface OptimizationProblem<Permutation>
      Parameters:
      candidate - The candidate solution to evaluate.
      Returns:
      The actual optimization value of the candidate solution.

    • minCost

      public double minCost()
      Description copied from interface: OptimizationProblem
      A lower bound on the minimum theoretical cost across all possible solutions to the problem instance, where lower cost implies better solution. The default implementation returns Double.NEGATIVE_INFINITY.
      Specified by:
      minCost in interface OptimizationProblem<Permutation>
      Returns:
      A lower bound on the minimum theoretical cost of the problem instance.