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

završni rad

• Naslov (engleski): Solving the capacitated vehicle routing problem using hybrid evolutionary algorithm with local search and population control
• Autor: Marin Kvesić
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Ivan Grubišić (član povjerenstva)
• Član povjerenstva: Stjepan Požgaj (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2024-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Problem kapacitiranog usmjeravanja vozila; genetski algoritam; hibridni evolucijski algoritam; lokalna pretraga; kontrola populacije; optimizacija ruta; Clarke-Wright uštede
• Ključne riječi (engleski): Capacitated Vehicle Routing Problem; Genetic Algorithm; Hybrid Evolutionary Algorithm; Local Search; Population Control; Route Optimization; Clarke-Wright Savings
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:576674
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2024-10-12 21:17:26