# TSP with multiple agents

Data: data_mtsp for 3, 4 and 5 agents

## Problem description

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.

## Possible representations

• [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,

## Uniform evaluation function

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.