Kartografické modelování IX – síťové analýzy vzdáleností jaro 2015 Petr Kubíček kubicek@geogr.muni.cz Laboratory on Geoinformatics and Cartography (LGC) Institute of Geography Masaryk University Czech Republic PŘÍŠTÍ TÝDEN ODPADÁ VÝUKA! PĚKNÉ JARO  Kartografické modelování Analýzy nad vektorovou sítí • Analýzy sítí jsou významnou oblastí aplikace GIS. • V podstatě se jedná opět o hledání nejkratší vzdálenosti (nejmenšího nákladu), ale s tím rozdílem, že sítě jsou vektorovou reprezentací. • Síť tvoří (orientovaný) ohodnocený graf, skládající se z uzlů (průsečíků) a hran (linií). Kartografické modelování Tvorba sítě • Před využíváním síťových analýz je nutné vytvořit všechny datové struktury, které jsou pro pozdější analýzy nutné – tedy vytvořit síť. • Postup tvorby sítě: – Je třeba získat liniovou vrstvu, nad kterou budou analýzy prováděny (ulice, rozvody, kanalizace). – Tato data musí být topologicky čistá (hlavně musí splňovat konektivitu a znalost směru) – nutná a v zásadě postačující podmínka pro analýzy sítí. – Následně lze síti přiřadit pravidla, která určují, jak je možné se pohybovat mezi jednotlivými uzly. – Přiřazení dalších atributů pro výstupy z analýz (zejména itineráře) – přidání jmen ulic, významných bodů (adres), názvy křižovatek, … Kartografické modelování Dopravní síť města Ostrava (Horák a kol. 2015) Kartografické modelování Pravidla pohybu po síti Pravidla uzlová a hranová: • Uzlová pravidla definují směr pohybu uzlem. – Například, pokud budu mít uliční síť, na některých křižovatkách není povoleno odbočení doleva či doprava. – Náklady na odbočení v různých směrech. • Hranová pravidla definují směr a rychlost pohybu po hraně. – Ulice mohou být jednosměrné, uzavřené, s nadefinovanou maximální a průměrnou rychlostí. • Pravidla mohu definovat pro různé druhy dopravy, pro různou denní dobu, … atd. • Monomodální x multimodální sítě. Kartografické modelování Hranová pravidla • technická – počet pruhů; – šířka vozovky; – typ povrchu vozovky; – maximální povolená výška pro vozidla. • dopravní – typ komunikace; – funkční kategorizace (např. třída komunikace); – maximální povolená rychlost; – reálná rychlost průjezdu; – jednosměrný provoz; – impedance = odpor (typicky náklady pro projetí danou hranou v různých směrech či jednotkové náklady, nemusí být shodné v různých směrech – např. cesta do kopce a z kopce). Kartografické modelování Bariéry Bariéry typicky reprezentuji omezení v síti, mohou ale také reprezentovat hustotu dopravy v síti a tím upravovat náklady za překonání hran a uzlů. • zcela znemožňující průjezd (např. kompletní uzavírka komunikace), • průjezdné, ale zvyšující náklady na překonání bariery (např. Střídavě jednosměrný provoz řizený semafory v rámci komunikace). Horák a kol. 2015 Kartografické modelování Dynamická segmentace a lineární referencování • Pravidla jsou obvykle uložena v atributových tabulkách. • Protože změna atributu nemusí vždy přijít pouze v uzlu (například změna max. povolené rychlosti), využívá se někdy speciální datový model pro liniové vrstvy – dynamickou segmentaci. • Je nutné definovat: • Cestu (linear feature) jako lineární prvek (polylinie), • Staničení (measurement system) - staničení má počátek v nějakém zvoleném bodě a jeho hodnota je dána vzdáleností od tohoto bodu. • Událost (event) je atribut spojený s cestou. Událost je dvojího druhu: bodová (např. havárie na dálnici), jež vyžaduje jedno staničení pro své určení, či liniová (např. druh povrchu dálnice v určitém úseku nebo rekonstrukce určitého úseku), jež vyžaduje dvoje staničení (od, do) pro své určení. Kartografické modelování Lineární referencování • Dynamická segmentace pak definuje polohu lineárního prvku pomocí cesty a události na ní. • Podle jiné definice hovoříme o procesu transformace lineárně referencovaných dat (událostí), které jsou uloženy v datové tabulce, do útvarů, které mohou být zobrazeny a analyzovány na mapě. Vztah linie 1: M – jedna linie M atributů Kartografické modelování Vlastnosti síťového modelu Pravidla umožní simulovat následující vlastnosti: • Cena cesty (pomocí max. rychlosti, času cesty a vzdálenosti) – základní atribut síťových dat, hrana musí obsahovat tento atribut vyjádřený alespoň jedním z těchto způsobů. • Lze vytvořit i další modifikace cen cesty: – Může se měnit s denní dobou – ráno, odpoledne, v noci. – Může záviset na směru průchodu hranou či uzlem (cesta tam je časově kratší, než cesta zpět, odbočení doprava je kratší než zabočení doleva). – Změna atributu může v reálném světě přijít kdykoli na linii a ne jen v uzlu (např. změna maximální rychlosti). Kartografické modelování Vlastnosti Směrování – přikázané směry jízdy, zákazy (speciální uzlová pravidla), včetně speciálních zákazů pro určité typy pohybujících se objektů (do ulice nesmí nákladní vozidlo) a přiřazení cen za provedení změny směru. Kartografické modelování Vlastnosti Neuzlové body – díky topologickému požadavku konektivity (linie se mohou protínat pouze v uzlových bodech) je třeba vyřešit situace, kdy je třeba modelovat podjezdy a nadjezdy. K tomuse obvykle používají dvě metody: • neplanární uzel – systém povolí protnutí liniových prvků bez nutnosti vytvoření uzlových bodů takže pro tento bod neexistuje křižovatka. • planární uzel – systém protíná liniové prvky pouze v uzlech, pak je nutné zadat takové uzlové atributy, které systém informují zda se jedná o křižovatku nebo o podjezd či nadjezd. Kartografické modelování Vlastní analýzy nad sítí • Hledání optimální trasy – jde o vyhledání optimální trasy mezi dvěma nebo více body (ve stanoveném pořadí nebo bez) na základě ceny cesty (vzdálenost, čas, …). Analýza umí produkovat i pokyny o cestě pro řidiče. Kartografické modelování Vlastní analýzy nad sítí Hledání cesty do nejbližšího zařízení – drobná modifikace předchozí analýzy. Jde o vyhledání optimální trasy do nejbližšího (optimálního) zařízení. • Příklad: Hromadná dopravní nehoda ve velkém městě. Jde o to, nalézt co nejrychlejší způsob, jakse k nehodě dostat sanitkou.Řešení je nalezení optimální cesty od optimálního zařízení k nehodě. • Je možné ještě hledat optimální cestu od nehody do nejbližší nemocnice.Tyto cesty totiž vzhledem ke konfiguraci sítě (jednosměrky) či vzhledem k času (ucpané ulice v určitém v důsledku nehody) nemusí být stejné! Užití bariér (Horák a kol. 2015). Kartografické modelování Vlastní analýzy nad sítí Alokace zdrojů – další možnost aplikace analýzy sítí. • Vyhledání všech lokalit, které jsou od vybraného objektu vzdáleny nějakou cenu cesty. • Příklad: vzdálenost do 30 minut od vyhlášené restaurace. Jak je vidět, je to analýza podobná vytváření obalových zón (buffers), ale bere v úvahu cenu cesty definovanou pomocí sítě (není to jen vzdálenost vzdušnou čarou). • Výsledkem této analýzy jsou tzv. izochrony, což jsou čáry spojující body se stejným časem k dosažení výchozího bodu. Kartografické modelování Vlastní analýzy nad sítí • Problém obchodního cestujícího – návštěva vybraných bodů tak, aby trasa byla optimální. • Cestující musí navštívit každý bod (místo) a na závěr se vrátit do původního bodu. • Aplikační využití při rozvoru balíků, obsluze automatů… Horák a kol. 2015 Kartografické modelování Data pro síťové analýzy • ZABAGED, OpenStreetNet, JSDI • StreetNet (CEDA) aktualizovan 2x ročně, eviduje i useky ve vystavbě, obsahuje i polní a lesní cesty, pro jednotlivé úseky je evidováno větší množství atributů, neobsahuje úseky v soukromých a uzavřených areálech. Kartografické modelování Streetnet ZABAGED Horáka a kol. 2015 Kartografické modelování Aktuální data pro síťové analýzy • Rodos http://rodosdata.it4i.cz/ vytvořit nad silniční dopravou komplexní informační nástavbu a integrovat ji do stávajících telematických systémů. Jádrem centra RODOS je Dynamicky Model Mobility (DMM), který integruje dynamicky model pohybu osob, vozidel a zboží. JAK SI VYTVOŘIT VLASTNÍ SÍŤ? Kartografické modelování Úseky a uzly - ŘSD Kartografické modelování Vlastnosti úseků • Delka_us - délka silničních úseků vyjádřená v metrech • Kod_tr_kom - kód třídy komunikace Kartografické modelování Uzly Kartografické modelování Úsek + uzly Kartografické modelování Ohodnocení úseků hran • Metrika? • čas, potřebný pro pohyb v síti silničních komunikací. • Délka komunikací (hran) a průměrná rychlost=čas. Kartografické modelování Ohodnocení úseků • Pro úseky silnic jednotlivých tříd jsou přiřazeny průměrné rychlosti a vypočítán čas potřebný k jejich překonání. JAK SE HODNOTÍ SÍŤ? Kartografické modelování Dijkstra algoritmus Algoritmus sloužící k nalezení nejkratší cesty v grafu. Je konečný (pro jakýkoliv konečný vstup algoritmus skončí), protože v každém průchodu cyklu se do množiny navštívených uzlů přidá právě jeden uzel, průchodů cyklem je tedy nejvýše tolik, kolik má graf vrcholů. Funguje nad hranově kladně ohodnoceným grafem. Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Kartografické modelování Dijkstra algoritmus https://www.youtube.com/watch?v=8Ls1RqHCOPw