- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,
,E> HamiltonianCycleImprovementAlgorithm<V,
E>
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)
.
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionConstructor.TwoOptHeuristicTSP
(int passes) ConstructorTwoOptHeuristicTSP
(int passes, long seed) ConstructorTwoOptHeuristicTSP
(int passes, Random rng) ConstructorTwoOptHeuristicTSP
(int passes, Random rng, double minCostImprovement) ConstructorTwoOptHeuristicTSP
(int passes, HamiltonianCycleAlgorithm<V, E> initializer) ConstructorTwoOptHeuristicTSP
(int passes, HamiltonianCycleAlgorithm<V, E> initializer, double minCostImprovement) ConstructorTwoOptHeuristicTSP
(HamiltonianCycleAlgorithm<V, E> initializer) Constructor -
Method Summary
Modifier and TypeMethodDescriptionprivate int[]
Create an initial tourComputes a 2-approximate tour.private int[]
improve
(int[] tour) Improve the tour using the 2-opt heuristic.improveTour
(GraphPath<V, E> tour) Try to improve a tour by running the 2-opt heuristic.private void
Initialize graph and mapping to integer vertices.private int[]
pathToTour
(GraphPath<V, E> path) Transform from a path representation to an array representation.tourToPath
(int[] tour) Transform from an array representation to a graph path.Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
-
Field Details
-
passes
private final int passes -
initializer
-
minCostImprovement
private final double minCostImprovement -
graph
-
n
private int n -
dist
private double[][] dist -
index
-
revIndex
-
-
Constructor Details
-
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 checkseed
- seed for the random number generator
-
TwoOptHeuristicTSP
Constructor- Parameters:
passes
- how many initial random tours to checkrng
- random number generator
-
TwoOptHeuristicTSP
Constructor- Parameters:
passes
- how many initial random tours to checkrng
- random number generatorminCostImprovement
- Minimum cost improvement per iteration
-
TwoOptHeuristicTSP
Constructor- Parameters:
initializer
- Algorithm to generate initial tour
-
TwoOptHeuristicTSP
Constructor- Parameters:
passes
- how many initial tours to checkinitializer
- Algorithm to generate initial tour
-
TwoOptHeuristicTSP
public TwoOptHeuristicTSP(int passes, HamiltonianCycleAlgorithm<V, E> initializer, double minCostImprovement) Constructor- Parameters:
passes
- how many initial tours to checkinitializer
- Algorithm to generate initial toursminCostImprovement
- Minimum cost improvement per iteration
-
-
Method Details
-
getTour
Computes a 2-approximate tour.- Specified by:
getTour
in interfaceHamiltonianCycleAlgorithm<V,
E> - Parameters:
graph
- the input graph- Returns:
- a tour
- Throws:
IllegalArgumentException
- if the graph is not undirectedIllegalArgumentException
- if the graph is not completeIllegalArgumentException
- if the graph contains no vertices
-
improveTour
Try to improve a tour by running the 2-opt heuristic.- Specified by:
improveTour
in interfaceHamiltonianCycleImprovementAlgorithm<V,
E> - Parameters:
tour
- a tour- Returns:
- a possibly improved tour
-
init
Initialize graph and mapping to integer vertices.- Parameters:
graph
- the input graph
-
createInitialTour
private int[] createInitialTour()Create an initial tour- Returns:
- a complete tour
-
improve
private int[] improve(int[] tour) Improve the tour using the 2-opt heuristic. 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 returned array instance might or might not be the input array.
- Parameters:
tour
- the input tour- Returns:
- a possibly improved tour
-
tourToPath
Transform from an array representation to a graph path.- Parameters:
tour
- an array containing the index of the vertices of the tour- Returns:
- a graph path
-
pathToTour
Transform from a path representation to an array representation.- Parameters:
path
- graph path- Returns:
- an array containing the index of the vertices of the tour
-