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 pivot node,
all nodes, except the depot, are visited exactly ones by some of the agents,
no route can have zero length.

Possible representations

[permutation of nodes][break-points]
- example: depot=1, [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]
…

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.

Table of Contents

TSP with multiple agents

Problem description

Possible representations

Uniform evaluation function