Finding optimal path in mountain terrain
| Thesis title: | Hledání optimální trasy v horském terénu |
|---|---|
| Author: | Neugebauer, Jakub |
| Thesis type: | Bakalářská práce |
| Supervisor: | Borovička, Adam |
| Opponents: | Hanousek, Jakub |
| Thesis language: | Česky |
| Abstract: | Práce pojednává o hledání optimální cesty v horském terénu. Zaměřuje se na vytvoření zcela nového matematického modelu, který bude schopný nalézt optimální cestu mezi dvěma libovolnými body s přihlédnutím na terénní nerovnosti a převýšení, díky nimž nemusí být nejkratší cesta tou nejlepší. Využívá různých metod výpočtu a jejich následné porovnání. Zejména se jedná o Dijkstrův algoritmus a model hledání nejkratší cesty pomocí celočíselného programování, který je upravován pro zprůchodnění terénu pomocí změny účelové funkce, přidáním nových proměnných, omezení či jejich kombinací. Výstupy teoretické části jsou demonstrovány na konkrétních příkladech v terénu Krkonoš. Nalezené cesty jsou poté porovnány s již existujícími trasami. Tyto příklady potvrzují správné nastavení navržených modelů. |
| Keywords: | celočíselné (lineární) programování; Dijkstrův algoritmus; minimální kostra; nejkratší cesta; optimální turistická trasa |
| Thesis title: | Finding optimal path in mountain terrain |
|---|---|
| Author: | Neugebauer, Jakub |
| Thesis type: | Bachelor thesis |
| Supervisor: | Borovička, Adam |
| Opponents: | Hanousek, Jakub |
| Thesis language: | Česky |
| Abstract: | Thesis is about finding optimal path in mountain terrain. It focuses on creating new mathematical model, which will be able to find optimal path between two nodes considering terrain unevenness and elevation difference, which causes that the shortest path is not always the best. It uses different counting methods and their comparation, especially Dijkstra$'$s algorithm and integer programming formulation for shortest path problem, wich is then adjusted to make terrain passable by changing objective, adding new variables and constraints or their combination. The final model is demonstrated on particular cases in terrain of Krkonoše mountains. Found paths are than compared to existning roads. These examples show that the model is set up correctly. |
| Keywords: | optimal tourist road; shortest path; Dijkstra´s algotithm; integer (linear) programming; minimum spanning tree |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 15. 10. 2019 |
|---|---|
| Date of submission: | 10. 5. 2020 |
| Date of defense: | 18. 6. 2020 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/71290/podrobnosti |