VYUŽITÍ METOD TEORIE GRAFŮ PRO HLEDÁNÍ NEJSPOLEHLIVĚJŠÍ CESTY V DOPRAVNÍ SÍTI

108

LOGVD 2012 - Žilina 20.-21.9.2012 Dopravná logistika a krízové situácie

VYUŽITÍ METOD TEORIE GRAFŮ PRO HLEDÁNÍ NEJSPOLEHLIVĚJŠÍ CESTY V DOPRAVNÍ SÍTI Andrea Peterková

*)

Anotace:

V článku je přiblíženo sociální riziko – dopravní nehody, o kterých jsme každý den díky médiím informování. Dále je přiblížena optimalizační metoda teorie grafů – hledání nejspolehlivější cesty v grafu, která může být využita při určování cesty například při přepravě speciální záchranné techniky. In the article is described by social risk - traffic accidents which we are information every day thanks to the media. Finding the most reliable path in a graph is a one of methods optimization method of graph theory. We can be used the method in determining the transport routes such as special rescue techniques.

1 MIMOŘÁDNÉ UDÁLOSTI V SEKTORU DOPRAVA Pojem doprava lze definovat jako soubor činností, pomocí kterých se uskutečňuje záměrný pohyb dopravních prostředků po dopravních komunikacích. Krizovým stavem v dopravě lze chápat stav, kdy je narušena normální funkce odvětví dopravy nebo celého dopravního systému a navození normálního stavu není zvládnutelné pomocí integrovaného záchranného systému, speciálními službami a prostředky resortu dopravy, které jsou běžně dosažitelné. Pro obnovení funkčnosti systému je nutné využít sil a prostředků rozpracovaných v krizových plánech subjektu hospodářské mobilizace resortu dopravy (Pavlíček, 2001). Mimořádné události (MU) v dopravě lze dělit podle původu na: • MU vně dopravního systému – situace, které jsou vyvolány příčinami, na které reagují státní orgány vyhlášením krizových stavů, v nichž dopravní systém plní svoji nezastupitelnou funkci v jiných, složitějších podmínkách a řídí se zpracovanými krizovými plány. Mezi vnější příčiny vzniku mimořádných událostí můžeme považovat přírodní faktory, ale i teroristický útok, sabotáž, vojenský konflikt aj., • MU uvnitř dopravního systému – mimořádné události, jejichž spouštěcím mechanismem je zdroj uvnitř systému: člověk, dopravní prostředek.

1.1 DOPRAVNÍ NEHODY Dopravní nehody jsou sociální rizika, která můžeme považovat za mimořádné události uvnitř dopravního systému, protože na jejich vznik mají vliv tyto faktory:  vozidlo,  dopravní cesta a prostředí,  člověk (řidič, chodec, cyklista).

*) Andrea Peterková, Ing. , Fakulta špeciálneho inžinierstva, Katedra krízového manažmentu, Žilinská univerzita v Žilině, Ul. 1. mája 32, 010 26 Žilina, e-mail: [email protected]

LOGVD 2012 - Žilina 20.-21.9.2012

109

Dopravná logistika a krízové situácie

Ze statistických údajů posledních let vyplývá, že lidský činitel je hlavní příčinou dopravních nehod a způsobí až 85% všech dopravních nehod. Dopravní cesta a prostředí je příčinou vzniku až 10 % dopravních nehod a vozidlo a jeho technický stav v 5 % nehod. Z uvedených statistických hodnot jasně vyplývá, že je nutné zvýšit tlak na zlepšení techniky jízdy řidičů, aby se předcházelo vzniku dopravních nehod.

Obr. 1 Podíl jednotlivých faktorů na vzniku dopravní nehody (zdroj: Slabý, 2005)

2 HLEDÁNÍ NEJSPOLEHLIVĚJŠÍ CESTY V GRAFU Hledání optimálních cest v grafech je jednou ze základních a velmi často využívaných metod teorie grafů. Mezi úlohy nalezení optimálních cest patří zejména: • nejkratší (minimální) cesty, • nejspolehlivější cesty, • cesty s maximální kapacitou. Pro všechny úlohy platí, že graf je obyčejný, souvislý, hranově ohodnocený, neorientovaný a reprezentuje model reálného systému silniční, železniční, letecké, vodní, potrubní, pásové nebo jiné dopravní sítě. Vrcholy grafu představují křižovatky dopravních komunikací a hrany grafu odpovídají úsekům komunikace.

