Efektivní hledání nejkratších cest v sítích hromadné přepravy osob
| Thesis title in Czech: | Efektivní hledání nejkratších cest v sítích hromadné přepravy osob |
|---|---|
| Thesis title in English: | Efficient shortest path search in the public transportation networks |
| Academic year of topic announcement: | 2008/2009 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Software Engineering (32-KSI) |
| Supervisor: | RNDr. Michal Žemlička, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 15.11.2008 |
| Date of assignment: | 15.11.2008 |
| Date and time of defence: | 24.05.2010 00:00 |
| Date of electronic submission: | 24.05.2010 |
| Date of proceeded defence: | 24.05.2010 |
| Opponents: | RNDr. Michal Kopecký, Ph.D. |
| Guidelines |
| 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. |
| References |
| 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) |
| Preliminary scope of work |
| 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. |
| Preliminary scope of work in English |
| 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. |