Search
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.
Kvalita řešení je určena jako délka nejdelší cesty z M cest.