On a bicycle around Slovak castles – application of traveling salesman

Bakalářska práce se věnuje vytvoření trasy cyklovýletu po slovenských hradech, zámcích a zříceninách. Nejdříve se stručně zabývá problematikou matematického modelování a lineárního programování. Dále se zaměřuje na teoretické postupy distribučních úloh, konkrétně na úlohu dopravního problému, přiřaďovacího problému, úlohu obchodního cestujícího a na úlohu o pokrytí. Následně práce v krátkosti přibližuje cyklistickou situaci na Slovensku a stručně popisuje slovenskou historii, výstavbu hradů a dějiny vybraných pevností. Praktická část práce se zabývá sběrem dat a formulací matematického modelu pro okruh napříč celým Slovenskem. Matematický model je dále přepsaný do optimalizačního softwaru MPL for Windows, za jehož pomoci je vypočítané optimální řešení. Tyto výsledky jsou interpretovány a graficky znázorněny na mapě Slovenska. Úloha je následně modifikována, a to tak, že se místo jednoho velkého okruhu vytvářejí tři menší. Nejdříve jsou historická opevnění pomocí algoritmů úlohy o pokrytí rozděleny do tří skupin a následně je pro každou z nich naformulovaný matematický model. Výsledky jsou opět interpretovány a graficky znázorněny na mapě.

This bachelor thesis focuses on creating a bicycle trip visiting Slovak castles, chateaus and ruins. Firstly, the thesis makes an introduction into the topics of mathematical modelling and linear programming. Secondly, it focuses on the theoretical methods of distribution tasks, specially transportation problem, assignment problem, travelling salesman problem and set covering problem. Subsequently, the thesis briefly reports the current cycling situation in Slovakia and describes Slovak history, the process of building castles and history of some of them. The practical part focuses on a collection of data and a formulation of a mathematical model for the route across the whole country. The mathematical model is further rewritten into a modeling system MPL for Windows, which helps to obtain the optimal solution. The results are interpreted and graphically displayed on a map of Slovakia. Subsequently, the problem is modified in a way of creating three routes from different starting points instead of one big route. Firstly, the historic fortifications are distributed into three groups using the algorithms of the set covering problem. Secondly, the mathematical models are created for each of the groups. The results are once again interpreted and graphically displayed on a map.