Original title: Automatizovaný návrh konstruktivních heuristik pro problém směrování vozidel
Translated title: Automated Design of Constructive Heuristics for the Vehicle Routing Problem
Authors: Červenka, Rostislav ; Bidlo, Michal (referee) ; Sedlák, David (advisor)
Document type: Master’s theses
Year: 2026
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato práce se zabývá automatickou tvorbou konstruktivních heuristik pro problém směrování vozidel a pro jeho varianty za pomocí hyperheuristického přístupu založeného na genetickém programování. Byl vyvinut systém, který vyvíjí funkce zaměřené na prioritu směrování pro 16 variant tohoto problému. Tyto varianty zahrnují více dep, omezení kapacity, časová okna a omezení dojezdu u elektromobilů. Ohodnocení výsledků ukázalo, že vyvinuté heuristiky dosáhly lepších výsledků než heuristiky nejbližšího souseda i heuristiky vytvořené pomocí velkého jazykového modelu ve všech variantách, přičemž nejlépe dopadly varianty s časovými okny a s elektromobily. Vygenerované heuristiky překonali i Clarke-Wrightův algoritmus úspor ve třech variantách, čímž potvrdili účinost tohoto přístupu, i když srovnání se známými optimálními řešeními ukazuje, že stále existuje značný prostor pro další zlepšování. 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.
Keywords: elektrické VRP; evoluce heuristik; evoluční algoritmy; Genetické programování; heuristiky; hyperheuristiky; Multi-Depot VRP; problém směrování vozidel; velké jazykové modely; VRP s časovými okny; zelené VRP; Electric VRP; Evolutionary Algorithms; Genetic Programming; Green VRP; Heuristic Evolution; Heuristics; Hyper-Heuristics; Large Language Models; Multi-Depot VRP; Vehicle Routing Problem; VRP with Time Windows

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/260139

Permalink: http://www.nusl.cz/ntk/nusl-776268


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses