Kdo nejlépe vyřešil problém obchodního cestujícího?

29. November 2018 23:19 0 komentářů

Studenti informatiky z Fakulty elektrotechnické ČVUT bodují na světové úrovni.

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 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.


Komentáře

RSS 

Komentujeme

Počítačové hry v hlavě – a to dokonce multiplayer

Pavel Houser , 03. August 2019 06:30

Tetris v podání vědců z University of Washington připomíná málem telepatii – jeden z hráčů vidí pada...

Více



Kalendář

25. 08.

29. 08.
VMworld US 2019
05. 09.

06. 09.
Technical Computing Camp 2019
06. 09.

11. 09.
IFA 2019
RSS 

Zprávičky

Průzkum: Chytrým mobilem platí již téměř třetina Čechů

ČTK , 20. August 2019 14:40

Podíl Čechů platících svým chytrým mobilem je 31 %, zatímco v roce 2016 to bylo pouze 13 %. ...

Více 0 komentářů

Startup vyvinul pro umělou inteligenci největší čip na světě

ČTK , 20. August 2019 10:24

Nově vyvinutý čip obsahuje 1,2 bilionu tranzistorů....

Více 0 komentářů

Nordic Telecom si stěžuje u ÚOHS

Pavel Houser , 20. August 2019 08:00

Vnitro u zakázky pro záchranné sbory argumentuje utajením a chce uplatnit výjimku ze zákona o zadává...

Více 0 komentářů

Starší zprávičky

Huawei bude moci nakupovat americké součástky o 90 dní déle

ČTK , 19. August 2019 15:33

Ministerstvo obchodu USA také oznámilo, že zařadí na černou listinu zhruba 50 přidružených firem Hua...

Více 0 komentářů

Bezpečnostní rady státu jedná o kybernetickém útoku na ministerstvo zahraničí

ČTK , 19. August 2019 11:36

Ministerstvo zahraničí čelilo kybernetickému útoku v červnu....

Více 0 komentářů

V Irsku končí první šetření velké firmy okolo pravidel GDPR

ČTK , 19. August 2019 08:00

Celý proces zřejmě bude trvat měsíce, protože firma musí dostat čas na to, aby se mohla k vyšetřován...

Více 0 komentářů

Většina uživatelů sociálních sítí v USA by za ně byla ochotna platit

ČTK , 18. August 2019 08:00

Autoři dále spočítali, kolik by platformy vydělaly, pokud by vycházely pouze s příjmy od předplatite...

Více 0 komentářů