Hodnocení bakalářské práce – oponent
Autor hodnocení: Ing. Kateřina Slaninová, Ph.D.
Vedoucí bakalářské práce: Ing. Jan Martinovič, Ph.D.
Oponenti: Ing. Kateřina Slaninová, Ph.D.
Téma: Řešení problému okružních jízd s využitím optimalizace pomocí mravenčích kolonií
Verze ZP: 1
Student: Jan Vargovský
1. Splnění požadavků zadání.
Student měl dle zadání bakalářské práce analyzovat algoritmy pro optimalizace mravenčích kolonií (Ant Colony Optimisation, ACO) a implementovat vybranou variantu tohoto algoritmu. Dále měl student provést benchmark implementovaného algoritmu na dodané datové sadě a implementovat jednoduchou vizualizaci. Student v práci popsal různé varianty optimalizace mravenčích kolonií ve vazbě na problém okružních jízd (Vehicle routing problem, VRP). Student implementoval jednu z variant algoritmu pro optimalizaci mravenčích kolonií a provedl srovnání výsledků tohoto
algoritmu s dalšími dvěma přístupy: heuristickým – adaptivní prohledávání velkého okolí (Adaptive Large Neighbourhood Search, ALNS) a s exaktním algoritmem VRP. Výsledky všech algoritmů byly porovnány a implementována vizualizace výsledků. Práci hodnotím jako náročnější. Zadání bylo dle mého názoru beze zbytku splněno.
2. Hodnocení formální stránky závěrečné práce.
Práce je logicky strukturována, rozsah jednotlivých částí je zvolen vhodně. Po jazykové stránce je práce napsána velmi pěkně, úprava odpovídá formálním požadavkům na bakalářskou práci. Občas se v práci objeví gramatické chybky, což ale nesnižuje kvalitu práce. Spíše oceňuji, že je práce napsána v anglickém jazyce, i když se jedná teprve o bakalářskou práci.
3. Hodnocení výsledků závěrečné práce.
Student implementoval algoritmus pro řešení problému okružních jízd (vehicle routing problem) s využitím optimalizace mravenčích kolonií. Pro implementaci použil .Net Core, resp. C# a MVC.
Pro vizualizaci výstupů použil D3 knihovnu v kombinaci s HTML, CSS a SVG. Výsledky implementovaného algoritmu porovnal s dalším heuristickým algoritmem, ALNS a s exaktním algoritmem pro výpočet VRP. Pro benchmark použil datovou sadu, kterou dostal k tomuto účelu k dispozici. Provedl 3 typy testů pro různě velké datové sady. Z výsledků testů je patrné, že implementovaný ACO algoritmus je rychlejší než ALNS a exaktní VRP algoritmus (jedná se ale o sekvenční variantu). Kód ACO je funkční, je dodán spolu s dokumentací v příloze k bakalářské práci.
Student dále implementoval jednoduchou vizualizaci výsledků. Jedná se o webovou aplikaci umožňující zadávat vstupní parametry před spuštěním algoritmu.
4. Hodnocení práce z hlediska přínosu nových poznatků.
Jedná se o práci, která sice nepřináší nové poznatky po vědecké stránce, ale která ukazuje na schopnost studenta samostatně nastudovat problematiku a navrhnout implementaci. Výsledky práce budou využity při řešení vybraných projektů zaměřených na VRP ať už ve spolupráci s OZO Ostrava nebo s firmou Sygic.
5. Charakteristika výběru a využití studijních pramenů.
Použité zdroje a literatura odpovídají a dostatečně popisují jak teoretickou část zaměřenou na popis algoritmu a jeho modifikací, tak implementační části práce.
6. Otázky k obhajobě.
K práci nemám žádných otázek.
7. Souhrnné hodnocení.
Student splnil cíl práce, prostudoval ACO algoritmy pro VRP a implementoval jednu z variant. Dále provedl testování implementovaného algoritmu a provedl porovnání jeho výsledků s ostatními. Také vizualizaci výsledků implementoval jako webovou aplikaci. Práci hodnotím jako výbornou a
doporučuji k obhajobě.
výborně Celkové hodnocení:
Ostrava, 19.05.2017 Ing. Kateřina Slaninová, Ph.D.
Classification of Bachelor Thesis – opponent
Author of classification: Ing. Kateřina Slaninová, Ph.D.
Supervisor: Ing. Jan Martinovič, Ph.D.
Opponents: Ing. Kateřina Slaninová, Ph.D.
Title: Ant Colony Optimization Algorithm for Vehicle Routing Problem
Thesis version: 1
Student: Jan Vargovský
1. Meeting the requirements of the thesis assignment.
According to the assignment, the student should analyse algorithms for Ant Colony Optimisation (ACO) and implement the selected variant of this method. Experimental verification should also be done on the given dataset and the outputs should be visualised by his own implementation. The student described several variants of ACO for Vehicle routing problem (VRP) and he implemented one of the approach. He also run a benchmark for comparison of the implemented algorithm with other two approaches: heuristics Adaptive Large Neighbourhood Search (ALNS), and exact VRP algorithm. He proposed a simple visualization of the outputs. I assess the thesis as more demanding.
In my opinion, the assignment was fully achieved.
2. Thesis technicality evaluation.
The bachelor thesis has a logical structure, the content is appropriate. It is well written; the thesis also meets layout and formal requirements. I have found some typos. However, it does not decrease the quality of the thesis. I rather appreciate that the bachelor thesis is written in English.
3. Results evaluation of the thesis.
Student has implemented the algorithm for VRP by ACO. He used Net Core, resp. C# a MVC for the implementation. The visualisation has been done by HTML, CSS and SVG in combination with D3 library. The outputs of the implemented algorithm were compared with another heuristic algorithm, ALNS, and with exact VRP algorithm. The benchmark was done on the dataset, which the student obtained for this purpose. He has done 3 different tests. It is apparent from the results that the
implemented ACO algorithm is faster than ALNS and exact VRP algorithm (however, it is sequential variant). The code of ACO is working, and is included with the documentation in the attachment of the bachelor thesis. The student has also implemented a simple, but clear visualisation of the results.
It is a web application which enables setting of the input parameters before running the algorithm.
4. Evaluation of the new findings contribution.
Although the bachelor thesis does not provide new research findings, it shows that the student is able to study the topic self-containedly and to propose the implementation. The results will be used in projects focused on VRP, for example in cooperation with OZO Ostrava or Sygic company.
5. Utilization and selection of information sources.
The information sources were used appropriately.
6. Question for the defense of the thesis.
I have no questions for the defence of the bachelor thesis.
7. Summary evaluation.
The student fully achieved the goals of the thesis. He examined several variants of ACO algorithms for VRP and he implemented one of these variants. He did an experimental verification of the
implemented algorithm and he compared the achieved results with the other algorithms (ALNS, exact VRP). He also implemented visualisation of the results as web application. I evaluate the bachelor thesis as excellent and recommend for the defence.
excellent Overall classification:
Ostrava, 19.05.2017 Ing. Kateřina Slaninová, Ph.D.
