Přístupnostní navigace
E-application
Search Search Close
Master's Thesis
Author of thesis: Ing. Rostislav Červenka
Acad. year: 2025/2026
Supervisor: Ing. David Sedlák
Reviewer: doc. Ing. Michal Bidlo, Ph.D.
This thesis focuses on the automated creation of constructive heuristics for the Vehicle Routing Problem and its variants using a Genetic Programming Hyper-Heuristic approach. A system was developed to evolve routing-priority functions for 16 problem variants that incorporate multiple depots, capacity restrictions, time windows, and electric-vehicle range constraints. Evaluation revealed that the evolved heuristics outperformed the Nearest Neighbor heuristic and heuristics generated using a Large Language Model across all variants, with the most significant performance gains observed in variants that included time windows and range constraints. The generated heuristics also surpassed the Clarke-Wright Savings algorithm in three variants, demonstrating that this approach is an effective alternative to classical construction methods, though with room for further improvement, as shown by comparisons against known optimal solutions.
Genetic Programming, Large Language Models, Vehicle Routing Problem, Multi-Depot VRP, VRP with Time Windows, Green VRP, Electric VRP, Heuristic Evolution, Heuristics, Hyper-Heuristics, Evolutionary Algorithms
Date of defence
22.06.2026
Result of the defence
Defended (thesis was successfully defended)
Grading
A
Process of defence
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.
Topics for thesis defence
Language of thesis
English
Faculty
Fakulta informačních technologií
Department
Department of Computer Systems
Study programme
Information Technology and Artificial Intelligence (MITAI)
Specialization
Machine Learning (NMAL)
Composition of Committee
prof. Dr. Ing. Jan Černocký (předseda) prof. Ing. Martin Čadík, Ph.D. (místopředseda) doc. Ing. Vladimír Janoušek, Ph.D. (člen) doc. Ing. Michal Bidlo, Ph.D. (člen) doc. Ing. František Zbořil, Ph.D. (člen) Ing. Petr Veigend, Ph.D. (člen)
Supervisor’s reportIng. David Sedlák
Celkový přístup diplomanta k práci hodnotím velmi pozitivně. Zadání bylo splněno ve všech bodech. Diplomant navrhl, implementoval a kvalitně vyhodnotil systém schopný automatizovaně navrhovat konstrukční heuristiky pro několik variant VRP. Dosažené výsledky lze označit za uspokojivé a je v plánu jejich využití v připravované publikaci. S ohledem na uvedené skutečnosti navrhuji práci hodnotit stupněm A.
Obsahem práce byl návrh a implementace systému pro automatizovaný návrh konstruktivních heuristik pro několik vybraných variant VRP a jejich kombinací primárně s využitím GP. Zadání považuji za průměrně obtížné v kontextu diplomové práce. Dosažené výsledky odpovídají předběžným předpokladům a lze je označit za uspokojivé.
Práce byla dokončena v dostatečném předstihu a diplomant měl tak dostatek času zapracovat všechny doporučení vedoucího k finální verzi technické zprávy.
Existující publikace výsledků nebo SW mi není známa, výsledky však považuji za vědecky přínosné a publikovatelné. Získané výsledky je v plánu zahrnout do připravované publikace na PRICAI2026 (CORE B).
Diplomant při řešení využil doporučenou literaturu a zároveň samostatně dohledal a následně použil řadu kvalitních a aktuální literárních pramenů.
Aktivitu diplomanta při řešení práce považuji za nadstandardní, práce byla ve všech fázích dostatečně konzultována, diplomant byl na konzultace připraven a vždy dodržoval dohodnuté termíny a postupy.
Grade proposed by supervisor: A
Reviewer’s reportdoc. Ing. Michal Bidlo, Ph.D.
Jedná se o vědecky hodnotnou a kvalitně zpracovanou DP s publikovatelnými výsledky. Navrhuji hodnotit známkou A.
Evaluation level: assignment fulfilled, and the work contains significant extensions
Zadání bylo splněno ve všech bodech a to velmi kvalitně. Nad rámec původního zadání považuji zařazení sekci 5.5 a 5.6 pojednávajících o generovaní heuristik pomocí LLM a jejich vyhodnocení.
Evaluation level: is within the usual extent
Práce popisuje na rozumné úrovni detailu a většinou velmi srozumitelně všechny potřebné části vedoucí k řešení daných úloh. Nemám vážnějších výhrad.
Práce je psána anglicky, jazyk je velmi dobře čitelný a má vysokou odbornou úroveň. Vyskytuje se jen menší množství gramatických nedostatků v česky psaných úvodních částech.
Bez výhrad.
Student implementoval s využitím knihovny DEAP a dalších podpůrných nástrojů komplexní systém umožňující tvorbu konstrukčních heuristik pro čtyři různé typy VRP. Svůj návrh doplnil o řadu experimentů vyhodnocujících nejen tyto zvolené varianty VRP ale i další jejich kombinace. Na závadu je možná pouze fakt, že statistické vyhodnocení každé sady čítalo pouze 5 nezávislých běhů (což je pro dosažení statistické významnosti málo), ovšem vzhledem k náročnosti úloh a množství vykonaných experimentů to považuji za akceptovatelné.
Práce přináší řadu nových publikovatelných výsledků.
Evaluation level: very difficult assignment
Diplomant řešil návrh konstruktivních heuristik pro několik vybraných typů VRP a jejich kombinací pomocí genetického programování (GP). Dále provedl porovnání výkonností a kvalit takto dosažených řešení s tradičně používanou konvenční metodou Nearest Neighbours. To vyžadovalo podrobné studium problematiky směrování vozidel, návrh vhodné reprezentace pro každý typ problému, návrh konfigurací GP a propojení funkcí vycházejících z GP s těmito reprezentacemi a jejich adekvátní vyhodnocení. Téma považuji za značně obtížné.
Grade proposed by reviewer: A
Responsibility: Mgr. et Mgr. Hana Odstrčilová