| Thesis title: |
Vytvoření aplikace na modelování souvislého síťového grafu a hledání nejkratší cesty |
| Author: |
Plaček, Vít |
| Thesis type: |
Bakalářská práce |
| Supervisor: |
Vávra, Vojtěch |
| Opponents: |
Sokol, Ondřej |
| Thesis language: |
Česky |
| Abstract: |
Tato bakalářská práce se zabývá využitím teorie grafů při modelování dopravních sítí a hledání cest v silniční dopravě. Teoretická část práce představuje základní pojmy teorie grafů, způsoby reprezentace grafu v počítači, vybrané grafové algoritmy a souvislost mezi dopravním problémem, teorií her a Wardropovým ekvilibriem. Pozornost je věnována také nákladovým funkcím hran, které umožňují modelovat změnu cestovní doby v závislosti na zatížení komunikace. Praktická část práce popisuje návrh a implementaci aplikace pro tvorbu a analýzu dopravní sítě. Aplikace umožňuje uživateli vytvářet orientovaný graf, nastavovat nákladové funkce hran, zadávat dopravní poptávku mezi dvojicemi uzlů a vypočítat přibližné rozložení dopravních toků v síti. Pro výpočet je využit upravený Frank-Wolfův postup s interpretací tlumené nejlepší odpovědi uživatelů. Výsledkem práce je nástroj, který umožňuje názorně demonstrovat vliv změn v dopravní síti na rozložení dopravního zatížení a cestovní náklady. |
| Keywords: |
teorie her; dopravní síť; Wardropovo ekvilibrium; Frank-Wolfeův algoritmus; dopravní tok; Python; Braessův paradox; teorie grafů; nákladová funkce |
| Thesis title: |
Development of an Application for Modeling a Connected Network Graph and Finding the Shortest Path |
| Author: |
Plaček, Vít |
| Thesis type: |
Bachelor thesis |
| Supervisor: |
Vávra, Vojtěch |
| Opponents: |
Sokol, Ondřej |
| Thesis language: |
Česky |
| Abstract: |
This bachelor thesis deals with the use of graph theory in modelling transportation networks and path finding in road traffic. The theoretical part introduces the basic concepts of graph theory, graph representation in computer programs, selected graph algorithms, and the relationship between transportation problems, game theory, and Wardrop equilibrium. Attention is also paid to edge cost functions, which make it possible to model changes in travel time depending on road congestion. The practical part describes the design and implementation of an application for creating and analysing a transportation network. The application allows the user to create a directed graph, define edge cost functions, enter transportation demand between pairs of nodes, and compute an approximate distribution of traffic flows in the network. The calculation is based on a modified Frank-Wolfe procedure interpreted as a damped best response of network users. The result of the thesis is a tool that can visually demonstrate the influence of changes in a transportation network on traffic flow distribution and travel costs. |
| Keywords: |
game theory; traffic flow; cost function; ransportation network; Wardrop equilibrium; Python; graph theory; Frank-Wolfe algorithm; Braess paradox |
Information about study
| Study programme: |
Aplikovaná informatika |
| 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: |
3. 2. 2025 |
| Date of submission: |
11. 5. 2026 |
| Date of defense: |
2026 |
Files for download
The files will be available after the defense of the thesis.