Travelling salesman problem

Tato práce se zabývá principy řešení optimalizační úlohy známé jako Problém obchodního cestujícího. První část je teoretickým úvodem do problematiky vázané na teorii složitosti a optimalizace. Dále je uveden popis principu užití a implementace metody větví a mezí, vybraných heuristických postupů a optimalizačního nástroje Gurobi optimizer.This thesis deals with various solving principles of optimization problem known as the travelling salesman problem. The first part is a theoretical introduction to the problem related to the theory of complexity and optimization. It also describes the principles of using and implementing the branch and bound method, selected heuristics and the optimization tool Gurobi optimizer.Fakulta elektrotechniky a informatikyProblém obchodního cestujícího je optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě. V teorii grafů zní úkol: V daném ohodnoceném úplném grafu najděte nejkratší Hamiltonovskou kružnici. Problém je, že s rostoucím počtem měst počet možných cest velice rychle narůstá. Proto se požívají heuristické metody. Cílem práce bude rešerše těchto metod, návrh a vypracování aplikace pro nalezení minimální Hamiltonovské kružnice. Diplomant vytvořil teoretickou část, popisující danou problematiku, vysvětlil používané metody včetně ilustrativních příkladů. Dále popsal vytvořenou aplikaci, včetně použitých návrhových vzorů, a přiložil uživatelskou dokumentaci, včetně srovnání výsledků jednotlivých algoritmů. Programová část je funkční. Práce byla zkontrolována v systému IS STAG a byla vyhodnocena jako původní. Nejedná se o plagiát