- java.lang.Object
-
- org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
-
- org.jgrapht.alg.tour.TwoOptHeuristicTSP<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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)
.
-
-
Field Summary
Fields Modifier and Type Field Description private double[][]
dist
private Graph<V,E>
graph
private java.util.Map<V,java.lang.Integer>
index
private HamiltonianCycleAlgorithm<V,E>
initializer
private double
minCostImprovement
private int
n
private int
passes
private java.util.List<V>
revIndex
-
Constructor Summary
Constructors Constructor Description TwoOptHeuristicTSP()
Constructor.TwoOptHeuristicTSP(int passes)
ConstructorTwoOptHeuristicTSP(int passes, long seed)
ConstructorTwoOptHeuristicTSP(int passes, java.util.Random rng)
ConstructorTwoOptHeuristicTSP(int passes, java.util.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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private int[]
createInitialTour()
Create an initial tourGraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a 2-approximate tour.private int[]
improve(int[] tour)
Improve the tour using the 2-opt heuristic.GraphPath<V,E>
improveTour(GraphPath<V,E> tour)
Try to improve a tour by running the 2-opt heuristic.private void
init(Graph<V,E> graph)
Initialize graph and mapping to integer vertices.private int[]
pathToTour(GraphPath<V,E> path)
Transform from a path representation to an array representation.private GraphPath<V,E>
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 Detail
-
passes
private final int passes
-
initializer
private final HamiltonianCycleAlgorithm<V,E> initializer
-
minCostImprovement
private final double minCostImprovement
-
n
private int n
-
dist
private double[][] dist
-
index
private java.util.Map<V,java.lang.Integer> index
-
revIndex
private java.util.List<V> revIndex
-
-
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 checkseed
- seed for the random number generator
-
TwoOptHeuristicTSP
public TwoOptHeuristicTSP(int passes, java.util.Random rng)
Constructor- Parameters:
passes
- how many initial random tours to checkrng
- random number generator
-
TwoOptHeuristicTSP
public TwoOptHeuristicTSP(int passes, java.util.Random rng, double minCostImprovement)
Constructor- Parameters:
passes
- how many initial random tours to checkrng
- random number generatorminCostImprovement
- 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 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 Detail
-
getTour
public GraphPath<V,E> getTour(Graph<V,E> graph)
Computes a 2-approximate tour.- Specified by:
getTour
in interfaceHamiltonianCycleAlgorithm<V,E>
- 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 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 interfaceHamiltonianCycleImprovementAlgorithm<V,E>
- Parameters:
tour
- a tour- Returns:
- a possibly improved tour
-
init
private void init(Graph<V,E> graph)
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
private GraphPath<V,E> tourToPath(int[] tour)
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
-
-