2.1 NEJSPOLEHLIVĚJŠÍ CESTA V GRAFU Při hledání nejspolehlivější cesty v grafu se využívá postup hledání nejkratší cesty z počátečního do koncového vrcholu. Pro nalezení cesty je nezbytné, aby hrany grafu byly ohodnoceny pravděpodobnostmi p(h ) úspěšného průchodu příslušnou hranou. Ohodnocení pravděpodobnosti neúspěšného průchodu hranou je třeba přepočítat na pravděpodobnost úspěšného průchodu hranou s využitím výpočtu pro opačný jev p (h ) = 1 − p(h ) . V silniční dopravě se do pravděpodobnosti průchodu hranou může považovat např. o pravděpodobnost, s jakou na daném úseku komunikace nedojde

110


k nehodě, pravděpodobnost, že nenastane krizová situace (sněhová kalamita, zasypání, zatopení aj.). Spolehlivost cesty m(u, v ) ∈ M mezi dvěma zadanými vrcholy u, v ∈ V grafu G = (V , X , p )

je definována:

s (m(u , v )) =

∏ p(h ) ; 0 ≤ p(h ) ≤ 1 .

h∈m (u ,v )

Cesta m ∗ (u, v ) ∈ M je nejspolehlivější cestou mezi vrcholy u a v, jestliže pro ní platí následující vztah: s (m ∗ (u , v )) = max {s (m(u , v ))} . m (u ,v )∈M

2.3 ALGORITMUS HLEDÁNÍ NEJSPOLEHLIVĚJŠÍ CESTY V GRAFU Uvažujme obyčejný, souvislý, hranově ohodnocený, neorientovaný graf G. 1. krok: V grafu G si označíme počáteční vrchol cesty u (např. u = v0) koncový vrchol cesty v (např. v = vn). 2. krok: Pokud ohodnocení hran grafu představuje pravděpodobnost úspěšného průchodu hranou, pokračujte na 3. krok. Pokud ohodnocení hran vyjadřuje pravděpodobnost neúspěšného průchodu hranou, změníme ohodnocení následovně: a) p (h ) = 1 − p(h ) , b) p(h ) = p (h ) c) pokračuje na 3. krok. 3. krok: Nově ohodnotíme hrany grafu: o(h ) = − log p(h ) ; je možné použít dekadický i přirozený logaritmus. 4. krok: V grafu vyhledáme minimální cestu. Tato cesta je zároveň nejspolehlivější cestou (Volek, 2002).

3 PŘÍPADOVÁ STUDIE

Za případovou studii jsem si vybrala nalezení nejspolehlivější cesty z obce Turzovka do obce Námestovo. Obě obce i cesta mezi nimi se nachází v Žilinském kraji. Pro výpočet nejspolehlivější cesty je nutné ohodnotit hrany pravděpodobností průchodu hranou. Při určování pravděpodobnosti jsem využila vzorec pro výpočet ukazatele pravděpodobnosti vzniku dopravních nehod PN: PN =

N0 , 365 ⋅ I

kde: N 0 …celkový počet nehod ve sledovaném období, I …celková denní intenzita provozu (voz./24 hod.).

Tento ukazatel vypovídá o pravděpodobnosti vzniku nehody ne určité komunikaci ve vztahu k jízdnímu výkonu. Na určení pravděpodobnosti vzniku dopravních nehod jsem vycházela z údajů poskytnutými Obvodními ředitelstvími Policejního sboru Žilinského kraje,

111


z rizikových map dostupných na www.eurorap.org a z hodnocení rizikových úseků na http://natankuj.sme.sk/bezpecnost-ciest?page=min).

Tab. 1 Vrcholy grafu Označení vrcholu Název obce v0 v1 v2 v3 v4 v5 v6 v7 v8 v9

Turzovka Čadca Bytča Krásno nad Kysucou Žilina Stará Bystrica Terchová Martin Párnica Námestovo

v1

v5

4,063.10-05

2,325.10-05

6,149.10-05

v3

2,502.10-05

2,939.10-05

v0

v6

2,52.10-05 2,752.10-05

v9

5,069.10-05 2,634.10-05

v4

3,959.10-05

v8

3,997.10-05 v2

2,601.10-05

2,446.10-05 v7

Obr. 2 Graf s pravděpodobnosti neúspěšného průchodu hranou (pravděpodobnost vzniku dopravních nehod)

112


v1

v5

0,9999594

0,9999767

0,9999385

v3

0,9999750

0,9999706

v0

v6

0,9999748 0,9999725

v9

0,9999493 0,9999737

