Řešený problém se dotýká oblasti městské hromadné dopravy. Aby lidé tuto službu v hojné míře využívali, je nutné jim poskytnout věrohodné informace. Jednou z nich je například odpověď na otázku: “kudy se dostanu z jednoho místa (zastávky) do druhého a jakých dopravních prostředků k tomu použít ”. Řešením je navržení vhodného datového modelu, který bude mimo algoritmů pro vyhledání trasy disponovat rovněž postupy pro správu a ukládání dat v souladu s tímto datovým modelem. Zpracování těchto úkolů bylo realizováno formou dvou diplomových prací.

Pracovní postup byl rozčleněn do několika dílčích úkolů. Nejprve bylo nutné zanalyzovat současnou situaci ve smyslu přístupu k řešení podobných problémů. Následovalo vytvoření datového modelu, na jehož základě došlo k návrhu příslušných algoritmů. Tyto byly převedeny do konkrétní podoby formou aplikací, vytvořených ve vhodném vývojovém prostředí. K otestování funkčnosti algoritmů posloužila práce s reálnými daty.

Datový model je tvořen základními prvky Zastavka a Linka, které si mimo dalších atributů nesou své jednoznačné identifikátory. Tyto prvky figurují ve vazeb-ních entitách Usek (spojuje dvě sousední zastávky a obsahuje čas potřebný k překonání vzdálenosti mezi nimi) a Linka_Zastavka (určuje příslušnost zastávek k jednotlivým linkám).

Nejvýznamnějším datovým zdrojem byla vrstva uliční a silniční sítě města Ostravy ve formátu systému ARC/INFO, na kterou byl datový model aplikován. Vrstva byla upravována pomocí podkladní rastrové katastrální mapy. Pro doplnění časových údajů entitě Usek bylo využito jízdního řádu ODIS. Lokalizace zastávek byla před převedením do digitální podoby značena do “papírové” mapy města Ostravy v měřítku 1:18000. Před samotným využitím těchto datových podkladů byla nutná jejich příprava. V této fázi autoři navázali na výsledky práce ze svého ročníkového projektu, v rámci něhož došlo k aktualizaci vrstvy ulic a doplnění kolejišť v místech jejich absence. Dále byla určena příslušnost liniových elementů z této vrstvy k jednotlivým linkám a došlo k samotnému vygenerování tras těchto linek v systému ARC/INFO. Výsledek byl převeden do formátu ESRI Shapefile, do něhož byly prostřednictvím bodové vrstvy rovněž ukládány nově lokalizované zastávky. Ukázalo se, že časová náročnost těchto úprav by výrazně převýšila rozsah časového intervalu pro zpracování samotných diplomových prací (pro představu: okolo 800 zpracovaných zastávek a přes 100 linek MHD).

S volbou formátu pro ukládání a práci s daty (ESRI Shapefile) byl spjat výběr nástrojů pro implementaci navržených algoritmů. Vybrán byl nakonec soubor komponent firmy ESRI – MapObjects 2.0 a vývojové prostředí pro jejich využití MS Visual Basic 5.0.

V oblasti správy a údržby liniových dat v dnešní době výrazně vyniká systém ARC/INFO. Datovým modelem, který je pro tuto oblast mj. využíván je tzv. route systém. Laicky řečeno umožňuje připojit společné atributy libovolné skupině liniových prvků bez nutnosti modifikace podkladních dat. Práce s daty je zde realizována na dvou úrovních. Jednou z nich je komunikace s uživatelem prostřednictvím zadávání jednotlivých příkazů systému. Druhým pak využití grafického prostředí nabídek, vytvořeného v jazyce AML. Možnost tvorby aplikace v tomto prostředí byla zavržena z důvodu zbytečně komplikovaného datového modelu. Takto vytvořený produkt by navíc byl nutnou součástí celého systému ARC/INFO.

