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

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.

Popis problému

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.

Možné reprezentace

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

Jednotná ohodnocovací funkce

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

courses/a0m33eoa/semestralni_ulohy/mtsp/start.txt · Last modified: 2018/06/25 12:56 (external edit)