v4

0,9999604

v8

0,9999600

0,9999740

0,9999755 v7

v2

Obr. 3 Graf s pravděpodobnosti úspěšného průchodu hranou (pravděpodobnost, že nevznikne dopravní nehoda) 0,108.10-04

0,385.10-04 v5

v1

0,9999594 0,9999767 0,209.10-04 v3 0,101.10-04 0,176.10-04

0,9999750 0,108.10-04

0,9999748

v0

0,9999385 0,267.10-04

0,127.10-04

0,650.10-04

v6

0,109.10-04

0

0,9999706

0,119.10-04 0,9999725

0,437.10-04

0,9999493 0,220.10-04

0,114.10-04

v4

0,171.10-04 0,173.10-04

0,9999604

v9

0,9999737

0,318.10-04 0,9999755

0,9999600

0,106.10-04

v2

0,112.10-04

v8

0,536.10-04

0,9999740

v7

0,171.10-04

0,424.10-04

Obr. 4 Výpočet ohodnocení vrcholů grafu 0,108.10-04

0,385.10-04

v1

v5

0,9999594 0,9999767 0,209.10-04

0,9999385

v3

0,9999750

0,9999706

v0

0,650.10-04

v6

0,9999748 0

0,9999725

0,437.10-04

0,9999737

v4

0,9999604

v8

0,318.10-04 0,9999600 v2

0,171.10-04

v9

0,9999493

0,536.10-04 0,9999740

0,9999755 v7

0,424.10-04

Obr. 5 Nalezení nejspolehlivější cesty

113


Z grafu je zřejmé, že podle ohodnocení pravděpodobnosti vzniku silničních dopravních nehod by nejspolehlivější cestou byla cesta: Turzovka – Čadca – Krásno nad Kys. – Žilina – Martin – Párnica – Námestovo.

ZÁVĚR V rámci projektu Agentury na podporu vědy a výzkumu, ve kterém jsme spoluředitelem, se zabývám témou „Ochrana kritické infrastruktury v sektoru doprava“. Jedním z rizik, které ohrožuje bezpečnost dopravy je i sociální riziko – dopravní nehody. Cílem tohoto článku bylo přiblížení metody teorie grafů a její využití při určování nejspolehlivější cesty na základě pravděpodobnosti vzniku dopravních nehod. Hledání nejspolehlivější cesty by se dala využít při určování cesty při převozu speciální záchranné techniky, při hledání evakuační trasy – trasy, kde se neprojevují negativní účinky krizového jevu. Dále by se algoritmus hledání nejspolehlivější cesty mohl využít při zanášení nebezpečných silničních úseků do navigačních přístrojů (GPS).

♦♦♦ Literatura

[1] VOLEK, J.: Operační výzkum I, Pardubice: Univerzita Pardubice, 2002.ISBN 80-7194-410-6 [2] Mapy rizik v cestní dopravě, online. [cit.2012-6-24]. Dostupné na WWW: www.eurorap.com

[3] VIDRIKOVÁ, D.: Ochrana prvkov kritickém infraštruktury v cestnej doprave, [cit.2012-6-26]. Dostupné na WWW: http://www.logistickymonitor.sk/en/images/prispevky/ochrana-prvkov.pdf [4] PAVLÍČEK, F.: Krizové stavy a doprava, Praha: Vydavatelství ČVUT, 2001. ISBN 80-01-02272-2 [5] KAŠPAR, V.: Vybrané metódy operačnej analýzy vo vojenskej doprave a vojenskom staviteľstve (metódy sieťovej analýzy - CPM, PERT), Žilina, FŠI ŽU, 1998, ISBN: 80-88829-27-5 [6] SLABÝ, P.-DLOUHÁ, E.: Dopravní stavby a systémy 20, 30, Praha: ČVUT, 2005, ISBN 80-01-02453-9 [7] EuroRAP – cesty Slovenska a ich rizikovost, [cit.2012-6-24]. Dostupné na

WWW: http://natankuj.sme.sk/bezpecnost-ciest?page=min Tato práce byla podporována Agenturou na podporu výzkumu Smlouva o poskytnutí prostředků č. APVV-0471-10 a vývoje na základě smlouvy č. APVV-0471-10.

Recenzent:

Ing. Vladislav Kašpar, PhD.

VYUŽITÍ METOD TEORIE GRAFŮ PRO HLEDÁNÍ NEJSPOLEHLIVĚJŠÍ CESTY V DOPRAVNÍ SÍTI

Recommend Documents