Výsledná aplikace pro správu a údržbu liniových dat pracuje ve dvou režimech – jako nástroj pro správu a modifikaci tématické datové sady, či jako prohlížečka libovolných dat formátu ESRI Shapefile (zde jsou speciální funkce nepřístupné). Pro uživatele pracující s linkami MHD je k dispozici schéma, které umožňuje nastavit natrvalo konkrétní datové vrstvy, jež se po každém spuštění automaticky připojí (uživatel má rovněž možnost volit některé atributy vrstev). Hlavní okno aplikace je rozděleno do několika logických částí: panel tlačítek pro základní operace s vrstvami, tlačítka speciálních funkcí, manažer vrstev (legenda), lišta ve spodní části okna, na níž se zobrazuje uživateli nápověda k právě prováděné činnosti a samozřejmě hlavní část – mapové okno. Mezi základní funkce, kterými aplikace disponuje patří připojení / odstranění vrstvy, přesun vrstvy nad ostatní, přiblížení / oddálení v mapě (zoom in / out), posun v rámci vrstvy (pan) atd. Přítomna je rovněž funkce grafického výběru geoprvků (volitelné dva režimy) na niž navazuje možnost vygenerování tabulky atributů právě vybraných prvků. Mezi speciální funkce pro manipulaci s tématickými daty MHD patří možnost vložení nové linky, odstranění stávající linky popř. modifikace průběhu již existující linky. Uživatel se při editaci ocitá v režimu, kdy lze využívat většinu standardních nástrojů pro manipulaci s daty a při ukončení práce se může rozhodnout, zda výsledek operace uložit, či změny stornovat. Samozřejmostí je přítomnost tlačítek realizujících výběr linek či zastávek na základě dotazu. Dalším z charakteristických rysů aplikace je možnost transformace polohy zastávek z původní lokalizace (“v terénu”) do podoby využitelné algoritmem pro nalezení trasy. Aplikace je rovněž vybavena nástrojem pro dynamické generování popisků pro prvky v mapě. Jakmile se uživatel kurzorem přiblíží k objektu z právě aktivní vrstvy, obdrží informaci o jeho identifikaci. Závěrem lze o produktu zmínit, že nevyžaduje od uživatele hlubší znalosti programových produktů v oblasti GIS (odpadají náklady na zaškolování personálu), má nepatrné nároky na diskovou paměť počítače (cca 250 kB) a neopomenutelnou výhodou jsou rovněž relativně nízké pořizovací náklady.

V oblasti služeb pro vyhledávání spojení v dopravní síti existuje v dnešní době celá řada produktů. Mnohé jsou uživateli dostupné prostřednictvím sítě Internet (např. aplikace DPMO pro vyhledání spojení v síti MHD). Většina z nich využívá algoritmů “prohledávání do hloubky” či “prohledávání do šířky”. Při prohledávání do hloubky dochází k postupnému procházení všech hran sítě a to tak dlouho, pokud není nalezen cílový uzel, či pokud nejsou otestovány všechny hrany. V případě prohledávání do šířky se algoritmus vydá ze startovního uzlu a postupuje do jeho sousedů, poté do sousedů těchto sousedů atd. Po nalezení cílového uzlu je výsledkem trasa s přívlastkem nejkratší.

Rysy vyvíjeného algoritmu jsou: vyhledání spojení, zohlednění časových intervalů mezi sousedními zastávkami, nezávislost na jízdním řádu a výsledná grafická prezentace výsledků. Celý algoritmus se skládá ze třech na sebe navazujících částí:

• vyhledání zastávek mezi počáteční a koncovou - zde je uplatněna metoda prohledávání do šířky (výsledkem je vygenerovaný seznam zastávek, kterými cestující projede)
• vyhledání linek, které cestující použije - algoritmus testuje propojení zastávek v seznamu (viz. výsledek minulého kroku) jednotlivými linkami a vybírá vždy tu linku, prostřednictvím které se dostane v rámci vybraných zastávek “nejdále”
• vykreslení výsledné trasy – zvýrazní ty liniové prvky vrstvy ulice, které leží na trase mezi počáteční a koncovou zastávkou

Na základě výše popsaného algoritmu vznikla aplikace, která byla testována při práci s reálnými daty. Hlavní okno aplikace pro vyhledání spojení v síti linek MHD sestává z části obsahující prvky pro výběr počáteční a koncové zastávky ze seznamu, a ve které se po nalezení trasy objeví doprovodné informace. V horní části hlavního formuláře jsou umístěny nástroje pro základní operace s připojenými vrstvami a největší část pracovní oblasti pokrývá výřez mapového okna. Samotný výběr počáteční a koncové zastávky probíhá prostřednictvím zmíněného seznamu, či grafickým výběrem přímo v mapovém okně. Jména zastávek v mapovém okně se objevují interaktivně po umístění kurzoru nad daný prvek. Po spuštění samotného vyhledání trasy jsou průchozí i přestupové zastávky v mapovém okně zvýrazněny příslušnou barvou a v levé části určené pro informace má uživatel možnost seznámit se s výpisem všech projížděných zastávek a rovněž s textovou informací, kterou linku použít a ve které zastávce přestoupit na jiný spoj. Nakonec dojde k vykreslení průběhu trasy v mapovém okně v jednom ze dvou režimů. Detailní vykreslení je časově poměrně náročné, proto má uživatel možnost zvolit vykreslení schématické, které je pouze přímým propojením jednotlivých zastávek (schématické vykreslení je z informativního hlediska zcela postačující).

Nalezená trasa je kompromisem mezi nejkratší trasou a trasou s nejmenším počtem přestupů. Negativním jevem je relativně velká časová náročnost vyhledávání, která je daní za využití “uživatelsky přítulného” vývojového prostředí.