Table of Contents
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.