- java.lang.Object
-
- org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
-
- org.jgrapht.alg.tour.NearestInsertionHeuristicTSP<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
NearestInsertionHeuristicTSP.Closest<V>
Class holding data for the closest unvisited vertex to a particular vertex in the tour.
-
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 whengetTour(org.jgrapht.Graph)
is called
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.List<V>
augment(java.util.List<V> subtour, java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> closestVertices, java.util.Set<V> unvisited, Graph<V,E> graph)
Augment an existing tour to give a complete tourprivate java.util.List<V>
augment(java.util.List<V> subtour, Graph<V,E> graph)
Augment an existing tour to give a complete tourprivate NearestInsertionHeuristicTSP.Closest<V>
chooseClosest(java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> closestVertices)
Chooses the closest unvisited vertex to the sub-tourprivate java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>>
getClosest(java.util.List<V> tourVertices, java.util.Set<V> unvisited, Graph<V,E> graph)
Initialise the Map storing closest unvisited vertex for each tour vertexprivate NearestInsertionHeuristicTSP.Closest<V>
getClosest(V tourVertex, java.util.Set<V> unvisited, Graph<V,E> graph)
Determines closest unvisited vertex to a vertex in the current tourGraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a tour using the nearest insertion heuristic.private java.util.List<V>
subtour(Graph<V,E> graph)
Get or create a sub-tour to start augmentingprivate void
updateClosest(java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> currentClosest, NearestInsertionHeuristicTSP.Closest<V> chosen, java.util.Set<V> unvisited, Graph<V,E> graph)
Update the Map storing closest unvisited vertex for each tour vertex-
Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
-
-
-
-
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 whengetTour(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 undirectedjava.lang.IllegalArgumentException
- If the graph is not completejava.lang.IllegalArgumentException
- If the graph contains no verticesjava.lang.IllegalArgumentException
- If the specified sub-tour is for a different Graph instancejava.lang.IllegalArgumentException
- If the graph does not contain specified sub-tour verticesjava.lang.IllegalArgumentException
- If the graph does not contain specified sub-tour edges
-
subtour
private java.util.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:
java.lang.IllegalArgumentException
- If the specified sub-tour is for a different Graph instancejava.lang.IllegalArgumentException
- If the graph does not contain specified sub-tour verticesjava.lang.IllegalArgumentException
- If the graph does not contain specified sub-tour edges
-
getClosest
private java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> getClosest(java.util.List<V> tourVertices, java.util.Set<V> unvisited, Graph<V,E> graph)
Initialise the Map storing closest unvisited vertex for each tour vertex- Parameters:
tourVertices
- Current tour verticesunvisited
- Set of unvisited verticesgraph
- The graph- Returns:
- Map storing closest unvisited vertex for each tour vertex
-
getClosest
private NearestInsertionHeuristicTSP.Closest<V> getClosest(V tourVertex, java.util.Set<V> unvisited, Graph<V,E> graph)
Determines closest unvisited vertex to a vertex in the current tour- Parameters:
tourVertex
- Vertex in the current tourunvisited
- Set of vertices not in the current tourgraph
- The graph- Returns:
- Closest unvisited vertex
-
updateClosest
private void updateClosest(java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> currentClosest, NearestInsertionHeuristicTSP.Closest<V> chosen, java.util.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 vertexchosen
- Latest vertex added to tourunvisited
- Set of unvisited verticesgraph
- The graph
-
chooseClosest
private NearestInsertionHeuristicTSP.Closest<V> chooseClosest(java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> closestVertices)
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 java.util.List<V> augment(java.util.List<V> subtour, Graph<V,E> graph)
Augment an existing tour to give a complete tour- Parameters:
subtour
- The vertices of the existing tourgraph
- The graph- Returns:
- List of vertices representing the complete tour
-
augment
private java.util.List<V> augment(java.util.List<V> subtour, java.util.Map<V,NearestInsertionHeuristicTSP.Closest<V>> closestVertices, java.util.Set<V> unvisited, Graph<V,E> graph)
Augment an existing tour to give a complete tour- Parameters:
subtour
- The vertices of the existing tourclosestVertices
- Map of data for closest unvisited verticesunvisited
- Set of unvisited verticesgraph
- The graph- Returns:
- List of vertices representing the complete tour
-
-