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

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.

courses/a0m33eoa/en/semestral_tasks/mtsp/start.txt · Last modified: 2020/11/14 12:05 by kubalik