Schválené projekty 2016

Rozdělení přidělené dotace z MŠMT na specifický vysokoškolský výzkum po fakultách se zohledněním celoškolských pracovišť na rok 2016

Celková přidělená částka z MŠMT na specifický vysokoškolský výzkum na VŠB-TUO - 55 896 914 Kč

Z toho 2.5% - 1 397 423 Kč - úhrada způsobilých nákladů spojených s organizací SGS

fakulta přidělená částka v Kč
FBI  1 270 231
EKF  4 459 400
FAST  2 765 016
FS  9 344 371
FEI 13 781 413
HGF  5 130 549
FMMI  7 000 000
VC 10 748 511
CELKEM 54 499 491

KódSP2016/179
Název projektuVyužití HPC pro řešení optimalizace přepravy se zapojením dynamického routingu II
ŘešitelMartinovič Jan Ing., Ph.D.
Školitel projektu
Období řešení projektu01.01.2016 - 31.12.2016
Předmět výzkumuANOTACE

Navrhovaný projekt bude navazovat na projekt "Využití HPC pro řešení optimalizace přepravy se zapojením dynamického routingu" v rámci kterého bylo řešeno propojení optimalizace přepravy a dynamické plánování trasy vozidel (plánování trasy, které na využívá historická a aktuální data o stavu dopravní sítě). V rámci navrhovaného projektu bude zkoumáno využití dalších možností využití HPC pro řešení tohoto problému, vylepšováním směrovacích algoritmů a také s tím související problematikou zpracování a ukládání potřebných dat. V oblasti vytváření rychlostních profilů, které jsou potřeba pro dynamické plánování tras, budeme analyzovat možnosti jejich dalšího vylepšení a to s využitím shlukovacích metod.

IMPAKT NAVRHOVANÉHO PROJEKTU

Vzhledem k výpočetní náročnosti problému optimalizace přepravy se zapojením směrovacích algoritmů s potenciálním využitím předzpracovaných dat (taková data mohou být např. předzpracována pomocí algoritmů pro shlukování dat), v projektu plánujeme využít infrastrukturu spravovanou IT4Innovations. V návaznosti na předchozí projekt budou existující algoritmy a přístupy přizpůsobeny pro jejich efektivní provoz s využitím HPC, je nutné počítat s jejich potenciálním využitím v reálných situacích, kdy vstupní data mohou obsahovat velké množství uzlů a dynamických dat s velmi krátkým časovým intervalem. Optimalizované algoritmy a řešení mohou vést k vytvoření nástrojů, které umožní dopravním společnostem efektivnější plánování svého provozu a z toho plynoucí snížení celkových provozních nákladů. Zvýšení efektivity provozu dopravních společností může mít vliv na dopravu obecně, kdy efektivnějším „chováním“ jednotlivých vozidel bude ovlivněna efektivita využití dopravní sítě. A v neposlední řadě také možný vliv na životní prostředí, neboť snižováním spotřeby paliva dojde také ke snížení emisí.

Z hlediska problémů řešených ve Výzkumném programu 1 na IT4Innovations a zejména nově také v H2020 projektu ANTAREX je problematika dynamického routingu a optimalizace přeprav velice aktuální. V rámci řešení projektu RODOS dochází k monitoringu dopravního proudu na silniční síti České republiky s časovým krokem jedné minuty. Tento zdroj dat představuje významný vstup pro vytvoření rychlostních profilů dopravní sítě, které budou sloužit jako vstup do dynamického routingu. Dalším vstupem jsou data z Národního dopravního informačního centra o aktuálních uzavírkách, nehodách a další událostech na dopravní síti. Tento monitoring a předzpracovaná historická data je potřeba dále využít při predikcích dopravního proudu a také v úlohách optimalizace přeprav a to s využitím dynamické složky dat.

