Number of the records: 1
Optimalizace postupu napojování komponent v rozpadlé silniční síti
Title statement Optimalizace postupu napojování komponent v rozpadlé silniční síti [rukopis] / Michal Trněný Additional Variant Titles Optimalizace postupu napojování komponent v rozpadlé silniční síti Personal name Trněný, Michal (dissertant) Translated title Optimization of the process of reconstruction of broken road networks Issue data 2023 Phys.des. 68 s. + CD ROM Note Oponent Jitka Machalová Ved. práce Rostislav Vodák Another responsib. Machalová, Jitka, 1974- (opponent) Vodák, Rostislav (thesis advisor) Another responsib. Univerzita Palackého. Katedra matematické analýzy a aplikací matematiky (degree grantor) Keywords silniční síť * komponenty souvislosti * napojování * optimalizace * mravenčí kolonie * Max-Min Ant System * kostra * složitost * road network * connected components * reconnection * optimization * ant colony * Max-Min Ant System * spanning tree * complexity Form, Genre diplomové práce master's theses UDC (043)378.2 Country Česko Language čeština Document kind PUBLIKAČNÍ ČINNOST Title Mgr. Degree program Navazující Degree program Matematika Degreee discipline Matematika a její aplikace book
Kvalifikační práce Downloaded Size datum zpřístupnění 00274257-122504018.pdf 8 490.5 KB 17.04.2023 Posudek Typ posudku 00274257-ved-560923305.pdf Posudek vedoucího 00274257-opon-207798371.pdf Posudek oponenta Ostatní přílohy Size Popis 00274257-other-551334829.zip 1 MB
Optimalizace postupu napojování komponent v rozpadlé silniční síti patří do třídy NP-úplných úloh, pro které nejsou známy deterministické algoritmy, které by libovolnou instanci dokázaly vyřešit v čase, který je polynomiální funkcí velikosti úlohy. Proto používáme stochastické algoritmy. V práci je k řešení úlohy využit Max-Min Ant System, algoritmus ze třídy ACO metaheuristik. Ke konkrétní rovinné síti, rozmístění stanic, blokací a dob jejich oprav hledáme optimální kombinaci parametrů, pro niž Max-Min Ant System funguje nejlépe. Zjišťujeme, zda optimalita parametrů zůstává zachována i pro jiné situace na stejné síti.The optimization of the process of reconnection of broken road network belongs to the class of NP-complete problems for which there are no known deterministic algorithms that can solve any instance in time, which is a polynomial function of the problem size. Therefore, we use stochastic algorithms. In the thesis, the Max-Min Ant System, an algorithm from the ACO class of metaheuristics, is used to solve the problem. Given a specific planar network, a distribution of stations, blockages and their repair times, we search for the optimal combination of parameters for which Max-Min Ant System performs best. We check whether the optimality of the parameters is preserved for other situations on the same network.
Number of the records: 1