NearestInsertionHeuristicTSP (JGraphT : a free Java graph library)

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.

Author:

Peter Harman

Constructor Summary

Constructors
Constructor	Description
`NearestInsertionHeuristicTSP()`	Constructor.
`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

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type Method Description

GraphPath<V,E> getTour(Graph<V,E> graph)
Computes a tour using the nearest insertion heuristic.
- Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
  checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
- Methods inherited from class java.lang.Object
  clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - 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 Detail
  - 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:
    
    java.lang.IllegalArgumentException - If the graph is not undirected
    
    java.lang.IllegalArgumentException - If the graph is not complete
    
    java.lang.IllegalArgumentException - If the graph contains no vertices
    
    java.lang.IllegalArgumentException - If the specified sub-tour is for a different Graph instance
    
    java.lang.IllegalArgumentException - If the graph does not contain specified sub-tour vertices
    
    java.lang.IllegalArgumentException - If the graph does not contain specified sub-tour edges