Problemi usmjeravanja vozila

diplomski rad

• Naslov (engleski): Vehicle routing problems
• Autor: Ivan Šiser
• Mentor: Nikola Ivković (mentor); MBZ: 306480
• Član povjerenstva: Ivan Magdalenić (član povjerenstva); MBZ: 244501
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet organizacije i informatike; (Katedra za informatičke tehnologije i računarstvo); Varaždin
• Datum i država obrane: 2021-09-24, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: DRUŠTVENE ZNANOSTI; Informacijske i komunikacijske znanosti; Organizacija i informatika

Sažetak

Problem usmjeravanja vozila (eng. Vehicle Routing Problem, skraćeno VRP) je jedan on najpopularnijih problema u kombinatornoj optimizaciji, a njegovo proučavanje utjecalo je na istraživanje nekoliko egzaktnih i heurističkih rješenja opće primjenjivosti. Zbog svoje složenosti, pripada skupini NP-teških problema. VRP ima nekoliko različitih varijanti s obzirom na vrstu i broj ograničenja, a odabir varijante ovisi o instanci problema koja se pokušava riješiti. U današnjem svijetu u kojemu transport i logistika igraju veliku ulogu, VRP postaje sve veći predmet istraživanja s ciljem minimiziranje cijene. U ovom radu najprije je obrađena tema VRP-a i njegovih varijanti, s teorijskog i matematičkog stajališta. Nakon toga su navedeni pristupi njegovom rješavanju. Jedan od takvih pristupa je i metaheuristička optimizacija kolonijom mrava (eng. Ant Colony Optimization, skraćeno ACO), u kojoj su glavna komponenta umjetni mravi koji postupno grade optimalno rješenje. ACO također ima različite varijante, koje je potrebno odabrati i prilagoditi ovisno o problemu koji se pokušava riješiti. Tako je obrađena i varijanta MAX-MIN mravljeg sustava (eng. MAX-MIN Ant System, skraćeno MMAS), koja se pokazala da daje najbolja rješenja za veliki skup vrhova i dovoljan broj iteracija. U ovom radu, implementirano je rješenje za problem usmjeravanja vozila s ograničenjem kapaciteta (eng. Capacitated VRP, skraćeno CVRP) pomoću MMAS varijante mravljeg algoritma. Implementacija je podvrgnuta testiranjem nad različitim instancama problema dostupnih na internetu i podešenim parametrima. Na temelju izlaznih podataka testiranja, provedena je statistička analiza prema kojoj je donesen zaključak o efikasnosti algoritma i mogućim poboljšanjima.

• Ključne riječi: algoritam; računalna inteligencija; optimizacije; usmjeravanja
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:211:196600
• Studijski program: Naziv: Informacijsko i programsko inženjerstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra informatike (mag.inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-09-27 04:11:59