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