Studenti informatiky z Fakulty elektrotechnické ČVUT vyhráli v prestižní soutěži Kiwi.com

Problém obchodního cestujícího (travelling salesman) je považován za jeden z nejnáročnějších úkolů (řadí se do skupiny problémů označovaných jako NP-hard* problem). 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. Takovou úlohou může být například i desková hra šachy, ve které by algoritmus procházel možné budoucí kombinace tahů. „Pro úlohu obchodního cestujícího by ovšem klasický BFS algoritmus nezvládl vyzkoušet všechny možné kombinace letů, protože jejich počet vzrůstá exponenciálně s počtem navštívených měst (tzv. kombinatorická exploze),” vysvětluje Petr Váňa, další ze členů týmu. “Bylo tedy nezbytně nutné strom obsahující možné kombinace letů vhodně prořezávat.” To by ovšem mohlo odstranit kvalitní.

řešení, a proto autoři do algoritmu přidali takzvané heuristiky, které na základě částečného řešení (několik prvních letů) odhadovaly výslednou cenu a umožňovaly odstraňovat neperspektivní kombinace letů. Důležitým aspektem vítězného řešení byla 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.

Vítězství tří výzkumníků znamená úspěch i pro FEL a centrum umělé inteligence (Artificial Intelligence Center), kde všichni působí.

„Pro AIC je úspěch v soutěži velmi cennou trofejí. Je zajímavé vidět, že naše zkušenost a technické znalosti v oblasti umělé inteligence představují kompetitivní výhodu při řešení netriválních průmyslových výzev,” říká prof. Michal Pěchouček z centra umělé inteligence AIC na FEL ČVUT. Dle jeho slov jsou v AIC oblíbené zejména průmyslové a aplikační problémy, které výzkumníkům umožňují se efektivně pohybovat na hraně technologického pokroku.

„Kiwi.com tu navíc všichni fandíme, startup, který uspěje v mezinárodní konkurenci, je pro nás obrovskou motivací. I v rámci AIC se rekrutují některé úspěšné projekty,” dodává s tím, že největší úspěchy má centrum v oblastech plánování, robotiky, inteligentních dopravních systémů, cyber security nebo teorie her.

Fakta k soutěži Travelling Salesman Challenge 2018:

1. místo ČR
2. místo Portugalsko
3. místo ČR
   

- 500+ týmů
- 50 unikátních národností (včetně USA, Indie, Ruska, UK, Slovenska, Indonésie, Rumunska, Španělska, Srbska atd.)
- 8697 odevzdaných řešení celkem
- 100 řešení s nejlepšími výsledky, která se dostala do závěrečné fáze hodnocení