## 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 HamiltonianCycleAlgorithmBase<V,​E>
implements 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 passes 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 Summary

Constructors
Constructor Description
TwoOptHeuristicTSP()
Constructor.
TwoOptHeuristicTSP​(int passes)
Constructor
TwoOptHeuristicTSP​(int passes, long seed)
Constructor
TwoOptHeuristicTSP​(int passes, java.util.Random rng)
Constructor
TwoOptHeuristicTSP​(int passes, java.util.Random rng, double minCostImprovement)
Constructor
TwoOptHeuristicTSP​(int passes, HamiltonianCycleAlgorithm<V,​E> initializer)
Constructor
TwoOptHeuristicTSP​(int passes, HamiltonianCycleAlgorithm<V,​E> initializer, double minCostImprovement)
Constructor
TwoOptHeuristicTSP​(HamiltonianCycleAlgorithm<V,​E> initializer)
Constructor
• ### Method Summary

All Methods
Modifier and Type Method Description
GraphPath<V,​E> getTour​(Graph<V,​E> graph)
Computes a 2-approximate tour.
GraphPath<V,​E> improveTour​(GraphPath<V,​E> tour)
Try to improve a tour by running the 2-opt 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

• #### TwoOptHeuristicTSP

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

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

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

public TwoOptHeuristicTSP​(int passes,
java.util.Random rng)
Constructor
Parameters:
passes - how many initial random tours to check
rng - random number generator
• #### TwoOptHeuristicTSP

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

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

• #### getTour

public GraphPath<V,​E> getTour​(Graph<V,​E> graph)
Computes a 2-approximate tour.
Specified by:
getTour in interface HamiltonianCycleAlgorithm<V,​E>
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
• #### improveTour

public GraphPath<V,​E> improveTour​(GraphPath<V,​E> tour)
Try to improve a tour by running the 2-opt heuristic.
Specified by:
improveTour in interface HamiltonianCycleImprovementAlgorithm<V,​E>
Parameters:
tour - a tour
Returns:
a possibly improved tour