Studenti doktorského studia Petr Váňa, Robert Pěnička a výzkumník Vojtěch Vonásek z katedry počítačů FEL ČVUT se v říjnu zúčastnili developerské soutěže pořádané technologickou společností Kiwi.com, během níž měli za úkol řešit tzv. problém obchodního cestujícího. Zvítězili v konkurenci více než 500 týmů z celého světa.
Jejich úkolem bylo navrhnout algoritmus, který bude nabízet nejlevnější letecká spojení mezi vybranými oblastmi. Trojice uspěla v mezinárodní konkurenci více než 500 týmů 50 národností a 8697 odevzdaných řešení.
Problém obchodního cestujícího (travelling salesman) je považován za jeden z nejnáročnějších úkolů. Obchodní cestující musí navštívit všechna zadaná města, u nichž není předem určené jejich pořadí. Klade si tedy základní otázku, jaký je nejefektivnější způsob, jak všechna tato města navštívit. To, co dělá tento problém náročným, je ohromné množství možných kombinací - například už pro 10 různých měst existuje přes 180 000 kombinací. Aby obchodní cestující našel tu pravou kombinaci, musel by je vyzkoušet všechny, proto jsou k řešení využívány moderní technologie a algoritmy.
Letos s podobným úkolem přišla technologická společnost zaměřená na vyhledávání a prodej letenek Kiwi.com. Vyhlásila programátorskou soutěž, během které měli účastníci najít ideální algoritmus pro cestujícího, který chce navštívit n oblastí a v každé oblasti právě jedno město. V jednotlivých destinacích se navíc může zdržet jediný den, poté ze stejného letiště cestovat dále.
„Večer před začátkem soutěže jsem si o ní přečetl článek na webu a okamžitě jsem si řekl, že máme šanci, protože já i Petr řešíme v rámci doktorského studia na Fakultě elektrotechnické podobné problémy. Hned další den ráno jsem mu napsal a ještě spolu s Vojtou jsme vytvořili tým,“ říká Robert Pěnička, jeden z členů týmu.
Vítězné řešení se podařilo najít právě trojici výzkumníků z ČVUT, a to prostřednictvím Breadth-first search (BFS) algoritmu, který se běžně používá pro prohledávání kombinatorických úloh. Důležitým aspektem vítězného řešení byla mimo jiné také vhodná optimalizace, která umožnila vyzkoušet více než sto milionů letů během časového limitu omezeného na 15 sekund.
„Stejně jako další soutěže a akce, které pořádáme, i Travelling Salesman Challenge je pro nás způsob, jak se spojit s nadějnými talenty a vzájemně navázat dobré vztahy. Díky tomu se dozvídáme, jak a na čem třeba právě studenti na ČVUT pracují a poznáváme zajímavé projekty a výzkumy. V Kiwi.com máme zase kvanta zajímavých dat, která mohou být pro studenty a jejich výzkum zajímavá i do budoucna," říká Jan Plhák, který v Kiwi.com vede tým zodpovědný za vývoj NOMADa a problém obchodního cestujícího tak převádí do praxe.
Zdroj: ČVUT
- Autor článku: ne
- Zdroj: ČVUT
