Vytvoření aplikace na modelování souvislého síťového grafu a hledání nejkratší cesty
Autor(ka) práce:
Plaček, Vít
Typ práce:
Bakalářská práce
Vedoucí práce:
Vávra, Vojtěch
Oponenti práce:
Sokol, Ondřej
Jazyk práce:
Česky
Abstrakt:
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.
Klíčová slova:
teorie her; dopravní síť; Wardropovo ekvilibrium; Frank-Wolfeův algoritmus; dopravní tok; Python; Braessův paradox; teorie grafů; nákladová funkce
Název práce:
Development of an Application for Modeling a Connected Network Graph and Finding the Shortest Path
Autor(ka) práce:
Plaček, Vít
Typ práce:
Bachelor thesis
Vedoucí práce:
Vávra, Vojtěch
Oponenti práce:
Sokol, Ondřej
Jazyk práce:
Česky
Abstrakt:
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.