Efektivní hledání nejkratších cest v sítích hromadné přepravy osob
| Název práce v češtině: | Efektivní hledání nejkratších cest v sítích hromadné přepravy osob |
|---|---|
| Název v anglickém jazyce: | Efficient shortest path search in the public transportation networks |
| Akademický rok vypsání: | 2008/2009 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwarového inženýrství (32-KSI) |
| Vedoucí / školitel: | RNDr. Michal Žemlička, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 15.11.2008 |
| Datum zadání: | 15.11.2008 |
| Datum a čas obhajoby: | 24.05.2010 00:00 |
| Datum odevzdání elektronické podoby: | 24.05.2010 |
| Datum proběhlé obhajoby: | 24.05.2010 |
| Oponenti: | RNDr. Michal Kopecký, Ph.D. |
| Zásady pro vypracování |
| Vytvořte univerzální knihovnu pro efektivní vyhledávání nejkratších cest v sítích hromadné dopravy. Volba cest by měla být ovlivnitelná přídavnými parametry (použitelnost osobami se sníženou pohyblivostí apod.). Knihovna by měla být použitelná jak na běžných počítačích, tak i na přenosných zařízeních. |
| Seznam odborné literatury |
| 1. Jaroslav Pokorný, Michal Žemlička: Základy implementace souborů a databází 2. vydání, Praha, Karolinum 2004, ISBN 80-246-0837-5.
2. Stefano Pallottino, Maria Grazia Scutell?: Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. Technical report TR-97-06, Univerist? di Pisa, Dipartimento di Informatica, 1997. URL ftp://ftp.di.unipi.it/pub/techreports/TR-97-06.ps.Z 3. Žižka Ondřej: Vyhledávání v jízdních řádech. Brno, 2008, diplomová práce, FIT VUT v Brně. (http://ondra.zizka.cz/projekty/diplomka/DiplomovaPrace-OndrejZizka.pdf) |
| Předběžná náplň práce |
| Hledání nejkratší cesty je jeden z nejstudovanějších grafových problémů, má mnoho zajímavých aplikací v nejrůznějších odvětvích. Jedním z odvětví je hromadná přeprava osob, kde nás zajímá jak se v co nejkratším čase (a s ohledem na další kritéria) dostat z místa A do místa B. Přičemž délka cesty závisí na jízdních řádech spojů realizujících cestu.
Cílem této práce je najít efektivní algoritmus pro hledání nejkratší cesty v sítích hromadné dopravy a implementovat jej v knihovně, která bude použitelná i na přenosných zařízeních. V průběhu implementace budou prozkoumány možnosti předzpracování jízdních řádů a využití heuristik pro urychlení hledání cesty. |
| Předběžná náplň práce v anglickém jazyce |
| The search for the shortest path is one of the most studied graph problems with interesting applications in various fields. One such field is human mass transportation, where we want to know how to get from place A to place B in the shortest period of time. Whereas the path length depends on the time tables of the traffic relations, which implements the path.
Goal of this study is to find efficient algorithm for the shortest path search in human mass transportation network and implement it in the library, which will be also useable on portable devices. The possibilities of time tables preprocessing and use of heuristics on search acceleration will be explored during implementation. |