Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Generalized TSP

Problem description

This is a modification of the classical Traveling Salesman Problem.

Given is a complete undirected graph with $N$ nodes (cities) divided into $M$ groups, each group represents certain region. The goal is to find a shortest possible route that visits each region exactly once and returns to the origin city.

Remark: Each group (region) is represented in the solution by a single node.

Possible representations

  • permutation of $M$ cities

Uniform evaluation function

Quality of solution is determined by the length of the route, that is to be minimized.

If solved as a pure black-box optimization problem, one could use information about cities locations and distance matrix only in the evaluation function. Here, it is allowed to use or analyze such a kind of information elsewhere as well, e.g., in recombination operators.

courses/a0m33eoa/semestral_tasks/generalized_tsp.txt · Last modified: 2021/09/20 12:24 by xposik