TAČR – Retia


Efektivní přístupy k úsporným a adaptabilním systémům údržby a obsluhy dopravních sítí

Identifikace projektu: TH02010930

Období řešení: 1/2017 – 12/2020

Řešitelé:

Cílem projektu je vytvoření metodiky zpracování nehomogenních vstupních dat s využitím geoinformačních systémů pro optimalizační výpočty zaměřené na obsluhu a údržbu dopravních sítí (Metodika zpracování vstupních dat pro optimalizační výpočty).

  • Metodika bude zpracována tak, aby korespondovala s typem dat, kterými společnosti zabezpečující obsluhu a údržbu obecně disponují a aby výsledný soubor dat odpovídal požadavkům optimalizačních výpočtů.
  • Funkčnost navržené metodiky bude ověřována na množinách reálných dat od partnerů z praxe.

Výsledná řešení (optimální trasy) budou zpracována v podobě specializovaných map, primárně pro verifikaci metodiky, sekundárně pro jednotlivé partnery z praxe.

V současné době existuje velké množství malých, středních i velkých společností z řad techn. služeb, městských služeb, komerčních společností, které zabezpečují služby spojené s údržbou a obsluhou dopravních sítí. Pro plánování obsluhy využívají především empirických zkušeností. Specializovaný software je spojen s vysokou fin. náročností (licence, školení pracovníků) a zároveň neposkytuje možnost řešit místní specifika. Projekt vhodně propojuje výpočetní možnosti s dispozicemi zákazníků. Metodika vysvětluje způsob přípravy potřebných dat z různě definovaných (nehomogenních) vstupů. Partneři z praxe verifikují použitelnost postupu, přičemž využijí poskytnutá řešení Nmap. Existují i zákazníci, kteří využijí dílčí výstupy – posloupnosti referenčních bodů pro GPS. Výstupy jsou ihned použitelné v praxi, organizační i úsporný efekt.

Fáze řešení projektu

  • (2017) Přípravná a studijní fáze
  • (2018) Rozbor dat a jejich zpracování
  • (2019) Příprava metodiky a ověřovací výpočty
  • (2020) Tvorba metodiky a specializovaných map

Další informace poskytne: Ing. Bc. Petr Kozel Ph.D. (odpovědný řešitel)

Výstupy projektu

ANALÝZA STÁVAJÍCÍCH ŘEŠENÍ

Počáteční fáze řešení projektu vychází z detailního rozboru problému, který je úzce spjat s analýzou stávajících řešení.

K tomu, aby bylo možné kvalitně popsat konkrétní problém, bylo nutné vyjít z podrobné rešerše, která započala již před samotným řešením projektu, stále probíhá a je plánována i do nadcházejících roků řešení projektu. Cílem této časově i tematicky plošné rešerše je shromáždit širokou množinu informací o stavu průmětu teoretického poznání a praktických aplikací do praxe. Toto mapování skutečnosti je prováděno v rámci komunikace nebo přímo spolupráce se subjekty, které se věnují údržbě a obsluze dopravních sítí. V praxi se nejčastěji jedná o subjekty, které zabezpečují svoz komunálního odpadu, údržbu a úklid pozemních komunikací a zjišťování probíhá jak na národní, tak na mezinárodní úrovni.

ŠKOLENÍ ŘEŠITELŮ V OBLASTI POUŽÍVANÉHO SOFTWARE

V rámci prvního řešitelského roku bylo naplánováno školení řešitelů v oblastech používaného software. Školení a kurzy, které proběhly, byly zaměřeny jak na teoretická východiska, která jsou prostřednictvím výpočetních nástrojů zpracovávána, tak na realizaci výpočtů v nástrojích samotných.

Algoritmická teorie grafů

V období měsíců únor 2017 – květen 2017 probíhalo školení Algoritmická teorie grafů, které se uskutečnilo na Fakultě riadenie a informatiky Žilinské univerzity v Žilině. Náplní kurzu bylo podrobné představení oblasti teorie grafů s důrazem na algoritmy, které jsou pro řešení úloh náležejících do teorie grafů používány. Teoretické poznatky byly použity při řešení dílčích úloh a promítnuty do odborných výstupů. Některé z algoritmů teorie grafů jsou postupně implementovány ve výpočetním prostředí Xpress-IVE a Wolfram Mathematica.

