Schválené projekty 2015

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 2015

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

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

fakultapřidělená částka v Kč
FBI  1 172 500
EKF  4 962 700
FAST  3 070 000
FS  8 256 000
FEI 12 282 100
HGF  5 433 000
FMMI  6 188 000
VC 10 223 000
CELKEM 51 587 300
KódSP2015/157
Název projektuVyužití HPC pro řešení optimalizace přepravy se zapojením dynamického routingu
ŘešitelMartinovič Jan Ing., Ph.D.
Školitel projektu
Období řešení projektu01.01.2015 - 31.12.2015
Předmět výzkumuANOTACE

Cílem projektu je zapojení dynamického routingu (dynamického plánování trasy) při řešení optimalizace přepravy, které může být využito např. při optimalizaci rozvozu zásilek nebo přepravě zboží. Dynamický routing bude využívat historická a aktuální data o dopravní situaci. Cílem optimalizace je snižování nákladů (např. menší spotřeba paliva, kratší čas rozvozu, nižší náklady na zaměstnance) při zadaných vstupních podmínkách (např. pracovní doba zaměstnanců, časové okna pro naložení a vyložení nákladu, doba trvání různých úkonů, vlastnosti vozidel, heterogenní vozový park, volba trasy podle hmotnosti nákladu a dopravních omezení na cestách). Hledání řešení s vysokým množstvím vstupních podmínek a zapojení dynamického plánování trasy je výpočetně náročné, a proto je nutné využít HPC.

IMPAKT NAVRHOVANÉHO PROJEKTU

Využíváním dynamického routingu v samotném procesu optimalizace přepravy dojde ke zvýšení složitosti celého problému a tak i k výpočetní náročnosti. Proto je potřeba nalézt takový algoritmus, který bude efektivně použitelný v reálném protředí, které obsahuje velké množství uzlů a dynamických dat. Výstupy mohou také mít význam na ovlivnění efektivity dopravních společností (snížení nákladů, zkrácení časů, efektivnější plánování a využití vozidel atd.) a také 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 v projektu RODOS 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 v 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. Proto je důležité nastudovat a implementovat algoritmy dynamického routingu a ty využít při řešení optimalizace přeprav.
Členové řešitelského týmuIng. Tomáš Kocyan
Ing. Jan Martinovič, Ph.D.
Bc. Martin Moudrý
Ing. Tomáš Režnar
Ing. Radek Tomis
Specifikace výstupů projektu (cíl projektu)SLOŽENÍ TÝMU A JEHO KVALITA

Odborný garant: Ing. Jan Martinovič, PhD

Členové:
Bc. Martin Moudrý
Ing. Tomáš Režnar
Ing. Radek Tomis

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

Kromer, P.; Martinovic, J.; Radecky, M.; Tomis, R.; Snasel, 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

Tomis, R., Režnar, T. a Martinovič, J. jsou členové týmu RODOS, kde se
zabývají zpracováním a vizualizace dopravních dat a to včetně aplikace pro
ČT.

Režnar T.: Use of the Simplex Algorithm for Solving the Multiple Traveling
Salesman Problem, Wofex, 2014

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.

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

• Implementace algoritmu pro řešení optimalizace přepravy se zapojením
dynamického routingu s využitím HPC při řešení optimalizačního problému
• Implementace směrovacího algoritmu pro plánování trasy s využívatím dynamické informace
o dopravní síti (zvážení využití HPC pro předzpracování dat)
• Testování implementovaných algoritmů a prezentování výsledků prostřednictvím příspěvků na konferencích a v časopisech indexovaných v databázích Web of Sceince a Scopus. Cílem je publikace dvou až tří takovýchto příspěvků.
• Dále budou tyto algoritmy začleňovány do existujících řešení v rámci projektu RODOS.

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) Datová analýza vstupů a výstupů problémů.
• (Q1) Průzkum a výběr vhodných datových struktury a algoritmů [4] pro dynamický routingy.
• (Q2-Q3) Implementace vybraného algoritmu pro řešení daného problému. Zvažujeme implementaci algoritmu
Large Neighborhood Search [1] nebo jeho varinaty podle [2]. Paralelní variantou tohoto algoritmu se zabýval článek [3], kde jej však autor využil pro
řešení odlišného problému.
• (Q2-Q3) Implementace vybraného algoritmu pro dynamický routing s využitím vhodných datových struktur.
• (Q2-Q4) V průběhu projektu budou získané výsledky publikovány v článcích na konferencích s případným rozšířením do článku časopiseckého.

REFERENCE

[1] Shaw, P. (1998). Using constraint programming and local search methods
to solve vehicle routing problems. In Principles and Practice of Constraint
Programming – CP98, volume 1520 of Lecture Notes in Computer Science,
pages 417–431. Springer Berlin / Heidelberg.
[2] Stefan Ropke, David Pisinger; An Adaptive Large Neighborhood Search
Heuristic for the Pickup and Delivery Problem with Time Windows; 2005
[3] Vera C. Hemmelmayr, Sequential and parallel large neighborhood search
algorithms for the periodic location routing problem, European Journal of
Operational Research, Available online 26 November 2014, ISSN 0377-2217
[4] Daniel Delling and Giacomo Nannicini. 2012. Core Routing on Dynamic
Time-Dependent Road Networks. INFORMS J. on Computing 24, 2 (April
2012), 187-201.

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. Stipendia84000,-84000,-
3. Materiálové náklady16800,-7653,-
4. Drobný hmotný a nehmotný majetek0,-6343,-
5. Služby0,-0,-
6. Cestovní náhrady90000,-92804,-
7. Doplňkové (režijní) náklady max. do výše 10% poskytnuté podpory21200,-21200,-
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áklady212000,-
Uznané náklady212000,-
Celkem běžné finanční prostředky212000,-212000,-