Tato práce je zaměřena na srovnání různých způsobů řešení vybraného dopravního problému, známého jako problém obchodního cestujícího. V prvních kapitolách práce je představen teoretický základ této problematiky a jsou uvedeny základní pojmy teorie grafů, které jsou potřebné k vyřešení problému obchodního cestujícího. Třetí kapitola práce je věnována podrobnému popisu metod, používaných k řešení tohoto problému. Jsou zde popsány algoritmy klasických, evolučních i metaheuristických metod. Ve čtvrté části je uvedena srovnávací analýza implementovaných algoritmů, včetně porovnání jejich výsledků na reálných geodatech. V poslední části práce je popsána architektura vytvořené aplikace, včetně uživatelské dokumentace a vizualizace získaných výsledků na reálné mapě.
Anotace v angličtině
This work is focused on the comparison of different techniques to solving a selected transport problem, known as the traveling salesman problem. The first chapters of the work introduce the theoretical basis of this issue and present the basic concepts of graph theory, which are needed to solve the travelling salesman problem. The third chapter is devoted to a detailed description of the methods used to solve this problem. Algorithms of classical, evolutionary and metaheuristic methods are described here. The fourth part presents a comparative analysis of implemented algorithms, including a comparison of their results on real geodata. The last part of the work describes the architecture of the created application, including user documentation and visualization of the obtained results on a real map.
Klíčová slova
Problém obchodního cestujícího, teorie grafů, evoluční metody, metaheuristické metody, optimalizace, cesta.
Tato práce je zaměřena na srovnání různých způsobů řešení vybraného dopravního problému, známého jako problém obchodního cestujícího. V prvních kapitolách práce je představen teoretický základ této problematiky a jsou uvedeny základní pojmy teorie grafů, které jsou potřebné k vyřešení problému obchodního cestujícího. Třetí kapitola práce je věnována podrobnému popisu metod, používaných k řešení tohoto problému. Jsou zde popsány algoritmy klasických, evolučních i metaheuristických metod. Ve čtvrté části je uvedena srovnávací analýza implementovaných algoritmů, včetně porovnání jejich výsledků na reálných geodatech. V poslední části práce je popsána architektura vytvořené aplikace, včetně uživatelské dokumentace a vizualizace získaných výsledků na reálné mapě.
Anotace v angličtině
This work is focused on the comparison of different techniques to solving a selected transport problem, known as the traveling salesman problem. The first chapters of the work introduce the theoretical basis of this issue and present the basic concepts of graph theory, which are needed to solve the travelling salesman problem. The third chapter is devoted to a detailed description of the methods used to solve this problem. Algorithms of classical, evolutionary and metaheuristic methods are described here. The fourth part presents a comparative analysis of implemented algorithms, including a comparison of their results on real geodata. The last part of the work describes the architecture of the created application, including user documentation and visualization of the obtained results on a real map.
Klíčová slova
Problém obchodního cestujícího, teorie grafů, evoluční metody, metaheuristické metody, optimalizace, cesta.
Diplomová práce by měla obsahovat srovnání jednotlivých metod, vhodných pro řešení vybraného dopravního problému - například problém obchodního cestujícího (okružní) nebo jiný dle výběru diplomanta. Dle rozsahu lze vybrat i dvě různé úlohy a srovnat je mezi sebou. Diplomová práce by měla obsahovat jak srovnání klasických metod při řešení vybraného problému (například pro problém obchodního cestujícího to jsou metoda výhodnostních čísel, metoda Habrových frekvencí, spojovací metoda, metoda ztrát a další), tak i genetický přístup a implementovaný genetický algoritmus. Práce by měla obsahovat i metaheureistické metody, hlavně metodu Tabu search. Výstupem by měla být aplikace, umožńující vyřešení konkrétního dopravního problému optimální metodou z diplomantem implementovaných metod a jejich srovnání. Práce by měla být doplněna i o grafické výstupy, vzniklé při optimalizaci řešených úloh.
Zásady pro vypracování
Diplomová práce by měla obsahovat srovnání jednotlivých metod, vhodných pro řešení vybraného dopravního problému - například problém obchodního cestujícího (okružní) nebo jiný dle výběru diplomanta. Dle rozsahu lze vybrat i dvě různé úlohy a srovnat je mezi sebou. Diplomová práce by měla obsahovat jak srovnání klasických metod při řešení vybraného problému (například pro problém obchodního cestujícího to jsou metoda výhodnostních čísel, metoda Habrových frekvencí, spojovací metoda, metoda ztrát a další), tak i genetický přístup a implementovaný genetický algoritmus. Práce by měla obsahovat i metaheureistické metody, hlavně metodu Tabu search. Výstupem by měla být aplikace, umožńující vyřešení konkrétního dopravního problému optimální metodou z diplomantem implementovaných metod a jejich srovnání. Práce by měla být doplněna i o grafické výstupy, vzniklé při optimalizaci řešených úloh.
Seznam doporučené literatury
DOSTÁL, Petr. Optimalizační metody. Kunovice: Evropský polytechnický institut, 2008, 44 s. ISBN 978-80-7314-136-3.
KUČERA, Petr. Metodologie řešení okružního dopravního problému. Praha: ČZU, 2009, 122s.
MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 4., upr. a dopl. vyd. V Praze: Karolinum, 2009, 442 s. ISBN 978-80-246-1740-4.
Seznam doporučené literatury
DOSTÁL, Petr. Optimalizační metody. Kunovice: Evropský polytechnický institut, 2008, 44 s. ISBN 978-80-7314-136-3.
KUČERA, Petr. Metodologie řešení okružního dopravního problému. Praha: ČZU, 2009, 122s.
MATOUŠEK, Jiří a Jaroslav NEŠETŘIL. Kapitoly z diskrétní matematiky. 4., upr. a dopl. vyd. V Praze: Karolinum, 2009, 442 s. ISBN 978-80-246-1740-4.
Přílohy volně vložené
-
Přílohy vázané v práci
ilustrace, mapy, grafy, tabulky
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Diplomová práce by měla obsahovat srovnání jednotlivých metod, vhodných pro řešení vybraného dopravního problému - například problém obchodního cestujícího (okružní) nebo jiný dle výběru diplomanta. Dle hodnocení vedoucího DP diplomant uplatnil klasické metody řešení problému obchodního cestujícího: algoritmus Branch and Bounds, algoritmus dynamického programování, metaheuristické metody: algoritmus simulovaného žíhání, algoritmus Tabu Search, a dále evoluční (genetické) metody: genetický algoritmus a algoritmus Ant colony.
Po kontrole proti plagiátorství je míra podobnosti práce menší než 5 procent, vyšší je pouze u zdrojových kódů, kde je to nutné.
Dle hodnocení oponenta autor provedl rešerši několika optimalizačních metod pro řešení problému obchodního cestujícího. Přínosem je zejména aplikační část, kde autor srovnal algoritmy popsané v teoretické části. Aplikace je použitelná a funkční. Vytkl bych chybějící porovnání metod. V práci je dost příkladů, které by stály zato shrnout. Autor splnil cíle práce. Provedl rešerši matematických metod a vytvořil funkční aplikaci. Problémem práce je asi jazyková bariéra autora. Z hlediska vyhodnocení textu DP pomocí systému pro odhalování plagiátorství práce není plagiátem. Větší míra shody je jen u souborů, které s prací nesouvisí. Diplomová práce byla zpracována požadované úrovni. Autor práce vysvětlil připomínky oponenta a členů komise.
Práce byla zkontrolována v systému IS/STAG, dle hodnocení komise nejeví známky plagiátorství.