Vyhodnocení zvolené trasy mobilního telefonu při známém cíli cesty

Petr Lukeš

ABSTRAKT

Tato bakalářská práce se zabývá problémem lokalizace uživatele pomocí mobilního telefonu a způsoby vyhodnocení trasy jeho pohybu. V první části je uvedena stručná historie sítí GSM, jejich architektura a technologické principy lokalizace uživatele pomocí sítě GSM. Další kapitola se zabývá lokalizací pomocí sítě GSM v praxi, zejména však dostupnými mapovými podklady, způsoby lokalizace uživatele a vyhodnocení jeho trasy při známém cíli cesty, včetně použití algoritmů pro hledání optimálních tras.

Klíčová slova: GSM, základnová stanice BTS, lokalizace, algoritmus

ABSTRACT

This bachelor work deals with problem of user localisation through mobile telephone and way how to evaluate route of his movement. In the firts part is mentioned brief history of GSM networks, their architecture and technological principes of user localisation through GSM netwtork. Next chapter deals with localisation through GSM network in practice, however mainly of available mapsets, methods of user localisation and evalution of his route with known target, including usage of algoithms for finding optimal route.

Keywords: GSM, base transfer station BTS, localisation, algorithm

Úvod

V součastné době se stále více dostávají do popředí zájmu odborníků i běžných uživatelů technologie pro určení aktuální polohy uživatele v terénu. Pokud máme k dispozici tuto informaci, jsme z ní schopni vyvodit kvalitativně zcela nový druh informací. Pro určení polohy uživatele můžeme použít tři technologicky zcela odlišné metody, přičemž každá z nich má své klady a zápory:

samostatný navigační přístroj GPS – výhodou tohoto řešení je velmi přesné určení polohy uživatele a minimální provozní náklady – určení polohy je zdarma. Nevýhodami jsou stále zatím poměrně velké počáteční náklady na pořízení přístroje GPS, jednoúčelovost, nízká škála poskytnutých doplňkových služeb
klient používající běžný MT sítě GSM – výhodou tohoto řešení jsou minimální vstupní náklady, multifunkčnost přístroje a široké spektrum doplňkových služeb (tyto služby se také někdy nazývají jako Location based services – služby založené na znalosti lokace). Největší nevýhodou určení polohy pomocí mobilního telefonu sítě GSM je přesnost určení polohy uživatele, která je řádově nižší při srovnání s navigačním přístrojem GPS. Další nevýhodou je to, že každé zjištění aktuální polohy je zpoplatněno finanční částkou podle tarifu jednotlivých operátorů.
kombinace navigačního přístroje GPS, který slouží ke zjištění polohy uživatele a mobilního telefonu sloužícího k přenosu informace o poloze klienta do logistické centrály, která je schopna klientovi na základě znalosti jeho aktuální polohy mu poskytnout některé doplňkové služby.

V mé bakalářské práci se zabývám principem lokalizace klienta pomocí mobilního telefonu GSM, její praktické nasazení, úskalími s tím souvisejícími. Podle mého názoru se jedná o zajímavou alternativu ke známému principu lokalizace pomocí navigačního přístroje GPS. V součastné době mají na tyto služby víceméně monopol provozovatelé jednotlivých mobilních sítí, neboť pouze oni mají k dispozici údaje o přesné poloze svých základnových stanic BTS, které jsou k úspěšné lokalizaci klienta pomocí mobilního telefonu GSM nezbytné. Vhledem k této situaci není určování polohy klienta pomocí mobilního telefonu sítě GSM příliš rozšířeno. Právě proto jsem se také snažil v mé bakalářské práci najít odpověď na otázku, za by nebylo možné tento stav změnit a polohu základnových stanic zjistit jakýmkoliv alternativním způsobem. Mým posledním úkolem bakalářské práce bylo nalézt způsob vyhodnocení trasy klienta při známém cíli cesty, pokud máme k dispozici určitý soubor jeho možných poloh v silniční síti v čase. Rád bych se také zmínil o diplomové práci studenta Aleše Daňka, který pracuje na druhé části tohoto projektu a snaží se vyvinout aplikaci pro MT ,která by byla schopna určit některé klíčové údaje o poloze klienta v síti GSM a odeslat je do logistické centrály.

Technologický princip lokalizace mobilního telefonu sítě GSM

