Kiwi.com vyhlašuje 2. ročník Travelling Salesman Challenge

Česká společnost Kiwi.com, která se zaměřuje na vyhledávání a prodej letenek do celého světa, dnes spustila druhý ročník soutěže Travelling Salesman Challenge, jejíž vítěz vyhraje cestu kolem světa. Cílem je vyřešit problém obchodního cestujícího a navrhnout fungující algoritmus, který bude nabízet nejlevnější letecká spojení mezi vybranými oblastmi. Příležitost ukázat své schopnosti mají týmy 2–3 developerů až do 29. října.

Účastníci loňského ročníku Travelling Salesman Challenge měli za úkol najít algoritmus, který bude schopen smysluplně kombinovat jednosměrné lety mezi více městy, a to třeba i v rámci jediného dne. Vítězství si minulý rok odnesl Čech Petr Lavička.

„Mou největší motivací byl NP úplný problém, který není matematicky řešitelný žádnou známou metodou. O vhodném algoritmu, který by se přiblížil co nejblíže k řešení zadaného problému, jsem přemýšlel po večerech. Nakonec jsem zvolil algoritmus nazývaný simulated annealing. Pořád jsem však nebyl spokojený, a tak jsem jej vylepšoval dále o mé vlastní metody. Mé řešení bylo nakonec schopné zhodnotit přibližně 120 milionů různých cest během půl minuty. Algoritmus týmu, který skončil druhý, byl téměř dvakrát tak pomalejší a neobsahoval mnou doplněné optimalizace,“ popisuje svou cestu k vítězství minulého ročníku Petr, který se k němu dopracoval sám. Do svého týmu však zapsal své nic netušící rodiče, kteří svět procestovali společně s ním.

Letošní výzva se zaměří na hledání nejlepšího algoritmu pro cestující, kteří chtějí navštívit jakékoliv město v předem vybrané oblasti. Při řešení úkolu se musí developeři držet i další podmínky – cestující se v jednotlivých destinacích může zdržet jediný den a poté ze stejného letiště cestovat dále.

“Letošní zadání soutěže je přímo navázané na další směřování našeho nového produktu NOMAD. Pořádáním této soutěže chceme dát lidem příležitost vyzkoušet, jaké je podílet se na inovaci cestovního průmyslu. Náš vlastní vývoj však probíhá zcela nezávisle na soutěži a platí, že co soutěžící vymyslí, zůstává jejich,” vysvětluje Jan Plhák, který vede tým zodpovědný za vývoj NOMADa.

Problém obchodního cestujícího, poprvé zdokumentovaný v roce 1930, je jednou z nejobtížnějších otázek v oblasti optimalizace, plánování a logistiky, jež se snaží najít optimální propojení různých bodů na mapě. Kromě těchto oblastí je možné ho využít právě pro cestování, a to pro cestující, kteří potřebují objet několik míst v jakémkoliv pořadí, ale v daném časovém horizontu.

Na letošní Travelling Salesman Challenge se mohou přihlásit dvou až tříčlenné týmy, vyřešit zadaný úkol je třeba do 29. října. Organizátor pozve TOP 10 týmů na slavnostní galavečer 9. listopadu v Praze, kde vyhlásí vítěze.

Hlavní cenou je cesta kolem světa, druhý tým získá cestovní vouchery v hodnotě 1000 eur, a třetí nejlepší tým získá cestovní vouchery v hodnotě 600 eur.

Detailní informace o soutěži Travelling Salesman Challenge jsou na oficiálním webu soutěže.