Rješavanje problema usmjeravanja vozila ograničenog kapaciteta uz pomoć hibridnog evolucijskog algoritma s lokalnom pretragom i kontrolom populacije

undergraduate thesis

• Title (english): Solving the capacitated vehicle routing problem using hybrid evolutionary algorithm with local search and population control
• Author: Marin Kvesić
• Mentor: Marin Golub (mentor)
• Committee member: Marin Golub (predsjednik povjerenstva)
• Committee member: Ivan Grubišić (član povjerenstva)
• Committee member: Stjepan Požgaj (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Ovaj završni rad bavi se rješavanjem problema usmjeravanja vozila s ograničenim
kapacitetom, koji je jedan od ključnih problema u optimizaciji logističkih operacija.
Problem uključuje pronalaženje optimalnih ruta za vozila koja moraju dostaviti robu do
različitih odredišta uz minimalne troškove, poštujući pritom ograničenja kapaciteta
vozila. U okviru praktičnog dijela rada programski je ostvaren hibridni evolucijski
algoritam koji kombinira genetski algoritam s lokalnom pretragom i kontrolom
populacije kako bi se postiglo čim bolje rješenje. Algoritam je implementiran koristeći
Python knjižnicu PyGAD. Razvijeno je i grafičko korisničko sučelje koje omogućava
unos problema, odabir algoritma, postavljanje hiperparametara i prikaz rezultata
evolucijskog procesa. Algoritmi su testirani na nekoliko standardnih instanci problema
s poznatim najboljim rješenjem. Rezultati su analizirani s obzirom na brzinu i kvalitetu
rješenja te su se ponudili načini za unaprjeđenje rada algoritma.

Abstract (english)

This thesis addresses the capacitated vehicle routing problem, which is one of the key
issues in optimizing logistics operations. The problem involves finding optimal routes
for vehicles that must deliver goods to various destinations with minimal costs while
respecting vehicle capacity constraints. A hybrid evolutionary algorithm that combines
a genetic algorithm with local search and population control has been implemented to
achieve the best possible solution. The algorithm is implemented using the Python
library PyGAD. A graphical user interface has also been developed, allowing for the
problem input, algorithm selection, hyperparameter configuration and the display of the
evolutionary process results. The algorithms were tested on several benchmark problem
instances with known best solutions. The results were analyzed in terms of speed and
solution quality. Methods for improving the algorithm's performance were proposed.

• Keywords: Problem kapacitiranog usmjeravanja vozila; genetski algoritam; hibridni evolucijski algoritam; lokalna pretraga; kontrola populacije; optimizacija ruta; Clarke-Wright uštede
• Keywords (english): Capacitated Vehicle Routing Problem; Genetic Algorithm; Hybrid Evolutionary Algorithm; Local Search; Population Control; Route Optimization; Clarke-Wright Savings
• Language: croatian
• URN:NBN: urn:nbn:hr:168:576674
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-10-12 21:17:26