Trněný, Michal
Optimalizace postupu napojování komponent v rozpadlé silniční síti [rukopis] / Michal Trněný. -- 2023. -- 68 s. + CD ROM. -- Oponent Jitka Machalová. -- Ved. práce Rostislav Vodák. -- Abstract: 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.. -- Abstract: 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.
Machalová, Jitka, 1974-. Vodák, Rostislav. Univerzita Palackého. Katedra matematické analýzy a aplikací matematiky
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. diplomové práce
(043)378.2