Pro účel lokalizace mobilního telefonu můžeme z výše popisované struktury sítě GSM vymezit tyto dva nejpodstatnější technické prvky - základnová stanice (BTS) a MT. K určení polohy mobilní stanice lze použít různých metod měření resp. jejich kombinací.Při zjištění polohy můžeme vycházet z těchto informací:

- operátor přirozeně ví, kde přesně se nachází jeho základnové stanice BTS

- ví také, s jakou základnovou stanicí (BTS) resp. s jakým jejím sektorem komunikuje MT

- ví, v jaké vzdálenosti od této stanice se mobil nachází (zná hodnotu TA)

Lokalizace podle BTS

Nejhrubší metoda je lokalizace podle BTS komunikující s mobilem. Potíž tohoto způsobu je v tom, že umožňuje určit pouze okruh (o teoretickém průměru 35 km) resp. výseč tohoto kruhu u vícesektorových BTS. Vzhledem k hustotě buněk lze sice s vysokou pravděpodobností předpokládat, že MT se nachází blíže, než oněch 35 km, ale i tak touto metodou nelze získat více, než např. víceméně spolehlivý odhad, v jakém okrese se volající nachází. V okrajových oblastech pochopitelně bude docházet k přesahům do sousedních okresů, ale z hlediska počtu volání nepůjde o příliš významný počet chyb (nicméně je s nimi potřeba počítat a např. v příhraničních oblastech při komunikaci přes státní hranici může jít o závažný problém). Pokud volající nevolá zrovna z extrémně řídce osídlené oblasti, lze při dnešní hustotě BTS předpokládat pravděpodobnou polohu volajícího v okruhu do 10 km od BTS, ve větších městech v okruhu stovek metrů či nejvýše jednotek kilometrů. Nejhorší situace nastane, pokud MT komunikuje s některou z "vykrývacích" buněk umístěných na vysokých kopcích - zde je skutečně reálná komunikace až do maximální vzdálenosti 35 km. Naopak zpravidla dostatečně přesná je tato lokalizace v případě tzv. "mikrocell", nízkovýkonných základnových stanic BTS, vykrývajících např. supermarkety, stanice metra, stadiony apod., i když i zde může být výjimečně přesah dosahu v řádu desítek až stovek metrů mimo daný objekt.

Lokalizace podle BTS a TA

Určení polohy lze významně zlepšit, pokud vedle příslušnosti k BTS zjistíme i hodnotu TA, která vypovídá o vzdálenosti, na níž mobil se základnovou stanicí BTS komunikuje. Z plochy ohraničené kruhem resp. z výseče tohoto území již získáme pouze mezikruží o šířce asi 1 km, které již - zejména v řidčeji osídlených oblastech - může ve spojení s další informací (např. poloha na dálnici, u rybníka atd.) vést k poměrně přesné lokalizaci mobilního telefonu.

Sektory jsou označeny rozdílnými barvami, jejich hranice ovšem nejsou zcela ostré. Přesnější lokalizace můžeme dosáhnout, pokud známe ještě další informaci. Např. víme-li, že volající z obrázku se nachází na dálnici, v případě jednosektorové BTS (vlevo) může být v úseku dálnice A, nebo B (viz obr.), v případě dvousektorové BTS (uprostřed) resp. třísektorové (vpravo) je již určení polohy relativně velmi přesné a zahrnuje asi 1 km dlouhý úsek dálnice (označeno B).Pro představu o hrubosti měření TA ještě připojuji obrázek, dovolující udělat si představu o velikosti území ohraničeného nejmenší lokalizovatelnou kružnicí o průměru 550 metrů (TA=0). BTS umístěná na horním okraji Václavského náměstí může obsluhovat MT nejen na celém Václavském náměstí, ale i např. na Hlavním nádraží, v Jindřišské, Vodičkově, náměstí I.P. Pavlova nebo náměstí Míru. Vzhledem k hustotě BTS v dané oblasti to sice nebude časté, ale není to technicky nemožné.

Lokalizace triangulací z více BTS

Triangulace z více BTS je obecně asi nejpřesnější metoda, jak zjistit polohu MT v síti GSM. Spočívá v zaměření polohy MT z několika BTS, pokud možno i se změřením TA. Technicky již ale jde o poměrně složité řešení, vyžadující jednak určitý čas, a jednak buď spolupráci SIM karty mobilu, nebo přímo mobilního telefonu. V takovém případě ovšem musí mobil obsahovat speciální čip. Systém na tomto základě začíná být uváděn do provozu v některých místech USA pod názvem Enhanced Observed Time Difference (E-OTD).

