Tour¶
Algorithms¶
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?”.
The following algorithms are available:
-
jgrapht.algorithms.tour.hamiltonian_palmer(graph)[source]¶ Palmer’s algorithm for computing Hamiltonian cycles in graphs that meet Ore’s condition.
Running time \(\mathcal{O}(n^2)\).
- Parameters
graph – the input graph. Must be simple and meet Ore’s condition.
- Returns
a hamiltonian cycle
- Return type
-
jgrapht.algorithms.tour.metric_tsp_christofides(graph)[source]¶ The Christofides 3/2-approximation algorithm for the metric TSP.
For details see:
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Graduate School of Industrial Administration, Carnegie Mellon University (1976).
Running time \(\mathcal{O}(n^3 m)\).
- Parameters
graph – The input graph. Must be undirected, complete and satisfy the triangle inequality.
- Returns
a tour which is a 3/2 approximation
- Return type
-
jgrapht.algorithms.tour.metric_tsp_two_approx(graph)[source]¶ A 2-approximation algorithm for the metric TSP.
This is an implementation of the folklore algorithm which returns a depth-first ordering of the minimum spanning tree. The algorithm is a 2-approximation assuming that the instance satisfies the triangle inequality. The implementation requires the input graph to be undirected and complete. The running time is \(\mathcal{O}(n^2 \log n)\).
- Parameters
graph – the input graph. Must be undirected, complete and satisfy the triangle inequality
- Returns
a tour which is a 2-approximation
- Return type
-
jgrapht.algorithms.tour.tsp_greedy_heuristic(graph)[source]¶ Construct a tour greedily. The algorithm repeatedly selects the shortest edge and adds it to the tour as long as it doesn’t create a cycle with less than \(n\) edges, or increases the degree of any node to more that two.
The runtime complexity is \(\mathcal{O}(n^2 \log n)\).
- Parameters
graph – the input graph. Must be undirected and complete
- Returns
a greedy tour
- Return type
-
jgrapht.algorithms.tour.tsp_held_karp(graph)[source]¶ A dynamic programming algorithm for the TSP.
Finds an optimal, minimum-cost Hamiltonian tour. Running time is \(\mathcal{O}(2^n \times n^2)\) and space \(\mathcal{O}(2^n \times n)\).
- Parameters
graph – the input graph. Must be undirected and complete
- Returns
an optimal tour
- Return type
-
jgrapht.algorithms.tour.tsp_nearest_insertion_heuristic(graph)[source]¶ The nearest insertion heuristic algorithm for the TSP problem.
The runtime complexity is \(\mathcal{O}(n^2)\).
- Parameters
graph – the input graph. Must be undirected and complete
- Returns
a tour
- Return type
-
jgrapht.algorithms.tour.tsp_nearest_neighbor_heuristic(graph, seed=None)[source]¶ The nearest neighbour heuristic algorithm for the TSP problem.
The runtime complexity is \(\mathcal{O}(n^2)\).
- Parameters
graph – the input graph. Must be undirected and complete
seed – seed for the random number generator, use system time if None
- Returns
a tour
- Return type
-
jgrapht.algorithms.tour.tsp_random(graph, seed=None)[source]¶ Compute a random Hamiltonian cycle. This is a simple unoptimized solution to the Travelling Salesman Problem, suitable for a starting point in optimizing using the two-opt heuristic.
- Parameters
graph – the input graph. Must be undirected and complete
seed – seed for the random number generator. If None then the seed is chosen based on the current time
- Returns
A random tour
- Return type
-
jgrapht.algorithms.tour.tsp_two_opt_heuristic(graph, k=1, min_cost_improvement=0.0001, seed=None)[source]¶ The 2-opt heuristic algorithm for the TSP problem.
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 are constructed randomly.
- Parameters
graph – the input graph. Must be undirected and complete
k – how many initial tours to generate
min_cost_improvement – minimum cost improvement per iteration
seed – seed for the random number generator, use system time if None
- Returns
a tour
- Return type
-
jgrapht.algorithms.tour.tsp_two_opt_heuristic_improve(graph_path, min_cost_improvement=0.0001, seed=None)[source]¶ Improve a tour using the 2-opt heuristic for the TSP problem.
This is an implementation of the 2-opt improvement heuristic algorithm. The algorithm takes as input a tour and then iteratively improves the tour 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.
Types¶
Tours are represented with instances of GraphPath.
-
class
jgrapht.types.GraphPath[source] Interface for a graph path.
-
abstract
edges()[source] Edges of the path.
- Return type
collections.abc.Iterable
-
abstract
end_vertex()[source] Ending vertex of the path.
-
abstract
graph()[source] The graph that this graph path refers to.
- Return type
-
abstract
start_vertex()[source] Starting vertex of the path.
-
property
vertices Vertices of the path.
-
abstract
weight()[source] Weight of the path.
- Return type
Double
-
abstract