Class NearestInsertionHeuristicTSP<V,E>

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

public class NearestInsertionHeuristicTSP<V,E> extends HamiltonianCycleAlgorithmBase<V,E>
The nearest 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 tour of a subset of all cities, and then inserting the rest by some heuristic. The initial sub-tour is often a triangle or the convex hull. One can also start with a single edge as sub-tour. This implementation uses the shortest edge by default as the initial sub-tour.

The implementation of this class is based on:
Nilsson, Christian. "Heuristics for the traveling salesman problem." Linkoping University 38 (2003)

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

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

This algorithm requires that the graph is complete.

  • Field Details

  • Constructor Details

    • NearestInsertionHeuristicTSP

      public NearestInsertionHeuristicTSP()
      Constructor. By default a sub-tour is chosen based on the shortest edge
    • NearestInsertionHeuristicTSP

      public NearestInsertionHeuristicTSP(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 shortest edge
  • Method Details

    • getTour

      public GraphPath<V,E> getTour(Graph<V,E> graph)
      Computes a tour using the nearest insertion heuristic.
      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
      IllegalArgumentException - If the specified sub-tour is for a different Graph instance
      IllegalArgumentException - If the graph does not contain specified sub-tour vertices
      IllegalArgumentException - If the graph does not contain specified sub-tour edges
    • subtour

      private List<V> subtour(Graph<V,E> graph)
      Get or create a sub-tour to start augmenting
      Parameters:
      graph - The graph
      Returns:
      Vertices of an initial sub-tour
      Throws:
      IllegalArgumentException - If the specified sub-tour is for a different Graph instance
      IllegalArgumentException - If the graph does not contain specified sub-tour vertices
      IllegalArgumentException - If the graph does not contain specified sub-tour edges
    • getClosest

      private Map<V,NearestInsertionHeuristicTSP.Closest<V>> getClosest(List<V> tourVertices, Set<V> unvisited, Graph<V,E> graph)
      Initialise the Map storing closest unvisited vertex for each tour vertex
      Parameters:
      tourVertices - Current tour vertices
      unvisited - Set of unvisited vertices
      graph - The graph
      Returns:
      Map storing closest unvisited vertex for each tour vertex
    • getClosest

      private NearestInsertionHeuristicTSP.Closest<V> getClosest(V tourVertex, Set<V> unvisited, Graph<V,E> graph)
      Determines closest unvisited vertex to a vertex in the current tour
      Parameters:
      tourVertex - Vertex in the current tour
      unvisited - Set of vertices not in the current tour
      graph - The graph
      Returns:
      Closest unvisited vertex
    • updateClosest

      private void updateClosest(Map<V,NearestInsertionHeuristicTSP.Closest<V>> currentClosest, NearestInsertionHeuristicTSP.Closest<V> chosen, Set<V> unvisited, Graph<V,E> graph)
      Update the Map storing closest unvisited vertex for each tour vertex
      Parameters:
      currentClosest - Map storing closest unvisited vertex for each tour vertex
      chosen - Latest vertex added to tour
      unvisited - Set of unvisited vertices
      graph - The graph
    • chooseClosest

      Chooses the closest unvisited vertex to the sub-tour
      Parameters:
      closestVertices - Map storing closest unvisited vertex for each tour vertex
      Returns:
      First result of sorting values
    • augment

      private List<V> augment(List<V> subtour, Graph<V,E> graph)
      Augment an existing tour to give a complete tour
      Parameters:
      subtour - The vertices of the existing tour
      graph - The graph
      Returns:
      List of vertices representing the complete tour
    • augment

      private List<V> augment(List<V> subtour, Map<V,NearestInsertionHeuristicTSP.Closest<V>> closestVertices, Set<V> unvisited, Graph<V,E> graph)
      Augment an existing tour to give a complete tour
      Parameters:
      subtour - The vertices of the existing tour
      closestVertices - Map of data for closest unvisited vertices
      unvisited - Set of unvisited vertices
      graph - The graph
      Returns:
      List of vertices representing the complete tour