Moderní směrovací algoritmy [1,2] využívají předzpracování dat pro snížení času potřebného pro pozdější vyhledávání tras. Tyto algoritmy však není možné použít s dynamicky se měnícími daty. Existují časově závislé verze těchto směrovacích algoritmů [3,4], které řeší zapojení dynamických dat během plánování trasy, nicméně za cenu pomalého předzpracování dat. Při využití různých metrik a omezení, jako jsou například typ, kategorie a vlastnosti vozidla, možnost využití dálnic a placených úseků a podobně, je nutné pro každou kombinaci těchto parametrů předzpracovat data pro pozdější rychlé vyhledávání tras, což je výpočetně náročná úloha. Proto vznikly směrovací algoritmy [5], které řeší tento problém předzpracováním pouze informací nezávislých na metrice, jako je například hierarchie silniční sítě. Tímto způsobem je možné rychle vyhledávat trasy pro různé metriky. Efektivní přístup ke vstupním datům směrovacích algoritmů je klíčový pro jejich optimální běh. Reprezentace silniční sítě spolu s jejími omezeními a metrikami může klást značné nároky na diskový prostor, z tohoto důvodu jsou zkoumány přístupy, které s pomocí algoritmů pro shlukování dat optimalizují fyzickou reprezentaci dat a minimalizují tak počet přístupů k disku [6,7]. Různými variantami optimalizace přepravy s využitím časově závislého směrování vozidel (směrování vozidel, kdy pro výsledná doba a trasa jízdy je závislá na době vyjetí vozidla z počáteční lokace) se zabývali např. autoři článků [8,9]. Kromě závislosti na času vyjetí vozidla, existují i varianty optimalizace přepravy, kdy je trasa a doba jízdy vozidla závislá na nákladu vozidla [10]. Pro hledání optimálního řešení úloh mohou být použity algoritmy například Iterated Local Search [11] nebo hybridní Ant Colony Algorithm [12]. V článku [13] autoři navrhli paralelní algoritmus pro řešení optimalizace přepravy bez zapojení časové závislosti trasy a doby jízdy vozidel.

REFERENCE:
[1] Geisberger, R., Sanders, P., Schultes, D., & Vetter, C. (2012). Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3), 388-404.
[2] Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., & Werneck, R. F. (2015). Route planning in transportation networks. arXiv preprint arXiv:1504.05140.
[3] Nannicini, G., Delling, D., Schultes, D., & Liberti, L. (2012). Bidirectional A* search on time‐dependent road networks. Networks, 59(2), 240-251.
[4] Kaufmann, H., & Speck, J. (2013). Towards Mobile Time-Dependent Route Planning. Bachelor thesis, Karlsruhe Institute of Technology.
[5] Delling, D., Goldberg, A. V., Pajor, T., & Werneck, R. F. (2011). Customizable route planning. In Experimental algorithms (pp. 376-387). Springer Berlin Heidelberg.
[6] Demir, E., Aykanat, C., & Cambazoglu, B. B. (2010). A link-based storage scheme for efficient aggregate query processing on clustered road networks. Information Systems, 35(1), 75-93.
[7] Demir, E., & Aykanat, C. (2010). Efficient successor retrieval operations for aggregate query processing on clustered road networks. Information Sciences, 180(14), 2743-2762.
[8] Tasa, D., Dellaert, N., van Woensel, T., and de Kok, T. The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transportation Research Part C: Emerging Technologies 48 (2014), 66-83.
[9] Malandraki, C., and Daskin, M. S. Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science 26, 3 (1992), 185-200.
[10] Zachariadis, E. E., Tarantilis, C. D., and Kiranoudis, C. T. The load-dependent vehicle routing problem and its pick-up and delivery extension. Transportation Research Part B: Methodological 71, C (2015), 158-181.
[11] Hashimoto, Hideki, Mutsunori Yagiura, and Toshihide Ibaraki. "An iterated local search algorithm for the time-dependent vehicle routing problem with time windows." Discrete Optimization 5.2 (2008): 434-456.
[12] Balseiro, S. R., Irene Loiseau, and Juan Ramonet. "An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows." Computers & Operations Research 38.6 (2011): 954-966.
[13] Groër, Chris, Bruce Golden, and Edward Wasil. "A parallel algorithm for the vehicle routing problem." INFORMS Journal on Computing 23.2 (2011): 315-330.
Členové řešitelského týmuIng. Vojtěch Cima
Ing. Martin Golasowski, Ph.D.
Ing. Jan Martinovič, Ph.D.
Bc. Martin Moudrý
Ing. Tomáš Režnar
Ing. Robert Skopal
Bc. Radim Strejček
Ing. Radek Tomis
Bc. Petr Zubek
Specifikace výstupů projektu (cíl projektu)SLOŽENÍ TÝMU A JEHO KVALITA

Odborný garant: Ing. Jan Martinovič, PhD;

Členové:
Ing. Martin Golasowski
Bc. Martin Moudrý
Ing. Tomáš Režnar
Ing. Robert Skopal
Ing. Radek Tomis
Bc. Petr Zubek
3 x Zatím neurčený student Mgr. studia 9 až 12 měsíc

Nejhodnotnější výstupy týmu:

