Module org.jgrapht.core
Package org.jgrapht.alg.tour

Class FarthestInsertionHeuristicTSP<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>
    public class FarthestInsertionHeuristicTSP<V,​E>
extends HamiltonianCycleAlgorithmBase<V,​E>
    The farthest insertion 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?".

    Insertion heuristics are quite straightforward, and there are many variants to choose from. The basics of insertion heuristics is to start with a partial tour of a subset of all cities, and then iteratively an unvisited vertex (a vertex whichis not in the tour) is chosen given a criterion and inserted in the best position of the partial tour. Per each iteration, the farthest insertion heuristic selects the farthest unvisited vertex from the partial tour. This algorithm provides a guarantee to compute tours no more than 0(log N) times optimum (assuming the triangle inequality). However, regarding practical results, some references refer to this heuristic as one of the best among the category of insertion heuristics. This implementation uses the longest edge by default as the initial sub-tour if one is not provided.

    The description of this algorithm can be consulted on:
    Johnson, D. S., & McGeoch, L. A. (2007). Experimental Analysis of Heuristics for the STSP. In G. Gutin & A. P. Punnen (Eds.), The Traveling Salesman Problem and Its Variations (pp. 369–443). Springer US. https://doi.org/10.1007/0-306-48213-4_9

    This implementation can also be used in order to augment an existing partial tour. See constructor FarthestInsertionHeuristicTSP(GraphPath).

    The runtime complexity of this class is $O(V^2)$.

    This algorithm requires that the graph is complete.

    Author:
    J. Alejandro Cornejo-Acosta

    • Constructor Detail

      • FarthestInsertionHeuristicTSP

        public FarthestInsertionHeuristicTSP()
        Constructor. By default a sub-tour is chosen based on the longest edge

      • FarthestInsertionHeuristicTSP

        public FarthestInsertionHeuristicTSP​(GraphPath<V,​E> subtour)
        Constructor Specifies an existing sub-tour that will be augmented to form a complete tour when getTour(org.jgrapht.Graph) is called
        Parameters:
        subtour - Initial sub-tour, or null to start with longest edge