Školení se pravidelně zúčastňoval Ing. Mgr. Petr Kozel, Ph.D.

Základy programování v R

V období měsíců březen 2017 – květen 2017 rovněž probíhal kurz s názvem Základy programování v R, který byl realizován na Ekonomické fakultě VŠB – Technické univerzity v Ostravě. Cílem kurzu bylo představení programovacího jazyka R. V první části kurzu bylo probráno využití jazyka R v numerických matematických výpočtech, včetně maticového počtu. Další části kurzu byly věnovány programátorským konstrukcím implementovaným v jazyce R. Předmětem kurzu dále bylo seznámení se s datovými typy používanými v jazyce R, s vytvářením cyklů, větvením výpočtů a podmíněnými příkazy. Poslední část byla věnována speciálním funkcím jazyka R, které urychlují práci s rozsáhlými seznamy a maticemi.

Kurzu se zúčastňovali: Ing. Mgr. Petr Kozel, Ph.D., RNDr. Šárka Michalcová, Ph.D., Ing. Václav Friedrich, Ph.D., RNDr. Marek Pomp, Ph.D. a Ing. Lucie Orlíková, Ph.D.

Wolfram Mathematica – A First Course

Školení Mathematica – A First Course se konalo dne 22. září 2017 v prostorách Ekonomické fakulty VŠB – Technické univerzity v Ostravě. Lektorem byl doc. János Karsai z University of Szeged, certifikovaný školitel společnosti Wolfram Company pro střední a východní Evropu a nositel ceny Wolfram Innovator Award. Školení v rozsahu 8 hodin mělo charakter praktického workshopu, kdy každý účastník měl k dispozici počítač s instalací programu Wolfram Mathematica. Cílem školení bylo seznámit  se se základními funkcemi programu Mathematica a vytvořit tak komplexní základ pro pokročilejší práci při řešení aplikací a vývoji softwarových řešení.

Školení se zúčastnili: Ing. Mgr. Petr Kozel, Ph.D., RNDr. Šárka Michalcová, Ph.D., Ing. Václav Friedrich, Ph.D. a RNDr. Marek Pomp, Ph.D.

Online kurzy zaměřené na software Python a R

V období měsíců leden 2017 – prosinec 2017 byl realizován online kurz, zaměřený na paletu programovacích nástrojů, především na software Python a R. Kurz se uskutečňoval prostřednictvím samostudijních webových výukových prezentací.

Programovací jazyk Python je součástí všech systémů GIS, kde slouží jednak pro automatizaci zpracování a analýzy dat, tak i pro tvorbu nových nástrojů. Kurzy byly rozděleny na základy programování v jazyce Python a dále na tvorbu geoprocessingových skriptů v jazyce Python. Součástí portfolia byly i kurzy zaměřené na síťové analýzy a knihovny nutné pro zpracování a vizualizaci prostorových dat.

Kurzy programovacího jazyka R byly kromě základní práce s jazykem R zaměřeny na propojení tohoto jazyka s prostředím GIS. Pro práci v prostředí GIS je k dispozici balíček geoR, který pak umožňuje zpracovávat data přímo přes rozhraní systému GIS.

Online kurzů využili: Ing. Lucie Orlíková, Ph.D. a Ing. Václav Friedrich, Ph.D.

ODBORNÉ VÝSTUPY

Dílčí výsledky, kterých bylo v průběhu prvního řešitelského roku dosaženo, byly podkladem pro odborné výstupy v podobě článků a vystoupení na konferenci. Jedná se o dva příspěvky na odborné konferenci a jednu publikaci v odborném periodiku.

Příspěvky na konferenci

