Traveling Salesman Problem
The same group on the Doxygen site.
- group Traveling Salesman Problem
Algorithms for the symmetric traveling salesman problem.
This group contains basic heuristic algorithms for the the symmetric traveling salesman problem (TSP). Given an undirected full graph with a cost map on its edges, the problem is to find a shortest possible tour that visits each node exactly once (i.e. the minimum cost Hamiltonian cycle).
These TSP algorithms are intended to be used with a metric cost function, i.e. the edge costs should satisfy the triangle inequality. Otherwise the algorithms could yield worse results.
LEMON provides five well-known heuristics for solving symmetric TSP:
NearestNeighborTsp Neareast neighbor algorithm
GreedyTsp Greedy algorithm
InsertionTsp Insertion heuristic (with four selection methods)
ChristofidesTsp Christofides algorithm
Opt2Tsp 2-opt algorithm
NearestNeighborTsp, GreedyTsp, and InsertionTsp are the fastest solution methods. Furthermore, InsertionTsp is usually quite effective.
ChristofidesTsp is somewhat slower, but it has the best guaranteed approximation factor: 3/2.
Opt2Tsp usually provides the best results in practice, but it is the slowest method. It can also be used to improve given tours, for example, the results of other algorithms.

Classes
Class |
Description |
|---|---|
Christofides algorithm for symmetric TSP. |
|
Greedy algorithm for symmetric TSP. |
|
Insertion algorithm for symmetric TSP. |
|
Nearest neighbor algorithm for symmetric TSP. |
|
2-opt algorithm for symmetric TSP. |