Data: data_mtsp for 3, 4 and 5 agents

This is a modification of the classical Traveling Salesman Problem.

Given is an undirected graph with $N$ nodes (cities), one of them serving as a **depot**. The depot is a node where all routes start and end.
Further, there are $M$ agents (traveling salespersons). The goal is to find a set of $M$ routes such that the length of the longest one is minimal subject to

- all routes start and end at the depot node,
- all nodes, except the depot, are visited exactly once by one of the agents,
- no route can have zero length.

- [permutation of nodes][break-points]
- example: if depot=1, then a solution [2-4-3|5-8-6-7|10-9][3,7] implies routes r1=[1,2,4,3,1], r2=[1,5,8,6,7,1], r3=[1,10,9,1]

- permutation of nodes with depot ID sticked in several times,
- …

Solution quality is determined by the length of the longest tour, that is to be minimized.

If solved as a pure black-box optimization problem, one could use information about cities locations or the 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/mtsp.txt · Last modified: 2022/11/14 10:33 by xposik