Tato práce formalizuje problém vyhledávání spojení ve veřejné dopravě a dále diskutuje používané grafové i negrafové algoritmy a modely. V potaz je
brána použitelnost navrhovaného řešení v mobilních zařízeních, která vyhledávají spojení offline. Tato zařízení nemají stálý přístup k výkonnému
serveru, který by vyhledávání provedl. Z toho důvodu musí být data jízdních řádů uchovávána v kompaktní podobě a zvolený model musí počítat s omezeným
výkonem. Tato práce uvažuje možnosti využití paralelismu při vyhledávání spojení a za tímto účelem navrhuje heuristiku pro odhad optimálních časů
odjezdů, která umožní paralelizaci vyhledávání několika spojení současně. Tato heuristika byla otestována nad časově závislým grafem.
Anotace v angličtině
This thesis formalizes the problem of connection search in public transport and further discuses available graph and non-graph based algorithms and
models. The usability of the proposed solution on mobile devices, that perform the connection search offline, is taken into account. These devices do
not have permanent access to powerful server that could perform the search. For this reason, timetable data must be stored in a compact form and
chosen model must take into account limited performance. This thesis considers the possibility of using parallelism in connection search and for this
purpose proposes a heuristic for estimating optimal departure times, which will allow parallelization of searching several connections simultaneously.
This heuristic has been tested on time-dependent graph.
Public transport, timetable, connection search, parallelism, heuristic
Rozsah průvodní práce
55
Jazyk
CZ
Anotace
Tato práce formalizuje problém vyhledávání spojení ve veřejné dopravě a dále diskutuje používané grafové i negrafové algoritmy a modely. V potaz je
brána použitelnost navrhovaného řešení v mobilních zařízeních, která vyhledávají spojení offline. Tato zařízení nemají stálý přístup k výkonnému
serveru, který by vyhledávání provedl. Z toho důvodu musí být data jízdních řádů uchovávána v kompaktní podobě a zvolený model musí počítat s omezeným
výkonem. Tato práce uvažuje možnosti využití paralelismu při vyhledávání spojení a za tímto účelem navrhuje heuristiku pro odhad optimálních časů
odjezdů, která umožní paralelizaci vyhledávání několika spojení současně. Tato heuristika byla otestována nad časově závislým grafem.
Anotace v angličtině
This thesis formalizes the problem of connection search in public transport and further discuses available graph and non-graph based algorithms and
models. The usability of the proposed solution on mobile devices, that perform the connection search offline, is taken into account. These devices do
not have permanent access to powerful server that could perform the search. For this reason, timetable data must be stored in a compact form and
chosen model must take into account limited performance. This thesis considers the possibility of using parallelism in connection search and for this
purpose proposes a heuristic for estimating optimal departure times, which will allow parallelization of searching several connections simultaneously.
This heuristic has been tested on time-dependent graph.
Public transport, timetable, connection search, parallelism, heuristic
Zásady pro vypracování
Proveďte analýzu výkonu aplikace vytvořené v rámci vaší bakalářské práce a identifikujte kritická místa.
Navrhněte možná zlepšení - optimalizace datových struktur, paralelizace vyhledávání za použití více jader procesoru, případně jiné.
Navržená zlepšení implementujte do aplikace, a to s důrazem na minimalizaci množství ukládaných dat.
Otestujte takto zlepšenou aplikaci na reálných datech, výsledky testu vyhodnoťte a analyzujte.
Zásady pro vypracování
Proveďte analýzu výkonu aplikace vytvořené v rámci vaší bakalářské práce a identifikujte kritická místa.
Navrhněte možná zlepšení - optimalizace datových struktur, paralelizace vyhledávání za použití více jader procesoru, případně jiné.
Navržená zlepšení implementujte do aplikace, a to s důrazem na minimalizaci množství ukládaných dat.
Otestujte takto zlepšenou aplikaci na reálných datech, výsledky testu vyhodnoťte a analyzujte.
Seznam doporučené literatury
\renewcommand{\labelenumi}{[\theenumi]}
DEO, Narsingh. Graph theory with applications to engineering and computer science. Dover edition. Mineola, New York: Dover Publications, 2016. ISBN 978-0486807935.
BAST, Hannah, CARLSSON, Erik, EIGENWILLIG, Arno, GEISBERGER, Robert, HARRELSON, Chris, RAYCHEV, Veselin, and VIGER, Fabien. Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In Mark de Berg and Ulrich Meyer, editors, ESA, volume 6346 of Lecture Notes in Computer Science, pages 290?301, Springer, 2010. ISBN 978-3-642-15775-2.
KŘEPELKA, Michal. Offline vyhledávání spojů na platformě Android. Bakalářská práce, UJEP, 2017.
Seznam doporučené literatury
\renewcommand{\labelenumi}{[\theenumi]}
DEO, Narsingh. Graph theory with applications to engineering and computer science. Dover edition. Mineola, New York: Dover Publications, 2016. ISBN 978-0486807935.
BAST, Hannah, CARLSSON, Erik, EIGENWILLIG, Arno, GEISBERGER, Robert, HARRELSON, Chris, RAYCHEV, Veselin, and VIGER, Fabien. Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. In Mark de Berg and Ulrich Meyer, editors, ESA, volume 6346 of Lecture Notes in Computer Science, pages 290?301, Springer, 2010. ISBN 978-3-642-15775-2.
KŘEPELKA, Michal. Offline vyhledávání spojů na platformě Android. Bakalářská práce, UJEP, 2017.
Přílohy volně vložené
1 DVD
Přílohy vázané v práci
-
Převzato z knihovny
Ano
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Průběh obhajoby je zveřejněn pouze přihlášenému uživateli.