Lokalizace pomocí sítě GSM v praxi

Mapové podklady pro lokalizaci pomocí mobilního telefonu

Pro praktické využití lokalizace automobilu pomocí mobilního telefonu je (jako v každém GIS projektu obecně) klíčovým a limitujícím faktorem dostupnost kvalitních datových sad. Pro určení polohy automobilu za pomocí údajů o identifikátoru BTS stanice a časovém předstihu signálu (Timing advance) musíme mít k dispozici nutně minimálně tyto dvě mapové vrstvy

Vektorovou liniovou vrstvu silniční sítě ČR (resp. státu, ve kterém chceme provést zaměření polohy automobilu)
Vektorovou bodovou vrstvu stanic BTS

Získání vektorových liniových dat silniční sítě ČR nečiní v součastné době žádné problémy. Můžeme se obrátit na některou ze soukromých společností poskytující digitální data České republiky a tyto data silniční sítě zakoupit, případně využít zdarma služeb tzv. „Silniční databanky“, kterou provozuje Ministerstvo Dopravy České republiky (internetová adresa http://www.rsd.cz). Těchto dat jsem využil i já při tvorbě bakalářské práce, proto bych je na tomto místě rád blíže představil.

Mapové podklady základnových stanic BTS

Mapové podklady mobilních operátorů

Zatímco získání kvalitních mapových podkladů silniční sítě České republiky nečiní v praxi žádné problémy, situace s mapovými podklady základnových stanic BTS je zcela jiná. Tento stav je dán specifickým postavením základnových stanic BTS jako součásti sítě mobilního operátora. V České republice působní na trhu tři mobilní operátoři (Eurotel Praha spol s.r.o, T-mobile Czech Republic a.s, Oskar Mobil a.s), přičemž každý provozuje vlastní mobilní síť se svými základnovými stanicemi BTS. Tito mobilní operátoři samozřejmě mají pro své vnitřní účely k dispozici mapové podklady základnových stanic BTS, jejich získání touto cestou bych však neviděl příliš reálně. Pokoušel jsem se kontaktovat mobilní operátory kvůli získání těchto mapových podkladů, bohužel mi však shodně poslali zamítavou reakci. Nevylučuji ovšem, že pokud by mobilního operátora oslovila firma, mohla by mapové podklady základnových stanic BTS získat (za jistě nemalou finanční částku).

Mapové podklady získané jinou cestou

Druhou možností, jak získat mapové podklady základnových stanic BTS jsou textové seznamy BTS volně dostupné na internetu. Tyto seznamy vytvářejí dobrovolníci a fanoušci technologie GSM. Při určení polohy základnové stanice BTS se využívá víceméně obráceného postupu, než při lokalizaci mobilního telefonu. Každá základnová stanice BTS má svůj jedinečný identifikátor – tzv. Cell ID (identifikátor buňky). Při určení její polohy sledujeme hodnotu timing advance (časový předstih), která udává vzdálenost k základnové stanici BTS. Tímto způsobem byly identifikovány a lokalizovány všechny základnové stanice BTS na našem území.Pro další využití textových seznamů je nutno ručně digitalizovat polohu každé základnové stanice BTS jako bodovou vektorovou vrstvu. Digitalizace bude probíhat třemi různými metodami, a to podle způsobu určení polohy základnové stanice:

poloha základnové stanice BTS je určena přesnými zeměpisnými souřadnicemi pomocí přístroje GPS – zde můžeme provézt zcela automatizovaný vklad bodové vrstvy BTS pomocí libovolného GIS software, který obsahuje tuto funkci
poloha základnové stanice BTS je určena geokódem (např. poštovní adresa) s dostatečnou rozlišovací schopností – zde můžeme provést tzv. geokódování, při kterém se prvku přiřadí poloha na základě textového atributu udávající polohu
poloha základnové stanice BTS je určena geokódem (např. „stožár v poli“) s nedostatečnou rozlišovací schopností – zde je nutno provést upřesnění polohy
1. analýzou stávajících mapových podkladů – pokud je poloha základnové stanice určena např. textovým popisem „Poruba, Slavíkova x 17. Listopadu“
2. šetřením v terénu – pokud je poloha základnové stanice určena např. textovým popisem „Veveří, Úvoz 118 (vysoký dům 100m od Veveří)“Analýza kvality určení polohy základnových stanic BTS

Pro kompletní představu o využitelnosti seznamů základnových stanic BTS, které jsou volně ke stažení na internetu jsem provedl analýzu kvality určení polohy základnových stanic. Jelikož se jedná o časově poměrně náročný úkol, rozhodl jsem se provést tuto analýzu pouze pro mobilního operátora Oskar. Předpokládám, že pro zbylé dva mobilní operátory (Eurotel, T-Mobile) bude situace obdobná. Jak jsem již uvedl výše, seznamy základnových stanic BTS se vyskytují ve formátu XLS – Microsoft Excel, proto jsem i samotnou analýzu provedl v tomto kancelářském programu. Nejprve bylo potřeba se zbavit všech duplicitních záznamů – každá základnová stanice se zde vyskytovala minimálně ve dvou exemplářích se shodou polohou, lišící se pouze v údaji Cell ID (jedinečném identifikátoru každého z výseku antén základnové stanice). Poté jsem ručně procházel každou základnovou stanici a sledoval, jakým způsobem je uvedena její poloha. Na základě způsobu určení polohy jsem poté každé základové stanici přiřadil jeden z identifikátorů – G (poloha určena pomocí přístroje GPS), D (dostatečné určení polohy geokódem), N (nedostatečné určení polohy geokódem, nutné šetření v mapách) a S (nutné místní šetření). Po provedení šetření u všech základnových stanic jsem dospěl výsledkům, které zobrazuje tabulka č.1.

Způsob určení polohy základových stanic	Počty základových stanic
Dostatečné určení polohy geokódem	1136
Nutné upřesnění pomocí map	924
Nutné šetření v terénu	718
GPS	220

Celkem	2998

tabulka 1 - počty základnových stanic BTS podle kvality určení polohy

Výsečový graf znázorňující procentuální poměr jednotlivých způsobů určení polohy základnových stanic zachycuje obrázek č.1.

obrázek 1 - kvalita určení polohy BTS stanic sítě Oskar

Vyhodnocení zvolené trasy při známém cíli cesty

Sledování polohy uživatele mobilního telefonu GSM není nepřetržité, ale probíhá v určitých časových úsecích. Tato situace je způsobena hlavně těmito dvěma důvody:

časovou prodlevou nutnou pro zjištění údajů o dostupných základnových stanicích BTS.
způsobem komunikace uživatele mobilního telefonu s řídícím střediskem – nejvíce se využívají krátké textové zprávy SMS, případně datové přenosy GPRS. V obou případech vznikají při přenosu dat o poloze uživatele finanční náklady

Proto je třeba vhodně zvolit interval určení polohy uživatele. Ve scénáři, který rozvádím níže jsem na fiktivní trase Ostrava – Praha určil polohu klienta celkem 10x. V reálu může být tento interval samozřejmě větší, či menší.

Cílovým stavem, kterého chceme dosáhnout je mít k dispozici záznam o pohybu uživatele ve formě vektorové liniové vrstvy, která by odrážela reálný pohyb uživatele. K tomu použijeme nástrojů teorie grafů a síťové analýzy, konkrétně Dijkstrův algoritmus pro výpočet nejkratší cesty v grafu. Nejprve je ovšem potřeba data pro tyto analýzy připravit.

Příprava dat pro síťové analýzy

Pro to, abychom mohli provést vyhodnocení trasy uživatele mobilního telefonu musíme nejprve data, které máme k dispozici patřičným způsobem upravit pro jejich další použití. Tento postup můžeme rozdělit do dvou částí:

úprava atributových dat vrstvy silniční sítě
konverze a výběr dat o poloze uživatele

ad 1. Úprava atributových dat vrstvy silniční sítě

Jelikož vyhodnocení trasy pohybu uživatele mobilního telefonu budeme provádět pomocí nástrojů síťové analýzy, je třeba data silniční sítě nejprve na tuto analýzu připravit. Pro výpočet síťové analýzy jsem použil nástroje Network Analyst, který je extenzí programu ArcView GIS 3.2 společnosti ESRI. Network analyst je schopen provádět síťové analýzy těmito dvěma algoritmy:

nalezení nejkratší trasy mezi zadanými body
nalezení nejrychlejší trasy mezi zadanými body

Extenze Network analyst má i další funkce (např. nalezení optimálního pořadí průjezdu, nalezení nejbližšího objektu atd), které ovšem nevyužijeme. S daty silniční sítě, které máme k dispozici jsme schopni bez jakýchkoliv úprav provést pouze algoritmus nalezení nejkratší trasy mezi zadanými body (tento algoritmus využívá údaje o délce linie, která je standardní součástí všech vektorových liniových dat). Vyhledání nejkratší trasy je však ve většině případů zavádějící a neodpovídá realitě – trasa často vede po komunikacích II a III.třídy, po kterých sice vychází výpočty vzdálenosti nejlépe, ale v reálném provozu je daleko výhodnější zvolit trasu delší, ale po kvalitnějších komunikacích (dálnice a komunikace I.třídy) u kterých předpokládáme kratší čas průjezdu. Proto by mělo být našim cílem přidat popisné části dat vrstvy silniční sítě atribut, který by vyjadřoval průměrný čas průjezdu jednotlivými úseky silniční sítě s ohledem na třídu komunikace. Toho docílíme poměrně jednoduše, když si určíme průměrnou rychlost pohybu po jednotlivých typech komunikací.

Typ komunikace	Rychlost (km/h)	Rychlost (m/s)
Dálnice	100	27,77
Komunikace I.třídy	70	19,44
Komunikace II.třídy	50	13,88
Komunikace III.třídy	40	11,11

tabulka 2 - volba rychlostí průjezdu jednotlivými typy komunikací

Pro popisné data vrstvy silniční sítě jsem vytvořil nový atribut „Rych_m_s“, který udává průměrnou rychlost průjezdu daným úsekem v metrech za sekundu. Tento atribut jsem vyplnil podle hodnot, které jsou uvedeny v tabulce č.8

Atributem, kterého využijeme pro analýzu nejrychlejší trasy pohybu uživatele je atribut „Doba_pr“. Ten nám udává čas průjezdu (v sekundách) daným úsekem v závislosti na typu komunikace. Získáme jej jednoduše za pomocí fyzikálního vzorce , kde s (dráha) je délka úseku a v (rychlost) je v předchozím kroku vytvořený atribut „Rych_m_s“. Pro naplnění atributu „Doba_pr“ jsem využil funkce „Field calculator“ programu ArcView GIS 3.2.

Na konci úpravy dat silniční sítě pro sítové analýzy je ještě třeba přiřadit atributu „Doba_pr“ zástupné jméno (alias) SECONDS, které extenze Network analyst standardně hledá v popisné části zkoumaných dat.

ad 2 - Konverze a výběr dat o poloze uživatele

Algoritmus znázorňující celý proces konverze dat pro síťovou analýzu je zobrazen na obrázku č.2.

Obrázek 2 - algoritmus přípravy dat pro síťové analýzy

Jako první krok musíme provést konverzi vektorových liniových dat o možné poloze uživatele na data vektorové bodové. Toto je nutno provést s ohledem na další využití těchto dat jako vstupních prvků síťové analýzy. Pro provedení této konverze jsem použil nástroje „Feature to point“ softwarového balíku ArcGIS 9.0 (konkrétně se jedná o konverzní funkci programu ArcToolbox).

Výsledkem operace je sada nových vektorových bodových dat, kde každý z bodů leží ve středu původního liniového úseku silniční sítě. Podle přesnosti určení polohy uživatele nám tedy vznikl shluk bodových dat reprezentující některou z možných poloh uživatele v silniční síti. Tyto data již není problém použít jako uzly, které reprezentují průjezd daným místem. Zde ovšem nastává problém s tím, že pro dané místo je možných poloh sítě příliš mnoho, což by způsobovalo při následné síťové analýze zavádějící výsledky. Algoritmus by se snažil nesmyslně určit průjezd všemi body, včetně těch, které jsou v reálu zcela irelevantní (komunikace nižších tříd by při vyhodnocení měla stejnou váhu jako dálnice apod.). Tento problém jsem vyřešil tím, že jsem provedl selekci v každém se shluků bodů reprezentující možnou polohu uživatele a v každém shluku vybral pouze bod reprezentující nejkvalitnější komunikaci, která je nejdelší (v daném úseku). Tento výběr by měl nejvíce odpovídat realitě, ve speciálních případech ovšem není problém algoritmus výběru modifikovat pro danou konkrétní situaci (např. pokud víme, že uživatel se nemůže pohybovat po dálnici,můžeme typ komunikace „dálnice“ zcela vyřadit z výběru).

Tímto způsobem jsem vypočítal pravděpodobnou trasu pohybu uživatele mobilního telefonu silniční sítí z kusých údajů o poloze, které jsme měli k dispozici na počátku. Byl zvolen algoritmus pro výpočet nejrychlejší trasy.

Při porovnání výsledků, kterých dosahují oba algoritmy jsem došel k těmto závěrům: na první pohled produkují oba algoritmy při větším počtu průjezdových uzlů (v mém případě deset uzlů, ale záleží samozřejmě na délce trasy) velice podobné výsledky. Při bližším pohledu si na některých místech můžeme všimnout odlišností mezi výstupy obou algoritmů. Algoritmus vypočítávající nejkratší trasu je podle mého názoru méně vhodný pro praktické využití, neboť vůbec nebere v potaz typ komunikace a často se stává, že volí domnělou trasu pohybu uživatele mobilního telefonu po komunikacích druhé a třetí třídy. Naopak algoritmus operující s časem průjezdu daným úsekem komunikace podle mého názoru produkuje reprezentativní výsledky o pohybu uživatele mobilního telefonu silniční sítí.

Obrázek 3 – nalezená optimální trasa

Závěr

Určení polohy klienta pomocí mobilního telefonu sítě GSM je zajímavou alternativou k stávajícímu hojně využívanému způsobu pomocí navigátoru GPS. Mezi jeho největší klady patří zajisté nízké počáteční náklady, které mohou vést v případě masivnějšího nasazení (kupříkladu ve větší dopravní firmě) k významným finančním úsporám. Další výhodou může být rovněž jednoduchost obsluhy takového zařízení (laický uživatel bude obsluhovat MT, který důvěrně zná). Největší nevýhodou tohoto způsobu určování polohy je její možná nízká přesnost (v odlehlejších částech republiky s nízkou hustotou základnových stanic BTS), která se v extrémních případech může pohybovat v řádech kilometrů. Naopak v centrech velkých měst se přesnost určení polohy může blížit desítkám metrů, což je například pro sledování služebních vozidel dopravní firmou zcela dostačující hodnota. Další nevýhodou je provázanost na mobilního operátora, který je z technologického hlediska jako jediný schopen provést určení polohy klienta. Vzhledem k tomuto faktickému monopolu jsou ceny za určení polohy relativně vysoké. Jistým možný řešením této situace by bylo vytvoření mapy základnových stanic BTS nezávislé na mobilním operátoru. Jednu z možností její tvorby, kterou jsem nastínil je využití na internetu běžně dostupných textových seznamů základnových stanic BTS a jejich strojové zpracování. Jak ovšem vyplynulo z mé analýzy kvality určení polohy základnových stanic v těchto seznamech, přibližně 24% procent základnových stanic BTS není bohužel lokalizováno s nutnou přesností, což sebou přináší zvýšené náklady na jejich terénní rekognoskaci. V případě zvažované tvorby mapových podkladů základnových stanic BTS by se tato skutečnost musela brát v potaz. Dobrovolné poskytnutí svých mapových podkladů mobilními operátory nepovažuji za reálné. Při určování trasy pohybu klienta silniční sítí máme jako údaje o poloze k dispozici určitý soubor jednotlivých úseků komunikací, po kterých se klient mohl v daném čase, kdy byla zjišťována jeho poloha pohybovat. Pokud si chceme vytvořit reprezentativní představu o kontinuálním pohybu klienta silniční sítí musíme použít nástrojů síťové analýzy. Tyto nástroje většinou fungují na principu Disktrova algoritmu pro výpočet trasy s nejnižším cenovým ohodnocením (tímto ohodnocením může být např. délka trvání průjezdu komunikace, nebo délka komunikace). Vznikají nám tedy dva algoritmy – výpočet nejrychlejší možné trasy a nejkratší možné trasy, které každý vykazují odlišné výsledky, přičemž realitě se více blíží spíše algoritmus pro výpočet nejrychlejší trasy.

Použité zdroje