Class TwoOptHeuristicTSP<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
org.jgrapht.alg.tour.TwoOptHeuristicTSP<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>, HamiltonianCycleImprovementAlgorithm<V,E>

public class TwoOptHeuristicTSP<V,E> extends HamiltonianCycleAlgorithmBase<V,E> implements HamiltonianCycleImprovementAlgorithm<V,E>
The 2-opt heuristic algorithm for the TSP problem.

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?".

This is an implementation of the 2-opt improvement heuristic algorithm. The algorithm generates passes initial tours and then iteratively improves the tours until a local minimum is reached. In each iteration it applies the best possible 2-opt move which means to find the best pair of edges $(i,i+1)$ and $(j,j+1)$ such that replacing them with $(i,j)$ and $(i+1,j+1)$ minimizes the tour length. The default initial tours use RandomTour, however an alternative algorithm can be provided to create the initial tour. Initial tours generated using NearestNeighborHeuristicTSP give good results and performance.

See wikipedia for more details.

This implementation can also be used in order to try to improve an existing tour. See method improveTour(GraphPath).

  • Field Details

    • passes

      private final int passes
    • initializer

      private final HamiltonianCycleAlgorithm<V,E> initializer
    • minCostImprovement

      private final double minCostImprovement
    • graph

      private Graph<V,E> graph
    • n

      private int n
    • dist

      private double[][] dist
    • index

      private Map<V,Integer> index
    • revIndex

      private List<V> revIndex
  • Constructor Details

    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP()
      Constructor. By default one initial random tour is used.
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes)
      Constructor
      Parameters:
      passes - how many initial random tours to check
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes, long seed)
      Constructor
      Parameters:
      passes - how many initial random tours to check
      seed - seed for the random number generator
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes, Random rng)
      Constructor
      Parameters:
      passes - how many initial random tours to check
      rng - random number generator
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes, Random rng, double minCostImprovement)
      Constructor
      Parameters:
      passes - how many initial random tours to check
      rng - random number generator
      minCostImprovement - Minimum cost improvement per iteration
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(HamiltonianCycleAlgorithm<V,E> initializer)
      Constructor
      Parameters:
      initializer - Algorithm to generate initial tour
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes, HamiltonianCycleAlgorithm<V,E> initializer)
      Constructor
      Parameters:
      passes - how many initial tours to check
      initializer - Algorithm to generate initial tour
    • TwoOptHeuristicTSP

      public TwoOptHeuristicTSP(int passes, HamiltonianCycleAlgorithm<V,E> initializer, double minCostImprovement)
      Constructor
      Parameters:
      passes - how many initial tours to check
      initializer - Algorithm to generate initial tours
      minCostImprovement - Minimum cost improvement per iteration
  • Method Details

    • getTour

      public GraphPath<V,E> getTour(Graph<V,E> graph)
      Computes a 2-approximate tour.
      Specified by:
      getTour in interface HamiltonianCycleAlgorithm<V,E>
      Parameters:
      graph - the input graph
      Returns:
      a tour
      Throws:
      IllegalArgumentException - if the graph is not undirected
      IllegalArgumentException - if the graph is not complete
      IllegalArgumentException - if the graph contains no vertices
    • improveTour

      public GraphPath<V,E> improveTour(GraphPath<V,E> tour)
      Try to improve a tour by running the 2-opt heuristic.
      Specified by:
      improveTour in interface HamiltonianCycleImprovementAlgorithm<V,E>
      Parameters:
      tour - a tour
      Returns:
      a possibly improved tour
    • init

      private void init(Graph<V,E> graph)
      Initialize graph and mapping to integer vertices.
      Parameters:
      graph - the input graph
    • createInitialTour

      private int[] createInitialTour()
      Create an initial tour
      Returns:
      a complete tour
    • improve

      private int[] improve(int[] tour)
      Improve the tour using the 2-opt heuristic. In each iteration it applies the best possible 2-opt move which means to find the best pair of edges $(i,i+1)$ and $(j,j+1)$ such that replacing them with $(i,j)$ and $(i+1,j+1)$ minimizes the tour length.

      The returned array instance might or might not be the input array.

      Parameters:
      tour - the input tour
      Returns:
      a possibly improved tour
    • tourToPath

      private GraphPath<V,E> tourToPath(int[] tour)
      Transform from an array representation to a graph path.
      Parameters:
      tour - an array containing the index of the vertices of the tour
      Returns:
      a graph path
    • pathToTour

      private int[] pathToTour(GraphPath<V,E> path)
      Transform from a path representation to an array representation.
      Parameters:
      path - graph path
      Returns:
      an array containing the index of the vertices of the tour