Golasowski, M., Litschmannová, M., Kuchař, S., Podhorányi, M., & Martinovic, J. (2015). Uncertainty modelling in Rainfall-Runoff simulations based on parallel Monte Carlo method. Neural Network World, 25(3), 267.

Uncertainty Modelling in Hydrodynamic Simulations using the Parallel Monte Carlo Method, in Proceedings of the Fourth International Conference on Parallel, Distributed, Grid and Cloud Computing for Engineering , Civil-Comp Press, Stirlingshire, UK, Paper 10, 2015.

Tomis, R., Martinovič, J., Slaninová, K., Rapant, L., & Vondrák, I. (2015). Time-Dependent Route Planning for the Highways in the Czech Republic. In Computer Information Systems and Industrial Management (pp. 145-153). Springer International Publishing.

Kromer, P.; Martinovič, J.; Radecký, M.; Tomis, R.; Snašel, V., "Ant colony inspired algorithm for adaptive traffic routing," Nature and Biologically Inspired Computing (NaBIC), 2011 Third World Congress on , vol., no., pp.329,334, 19-21 Oct. 2011

Tomis, R., Martinovič, J., Dvorský, J.: Směrování dopravních vozidel. Metody umělé inteligence v geoinformatice, Univerzita Palackého v Olomouci, 2011, strany 87-102, 978-80-244-2945-8

Režnar, T., Martinovič, J., Slaninová, K., and Grakova, E. Probabilistic time-dependent vehicle routing problem. Presented at the 13th International Symposium on Operations Research, SOR’15 (2015).

Moudrý, M.: Aplikace metod kvadratického programování na ořezání zvukového záznamu v reálném čase. 2014. Bakalářská práce oceněna jako nejlepší bc práce na katedře matematiky, VŠB - Technická univerzita Ostrava, Fakulta elektrotechniky a informatiky.

Tomis, R., Režnar, T. a Martinovič, J. se rámci řešení projektu RODOS podíleli na vytvoření vizualizačního software viaRODOS a to včetně aplikace pro ČT.

CÍLE PROJEKTU A OČEKÁVANÉ VÝSTUPY

• Optimalizace již implementovaných algoritmů, z předchozího projektu, pro řešení optimalizace přepravy se zapojením dynamického routingu s využitím HPC
• Rozšíření a optimalizace implementace směrovacího algoritmu pro plánování trasy s využítím dynamické informace o dopravní síti
• Využití state of the art přístupů v oblasti zpracování a ukládání strukturovaných dat na HPC
• Testování implementovaných algoritmů a prezentování výsledků prostřednictvím příspěvků na konferencích nebo v časopisech indexovaných v databázích Web of Science a Scopus. Cílem je publikace dvou až tří takovýchto příspěvků.

POSTUP ŘEŠENÍ PROJEKTU

Projekt je plánován na dobu jednoho roku. Projekt bude zpracováván paralelně v několika úlohách:
• (Q1) Studium state of the art přístupů v oblasti zpracování a ukládání strukturovaných dat.
• (Q1) Výběr vhodných technologií pro efektivní využití HPC pro řešení daných problémů s využitím infrastruktury IT4Innovations .
• (Q2) Výběr a využití vhodných datových struktur pro ukládání dat.
• (Q2-Q3) Průzkum možností využití shlukovaných dat a metrik kvality jako vstup pro směrovací algoritmus.
• (Q2-Q3) Využití infrastruktury IT4Innovations pro efektivnější implementaci směrovacích a optimalizačních algoritmů.
• (Q1-Q4) Získané výsledky projektu budou publikovány v článcích na konferencích nebo jako články časopisecké.

Rozpočet projektu - uznané náklady

NávrhSkutečnost
1. Osobní náklady
Z toho
0,-0,-
1.1. Mzdy (včetně pohyblivých složek)0,-0,-
1.2. Odvody pojistného na veřejné zdravotně pojištění a pojistného na sociální zabezpečení a příspěvku na státní politiku zaměstnanosti0,-0,-
2. Stipendia172000,-172000,-
3. Materiálové náklady15000,-1468,-
4. Drobný hmotný a nehmotný majetek0,-26801,-
5. Služby10900,-0,-
6. Cestovní náhrady145000,-142631,-
7. Doplňkové (režijní) náklady max. do výše 10% poskytnuté podpory38100,-38100,-
8. Konference pořádané VŠB-TUO k prezentaci výsledků studentského grantu (max. do výše 10% poskytnuté podpory)0,-0,-
9. Pořízení investic0,-0,-
Plánované náklady381000,-
Uznané náklady381000,-
Celkem běžné finanční prostředky381000,-381000,-