TSP s několika cestujícími

Data: mtsp_data.zip pro 3, 4 a 5 cestujících

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste pozice měst nebo matici vzdáleností využívat nikde jinde než v ohodnocovací funkci. V této úloze ale je povoleno využívat či analyzovat konkrétní úlohu MTSP i jinde, např. v rekombinačních operátorech.

Na vstupu je úplný neorientovaný graf o N uzlech. Cílem je nalézt takovou množinu cest pro M cestujících, které všechny vychází z počátečního uzlu (depotu) a zase v něm končí, všechny uzly (kromě depotu) jsou navštíveny právě jednou a délka nejdelší cesty je minimální. Žádná z cest nesmí mít nulovou délku.

• [permutace měst][break-pointy], příklad: [2-4-3|5-8-6-7|10-9][3,7]
• …

Kvalita řešení je určena jako délka nejdelší cesty z M cest a tu minimalizujeme.