Využití „sweep algorithm“ pro dekompozici množiny vrcholů a následné řešení úlohy obchodního cestujícího v dekomponovaných podmnožinách

  • Pomp, M., Kozel, P., Michalcová, Š., Orlíková, L. Using the Sweep Algorithm for decomposing a set of vertices and subsequent solution of the traveling salesman problem in decomposed subsets. Proceedings of 35th International Conference on Mathematical Methods in Economics, Hradec Králové, 2017.
    • Cílem úlohy obchodního cestujícího je nalézt optimální trasu, která prochází všemi vrcholy daného grafu právě jednou s výjimkou počátečního vrcholu a která má minimální délku. Základním požadavkem je, že kapacita obslužného vozidla pojme všechny požadavky rozmístěné ve vrcholech grafu (ať už se jedná o svoz či rozvoz). V praxi je však běžné, že kapacita obslužného vozidla je menší než součet požadavků, které je nutno uspokojit. Jedním ze základních způsobů, jak lze tento problém odstranit, je dekompozice vstupní množiny vrcholů na několik podmnožin tak, že součet kapacit požadavků v jednotlivých podmnožinách nepřesahuje kapacitu obslužného vozidla. V těchto podmnožinách pak lze optimální trasu vyhledat některým z dostupných způsobů (exaktní řešení – u úloh menšího rozsahu, heuristika – u rozsáhlých úloh). Předložený příspěvek je věnován využití „sweep algorithm“ pro dekompozici vstupní množiny vrcholů a následné vyhledání optimálních tras s využitím exaktního algoritmu. Výpočetní experimenty předložené v tomto příspěvky byly realizovány v podmínkách plánování optimálních tras pro obslužná vozidla zabezpečující svoz komunálního odpadu konkrétní komerční společnosti.

Transformace úlohy o vyhledání minimální Hamiltonovy kružnice na úlohu o vyhledání Eulerova tahu

  • Kozel, P., Friderich, V., Michalcová, Š. Transformation of Task to Locate a Minimal Hamiltonian Circuit into the Problem of Finding the Eulerian Path in Vehicle Routing Application. Proceedings of 35th International Conference on Mathematical Methods in Economics, Hradec Králové, 2017.
    • V první řadě se jedná o úlohy zaměřené na obsluhu vrcholu dopravní sítě, kdy vycházíme z úlohy o vyhledání minimální Hamiltonovy kružnice. V druhé řadě se jedná o úlohy zaměřené na obsluhu hrany dopravní sítě, kdy je výchozí úlohou vyhledání Eulerova tahu. Předložený příspěvek se zamýšlí nad možností a způsobem převodu úlohy o vyhledání minimální Hamiltonovy kružnice na úlohu o vyhledání Eulerova tahu, která je modifikována pro širší dopravní síť. V této širší dopravní síti je k obsluze hran možné použít doplňkovou síť umožňující efektivní přejezdy obslužného vozidla vedoucí ke snížení neproduktivně ujeté vzdálenosti. Představené přístupy využívají lineárního programování. V příspěvku jsou představeny experimenty na datech vycházejících z praxe.

Publikace v odborném periodiku

Dekompozice okružních jízd s využitím matematického programování

  • Kozel, P. Dekompozice okružních jízd s využitím matematického programování. Perner’s Contacts, Univerzita Pardubice, Dopravní fakulta Jana Pernera, číslo 3, ročník XII. str. 62-70.
    • Při řešení úloh zaměřených na obsluhu vrcholu dopravní sítě je nutné věnovat pozornost nejen optimální posloupnosti vrcholů s ohledem na zvolené optimalizační kritérium (např. celkovou ujetou vzdálenost), ale též dalším omezením, která plynou z potřeb praxe. Může se jednat například o nepřekročení kapacity obslužného vozidla. Předložený příspěvek je věnován využití dekompoziční metody využívající matematického programování, založené na tzv. Route-First Cluster-Sedond přístupu. V rámci této dvoukrokové metody je nejprve hledána optimální trasa obslužného vozidla a teprve následně je tato trasa dekomponována na dílčí okružní jízdy při zohlednění kapacity obslužného vozidla. V textu jsou postupně prezentovány matematické modely, které lze k realizaci uvedeného přístupu využít. Celý dekompoziční postup je též ilustrován na konkrétních příkladech.