Česká spoločnosť Kiwi.com, ktorá sa zaoberá vyhľadávaním a predajom leteniek do celého sveta, spustila druhý ročník súťaže Travelling Salesman Challenge, ktorej víťaz vyhrá cestu okolo sveta. Cieľom je vyriešiť problém obchodného cestujúceho a navrhnúť fungujúci algoritmus, ktorý bude ponúkať najlacnejšie letecké spojenia medzi vybranými oblasťami. Príležitosť ukázať svoje schopnosti majú tímy dvoch či troch vývojárov až do 29. októbra.
Účastníci minuloročného Travelling Salesman Challenge mali napísať taký algoritmus, ktorý bude schopný zmysluplne kombinovať jednosmerné letenky aj medzi viacerými mestami, a to aj v rámci jediného dňa. Minulý rok vytvoril najlepší algoritmus Čech Petr Lavička.
„Mojou najväčšou motiváciou bol NP úplný problém, ktorý nie je matematicky riešiteľný žiadnou známou metódou. O vhodnom algoritme, ktorý by sa najviac priblížil k riešeniu zadania, som rozmýšľal po večeroch. Nakoniec som si vybral algoritmus nazvaný simulated annealing. Stále som s ním však nebol spokojný, a tak som ho aj ďalej vylepšoval o vlastné metódy. Moje riešenie bolo nakoniec schopné zhodnotiť zhruba 120 miliónov rôznych trás behom 30 sekúnd. Algoritmus tímu, ktorý skončil druhý, bol takmer dvakrát pomalší a neobsahoval mnou doplnené optimalizácie,“ popísal svoju cestu k úspechu v prvom ročníku súťaže Travelling Salesman Challenge programátor Petr. Navyše do svojho tímu zapísal svojich nič netušiacich rodičov, s ktorými sa vybral na výhernú cestu okolo sveta.
Tohtoročná výzva je zameraná na hľadanie najlepšieho algoritmu pre cestujúcich, ktorí chcú navštíviť akékoľvek mesto vo vopred vybranej oblasti. Pri riešení zadanej úlohy sa musia developeri držať aj ďalšej podmienky – a to, že cestujúci sa v jednotlivých destináciách môže zdržať iba jediný deň a musí z toho istého letiska cestovať do ďalšej destinácie.
„Tohtoročná súťažná úloha je priamo naviazaná na ďalšie smerovanie nášho nového produktu NOMAD. Usporiadaním tejto súťaže chceme dať ľudom možnosť vyskúšať si, aké to je podieľať sa na inovácii cestovného priemyslu. Náš vlastný vývoj pritom nie je závislý na tejto súťaži a takisto platí, že čo súťažiaci vymyslia, zostáva ich,“ vysvetľuje Jan Plhák, ktorý vedie tím zodpovedný za vývoj služby NOMAD.
Problém obchodného cestujúceho, spomínaný už od 19. storočia, je jednou z najznámejších optimalizačných úloh, ktorá sa snaží nájsť optimálne prepojenie rôznych bodov na mape. Riešenie tohto cestovateľského problému je aplikovateľné v oblasti plánovania, optimalizácie a logistiky, ale takisto aj v cestovaní, pre ľudí, ktorí počas určitého časového horizontu potrebujú navštíviť niekoľko miest v akomkoľvek poradí.
Na tohtoročný Travelling Salesman Challenge sa môžu prihlásiť dvoj až trojčlenné tímy, ktoré majú vyriešiť zadanú úlohu do 29. októbra. Organizátor pozve TOP 10 tímov na slávnostný galavečer, ktorý sa bude konať 9. novembra v Prahe, kde vyhlási víťaza súťaže.
Hlavnou cenou je cesta okolo sveta, druhý najlepší tím získa cestovné vouchery v hodnote 1000 eur a tretí tím získa cestovné vouchery v hodnote 600 eur.
Podrobné informácie o súťaži Travelling Salesman Challenge sú k dispozícii na oficiálnom webe.