Package org.jgrapht.alg.tour

Class 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 Object
implements HamiltonianCycleAlgorithm<V,​E>, 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 k 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).

    Author:
    Dimitrios Michail

    • Constructor Detail

      • TwoOptHeuristicTSP

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

      • TwoOptHeuristicTSP

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

      • TwoOptHeuristicTSP

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

      • TwoOptHeuristicTSP

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

      • TwoOptHeuristicTSP

        public TwoOptHeuristicTSP​(int k,
                          Random rng,
                          double minCostImprovement)
        Constructor
        Parameters:
        k - 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 k,
                          HamiltonianCycleAlgorithm<V,​E> initializer)
        Constructor
        Parameters:
        k - how many initial tours to check
        initializer - Algorithm to generate initial tour

      • TwoOptHeuristicTSP

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