All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Files
Traveling Salesman Problem
Algorithms

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, 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.

tsp.png

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.