Traveling Salesman Problem

Detailed Description

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	ChristofidesTsp< CM >
	Christofides algorithm for symmetric TSP. More...
class	GreedyTsp< CM >
	Greedy algorithm for symmetric TSP. More...
class	InsertionTsp< CM >
	Insertion algorithm for symmetric TSP. More...
class	NearestNeighborTsp< CM >
	Nearest neighbor algorithm for symmetric TSP. More...
class	Opt2Tsp< CM >
	2-opt algorithm for symmetric TSP. More...

Files
file	christofides_tsp.h
	Christofides algorithm for symmetric TSP.
file	greedy_tsp.h
	Greedy algorithm for symmetric TSP.
file	insertion_tsp.h
	Insertion algorithm for symmetric TSP.
file	nearest_neighbor_tsp.h
	Nearest neighbor algorithm for symmetric TSP.
file	opt2_tsp.h
	2-opt algorithm for symmetric TSP.