CV08 – Síťové analýzy a geokódování

Síťové analýzy

Síťové analýzy představují sadu nástrojů pro řešení úloh typu nalezení nejkratší trasy (problém obchodního cestujícího), optimalizace rozmístění zdrojů či cílových stanic, zjišťování dostupnosti zařízení apod. Hlavním zdrojem dat pro tyto analýzy je ohodnocená uliční síť v podobě vektorové liniové vrstvy, kdy každý liniový segment má přiřazenu informaci o nákladnosti jeho průjezdu (nejčastěji časový údaj).

Typy síťových analýz:

1. Trasování cest:
   • Identifikace nejkratší cesty nebo nejrychlejších tras mezi dvěma body na síti. To může zahrnovat hledání optimální trasy pro navigaci vozidel nebo chodců.
2. Analýza dostupnosti:
   • Stanovení oblastí, které jsou dosažitelné z daného bodu nebo skupiny bodů na základě časových nebo vzdálenostních limitů. Například identifikace, jak daleko lze dojet autem za 30 minut z určitého bodu.
3. Optimalizace cestovního plánu:
   • Plánování tras vozidel tak, aby byly minimalizovány náklady, čas nebo jiné kritéria. Toto se často nazývá problém vehicle routing problem (VRP).
4. Analýza nejbližších zařízení:
   • Identifikace nejbližšího bodu nebo zařízení k danému bodu. To může být užitečné například pro hledání nejbližší nemocnice k pacientovi.
5. Analýza hustoty sítě:
   • Stanovení, jak hustě je síť pokryta různými prvky, jako jsou silnice nebo elektrické vedení. Toto může být užitečné pro plánování infrastruktury.
6. Přiřazování zařízení k poptávkovým místům:
   • Rozdělení úloh mezi různé zařízení na základě poptávky a umístění. Například rozdělení doručovacích zásilek mezi různé sklady tak, aby byla minimalizována doba a náklady.

Geokódování adres

Geokódování neboli adresování (address matching, geocoding) umožňuje připojit souřadnice k záznamům lokalizovaným adresou pomocí připojení k souboru, který obsahuje adresy i souřadnice. Geokódování využívá strukturované informace, kdy je adresa popsána v několika polích. Cílem geokódování je lapidárně řečeno umístit bodové objekty do mapy. Těmito bodovými objekty mohou být například adresy, místa nehod, místa deliktů, adresy zákazníků, čísla parcel. Obzvláště komplikovanou situací je geokódování zastávek a dalších objektů systému veřejné dopravy.

TSP úloha

Problém je pojmenovaný podle obchodníků, kteří jezdili od města k městu a snažili se tam prodat co nejvíce vysavačů, psacích strojů, nebo třeba encyklopedií. Proto se snažili svou cestu vybranými městy naplánovat tak, aby je všechna projeli s minimálními náklady, tedy po co nejkratší trase.

Problém obchodního cestujícího je NP-těžký optimalizační problém, jehož zadání neformálně zní například takto: je dáno několik měst a vzdálenosti mezi nimi. Úkolem je najít takovou cestu, která navštíví každé město právě jednou. Formálně se jedná o nalezení nejméně ohodnocené hamiltonovské kružnice v úplném ohodnocením grafu. Řešením úlohy je posloupnost měst, která udává, v jakém pořadí se mají města projet.

Problém je složitý především proto, že jeho složitost dramaticky narůstá s rostoucím počtem měst. Pro nalezení nejkratších cest mezi dvojicemi vrcholů
existují rychlé polynomiální algoritmy (např. Dijkstrův, Floydův-Warshallův apod.)

Dijkstrův algoritmus

Dijkstrův algoritmus je 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 (neohodnocený graf lze však na ohodnocený snadno převést). Pro grafy s hranami se záporným ohodnocením se obvykle používá pomalejší Bellmanův–Fordův algoritmus.

Zadání cvičení

• Prozkoumejte možnosti souřadnic dle standardu OCL
• Vyzkoušejte si vyhledání adresy dle What3Words
• Geokódujte adresy pomocí Google Awesome Tables (nutný účet u Google) a pomocí nástroje ke geokódování v ArcGIS Online
• Výsledky z obou nástrojů porovnejte v ArcGIS Pro
• V prostředí ArcGIS Online vyzkoušejte možnosti Network Analysis Services
• Na základě vaší vrstvy adres si vytvořte vlastní bodovou vrstvu, která bude obsahovat 5 zařízení (pro analýzy Closest Facility a Services Area)

Data

• V Excelu si vytvořte vlastní datovou sadu pro toto cvičení, list v Excelu bude obsahovat tyto sloupce s názvy: ID, Ulice, Cislo_popise, Nazev_obce.
• Vložte minimálně názvů 10 adres do tabulky (jelikož budeme používat ArcGIS Online rozmístěte adresy do vzdálenosti maximálně 30km od sebe).

Nástroje síťové analýzy v ArcGIS Online

1. Network Analysis Services:
   • ArcGIS Online poskytuje přístup k různým síťovým analýzám přes Network Analysis Services. Tyto služby umožňují provádět složité analýzy, jako je trasování cest, výpočet nejkratších tras, přiřazení oblastí, analýza přístupnosti a další.
2. Routing:
   • Directions: Tento nástroj umožňuje uživatelům plánovat trasy mezi různými body a získávat podrobné pokyny pro navigaci.
   • Closest Facility: Pomocí tohoto nástroje můžete najít nejbližší vybrané zařízení nebo bod podle zadaných kritérií.
3. Service Areas:
   • Tento nástroj umožňuje definovat a analyzovat oblasti služeb (service areas) kolem zvolených bodů. Je užitečný pro analýzu dostupnosti služeb nebo oblastí pokrytí.
4. Optimization:
   • Vehicle Routing Problem (VRP): Pomocí tohoto nástroje lze optimalizovat trasování vozidel, například při doručování zásilek, aby se minimalizovaly náklady a čas.
   • Location-Allocation: Tento nástroj umožňuje analyzovat a optimalizovat umístění zařízení, aby se maximalizovala pokrytí nebo minimalizovaly náklady na dopravu.

Postup v ArcGIS Online

• Přidejte si vlastní excelovskou tabulku do prostředí ArcGIS Online.
• Tabulku je nejdříve nutné geokódovat pomocí tlačítka Publish. V případě, že máte adresu rozdělenou do více sloupců je nutné zvolit možnost Location Information is in multiple fields.

• Vyberte správný sloupec pro geokódování, který obsahuje informace s názvem obce a nově vytvářenou vrstvu pojmenujte.

• Nalezenou shodu mezi adresními místy lze následně zkontrolovat. V případě, že došlo ke špatnému umístění adresního místa, můžete sami bod přesunout na správné místo.
• Vrstvu adresních bodů exportujte do shp a porovnejte s bodovou vrstvou získanou z Google Awesome Tables.
• Dostupné síťové analýzy pak naleznete v menu Analysis – Use Proximity. Vyzkoušejte si dostupné analýzy (Create Drive-time areas, Find nearest, Plan routes), změny v parametrech (auto, chodec, čas).