Randomizovaná heuristika pro úlohu listonoše s kapacitami - Rýdlová, Lenka (2015)
Teorie grafů je obsáhlá matematická disciplína. Spadá pod ní úloha čínského listonoše patřící do třídy rozvozních úloh. Úlohy čínského listonoše jsou v praxi velmi rozsáhlé a náročné na výpočet. Patří do kategorie NP-obtížných úloh. Z tohoto důvodu jsou navrhované heuristiky, které v polynomiálním čase poskytují přijatelně dobrá řešení. Cílem této práce je navrhnout randomizovanou heuristiku, která se neřídí deterministickými pravidly, ale náhodou. Provádí se Monte Carlo simulace, z které se vybírá nejlepší řešení. Heuristika je formulována pro neorientovanou kapacitní úlohu listonoše s nepovinnými hranami. Je naprogramována ve VBA a ozkoušena na testovacích úlohách. Na konci práce je zpracována případová studie na svoz komunálního odpadu.