wiki:Documentation/Reference/Traveling Salesman Problem

Version 8 (modified by abeham, 5 years ago) (diff)

--

Traveling Salesman Problem

The traveling salesman problem (TSP) is certainly one of the classical as well as most frequently analyzed representatives of combinatorial optimization problems with a lot of solution methodologies and solution manipulation operators. The problem is that a person has to visit a number of cities starting from and returning to his home city. The goal is to find a tour where every city is visited exactly once and where the travel distances become minimal.

Problem Parameters:

Parameter Description
BestKnownQuality The quality of the best known solution of this TSP instance.
BestKnownSolution The best known solution of this TSP instance.
Coordinates The x- and y-Coordinates of the cities.
DistanceMatrix The matrix which contains the distances between the cities.
Evaluator TSPRoundedEuclideanPathEvaluator: The operator which should be used to evaluate TSP solutions.
Maximization Set to false as the Traveling Salesman Problem is a minimization problem.
SolutionCreator RandomPermutationCreator: The operator which should be used to create new TSP solutions.
UseDistanceMatrix True if a distance matrix should be calculated and used for evaluation, otherwise false.

Is there a sample/tutorial?

Yes, HeuristicLab comes with a set of pre-configured algorithms that solve the "ch130" traveling salesman problem from the TSPLIB:

TPS Operators

TSPRoundedEuclideanPathEvaluator

An operator which evaluates TSP solutions given in path representation using the rounded Euclidean distance metric.

Operator Parameters:

Parameter Description
Coordinates The x- and y-Coordinates of the cities.
DistanceMatrix The matrix which contains the distances between the cities.
TSPTour The TSP solution given in path representation which should be evaluated.
TSPTourLength The evaluated quality of the TSP solution.
UseDistanceMatrix True if a distance matrix should be calculated and used for evaluation, otherwise false.