Package org.ddolib.examples.tsp

Class TSPGenerator

java.lang.Object
org.ddolib.examples.tsp.TSPGenerator
public class TSPGenerator extends Object
Class to generate and handle instances of the Traveling Salesman Problem (TSP).

This class provides functionality to:

  • Create TSP instances from a distance matrix (int[][] or double[][]).
  • Create Euclidean TSP instances by sampling coordinates within a square.
  • Create Euclidean TSP instances from given x/y coordinates.
  • Access distances between cities and the number of cities.
  • Save a TSP instance in XML format following the XML-TSPLIB standard.

The class maintains an internal distance matrix representing the cost between cities and optionally stores the objective value (best known solution).

Example usage: 

     // Generate a Euclidean TSP instance with 10 cities
     TSPGenerator tsp = new TSPGenerator(10, 42, 100);
     double dist = tsp.distance(0, 1);
     tsp.saveXml("instance.xml", 1234);
Author:
Pierre Schaus

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    double[][]
    distanceMatrix
    Distance matrix between cities
    int
    n
    Number of cities
    final double
    objective
    Best known objective value (optional, -1 if unknown)

  • Constructor Summary

    Constructors
    Constructor
    Description
    TSPGenerator(double[][] distanceMatrix)
    Constructs a TSP instance from a double[][] distance matrix.
    TSPGenerator(int[][] distanceMatrix)
    Constructs a TSP instance from an int[][] distance matrix.
    TSPGenerator(int[] xCoord, int[] yCoord)
    Constructs a Euclidean TSP instance from given x/y coordinates.
    TSPGenerator(int n, int seed, int squareLength)
    Constructs a Euclidean TSP instance by randomly sampling coordinates in a square.

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    dist(double x1, double y1, double x2, double y2)
    Computes the Euclidean distance between two points.
    double
    distance(int city1, int city2)
    Returns the distance between two cities.
    int
    nCities()
    Returns the number of cities in the instance.
    void
    saveXml(String path, int objective)
    Saves the TSP instance in XML format following XML-TSPLIB standards.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • distanceMatrix

      public double[][] distanceMatrix
      Distance matrix between cities

    • n

      public int n
      Number of cities

    • objective

      public final double objective
      Best known objective value (optional, -1 if unknown)

  • Constructor Details

    • TSPGenerator

      public TSPGenerator(double[][] distanceMatrix)
      Constructs a TSP instance from a double[][] distance matrix.
      Parameters:
      distanceMatrix - the distance matrix

    • TSPGenerator

      public TSPGenerator(int[][] distanceMatrix)
      Constructs a TSP instance from an int[][] distance matrix.
      Parameters:
      distanceMatrix - the distance matrix

    • TSPGenerator

      public TSPGenerator(int n, int seed, int squareLength)
      Constructs a Euclidean TSP instance by randomly sampling coordinates in a square.
      Parameters:
      n - number of cities
      seed - random seed for reproducibility
      squareLength - length of the square in which coordinates are sampled

    • TSPGenerator

      public TSPGenerator(int[] xCoord, int[] yCoord)
      Constructs a Euclidean TSP instance from given x/y coordinates.
      Parameters:
      xCoord - array of x-coordinates
      yCoord - array of y-coordinates

  • Method Details

    • nCities

      public int nCities()
      Returns the number of cities in the instance.
      Returns:
      the number of cities

    • distance

      public double distance(int city1, int city2)
      Returns the distance between two cities.
      Parameters:
      city1 - first city index
      city2 - second city index
      Returns:
      distance between city1 and city2

    • dist

      public double dist(double x1, double y1, double x2, double y2)
      Computes the Euclidean distance between two points.
      Parameters:
      x1 - x-coordinate of first point
      y1 - y-coordinate of first point
      x2 - x-coordinate of second point
      y2 - y-coordinate of second point
      Returns:
      Euclidean distance between the points

    • saveXml

      public void saveXml(String path, int objective)
      Saves the TSP instance in XML format following XML-TSPLIB standards.
      Parameters:
      path - path to the XML file
      objective - best known solution value