Package org.jgrapht.alg.tour

Class TwoOptHeuristicTSP<V,E>

java.lang.Object

org.jgrapht.alg.tour.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 java.lang.Object
implements HamiltonianCycleAlgorithm<V,E>, 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 k 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 k)	Constructor
TwoOptHeuristicTSP(int k, long seed)	Constructor
TwoOptHeuristicTSP(int k, java.util.Random rng)	Constructor
TwoOptHeuristicTSP(int k, java.util.Random rng, double minCostImprovement)	Constructor
TwoOptHeuristicTSP(int k, HamiltonianCycleAlgorithm<V,E> initializer)	Constructor
TwoOptHeuristicTSP(int k, HamiltonianCycleAlgorithm<V,E> initializer, double minCostImprovement)	Constructor
TwoOptHeuristicTSP(HamiltonianCycleAlgorithm<V,E> initializer)	Constructor

Method Summary

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 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 k)

Constructor

Parameters:

k - how many initial random tours to check

TwoOptHeuristicTSP

public TwoOptHeuristicTSP(int k,
                          long seed)

Constructor

Parameters:

k - how many initial random tours to check

seed - seed for the random number generator

TwoOptHeuristicTSP

public TwoOptHeuristicTSP(int k,
                          java.util.Random rng)

Constructor

Parameters:

k - how many initial random tours to check

rng - random number generator

TwoOptHeuristicTSP

public TwoOptHeuristicTSP(int k,
                          java.util.Random rng,
                          double minCostImprovement)

Constructor

Parameters:

k - 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 k,
                          HamiltonianCycleAlgorithm<V,E> initializer)

Constructor

Parameters:

k - how many initial tours to check

initializer - Algorithm to generate initial tour

TwoOptHeuristicTSP

public TwoOptHeuristicTSP(int k,
                          HamiltonianCycleAlgorithm<V,E> initializer,
                          double minCostImprovement)

Constructor

Parameters:

k - 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