Abstract: | V této práci řeším problém optimálního směrování v sítích s omezeními. Úkolem je z množiny linek v dané síti vybrat nejlevnější podmnožinu tak,
aby bylo možné přenášet data ze zdrojových do cílových uzlů a přitom splnit různé omezující podmínky. Tyto podmínky zahrnují požadavky na přenosovou kapacitu a zpoždění jednotlivých linek a také omezení na celkové zpoždění. K dalším podmínkám patří, že některé zprávy musí být přenášeny pouze po zabezpečených protokolech. Tento problém patří mezi NP-těžké a větší instance nemohou být vyřešeny optimálně v rozumném čase. Tento problém řeším pomocí dvou algoritmů: evolučního algoritmu a Prototype Optimisation with Evolved Improvement Steps. Popisuji princip jejich funkce, konkrétní implementaci a srovnání výsledků těchto algoritmů oproti jiným způsobům řešení tohoto problému: celočíselným lineárním programováním, Column Generation a Lagrangean Decomposition.
|
---|