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

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.

courses/a0m33eoa/semestral_tasks/mtsp.txt · Last modified: 2022/11/14 10:33 by xposik