abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
Traveling Salesman Problem

Algorithms for the symmetric traveling salesman problem. 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.

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

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.