Studenti informatiky z Fakulty elektrotechnické ČVUT bodují na světové úrovni V prestižní soutěži Kiwi.com řešili nejefektivněji tzv. problém obchodního cestujícího a vyhráli 1. místo

29. 11. 2018 – 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. 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ů (ř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:

 

  • místo ČR
  • místo Portugalsko
  • 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í

*nondeterministic polynomial time

O FEL ČVUT:

Samostatná Fakulta elektrotechnická ČVUT vznikla v roce 1950. V dnešní době se skládá ze 17 kateder umístěných ve dvou budovách: v rámci Kampusu Dejvice v Technické ulici a v naší historické budově na Karlově náměstí. Fakulta elektrotechnická poskytuje prvotřídní vzdělání v oblasti elektrotechniky a informatiky, elektroniky, telekomunikací, automatického řízení, kybernetiky a počítačového inženýrství. Fakulta se dlouhodobě řadí mezi prvních pět výzkumných institucí v České republice. Produkuje přibližně 30 % výzkumných výsledků celého ČVUT a má navázanou rozsáhlou vědeckou spolupráci se špičkovými světovými univerzitami i výzkumnými ústavy. Od roku 1950 Fakulta elektrotechnická vydala cca 30 000 diplomů, které byly vždy vysoce hodnoceny jako doklad prvotřídního vzdělání. Více informací najdete na www.fel.cvut.cz

O ČVUT:

České vysoké učení technické v Praze patří k největším a nejstarším technickým vysokým školám v Evropě. V současné době má ČVUT osm fakult (stavební, strojní, elektrotechnická, jaderná a fyzikálně inženýrská, architektury, dopravní, biomedicínského inženýrství, informačních technologií). Studuje na něm přes 18 000 studentů. Pro akademický rok 2018/19 nabízí ČVUT svým studentům 169 studijních programů a v rámci nich 480 studijních oborů. ČVUT vychovává odborníky v oblasti techniky, vědce a manažery se znalostí cizích jazyků, kteří jsou dynamičtí, flexibilní a dokáží se rychle přizpůsobovat požadavkům trhu. V roce 2018 se ČVUT umístilo v hodnocení QS World University Rankings, které zahrnuje více než 4500 světových univerzit, v oblasti „Civil and Structural Engineering” na 101. – 150. místě, v oblasti „Mechanical, Aeronautical and Manuf. Engineering“ na 151. – 200. místě, v oblasti „Computer Science and Information Systems” na 201. – 250. místě, v oblasti „Electrical and Electronic Engineering“ na 201. – 250. místě. V oblasti „Mathematics“ na 251. – 300. místě a „Physics and Astronomy“ na 151. – 200., v oblasti „Natural Sciences“ na 220. místě, v oblasti „Architecture/Built Environment“ na 151. – 200. místě, v oblasti „Engineering and Technology“ na 220. místě. V celkovém hodnocení university je ČVUT na 491. – 500. příčce v meziročním srovnání a je tak stále nejlepší tuzemskou technickou univerzitou. Více informací najdete na www.cvut.cz

O společnosti Kiwi.com

Společnost Kiwi.com byla založena jako start-up čtyřiadvacetiletým Oliverem Dlouhým a Jozefem Képesim v Brně v roce 2012. Kiwi.com díky svému algoritmu, tzv. virtuálnímu propojování (virtual interlining), který se zaměřuje na kombinace letů nespolupracujících aerolinek, vyhledává a sestavuje unikátní letecká spojení a cenové nabídky letenek. Společnost také nabízí záruku navazujících spojení, tzv. Kiwi.com Guarantee. První letenky společnost prodala v březnu 2013 v desítkách kusů, zatímco dnes její měsíční obrat dosahuje více než 1,5 miliardy Kč při průměrných 8 000 objednávkách denně. Kiwi.com dnes má globálně více než 1 700 zaměstnanců. Společnost se stala nejrychleji rostoucí technologickou firmou ve střední Evropě za rok 2017, když zvítězila v Deloitte Technology Fast 50. V hodnocení Deloitte Technology Fast 500 EMEA Kiwi.com obsadila v konkurenci 500 firem 7. místo. Za poslední 4 roky její tržby vzrostly o 7 165 % na více než 8,5 miliardy korun (332 milionů eur) v roce 2016. Do první desítky pro Evropu, Blízký východ a Afriku se přitom žádná česká firma ještě nikdy neprobojovala. Společnost Kiwi.com dnes zpracovává na 50 milionů vyhledávání denně a nabízí více než 225 tisíc aktualizovaných cen za minutu, svým uživatelům zároveň zprostředkovává nejlepší nabídky prostřednictvím notifikací a upozornění na cenu.