Problemi usmjeravanja vozila

master's thesis

• Title (english): Vehicle routing problems
• Author: Ivan Šiser
• Mentor: Nikola Ivković (mentor); MBZ: 306480
• Committee member: Ivan Magdalenić (član povjerenstva); MBZ: 244501
• Granter: University of Zagreb; Faculty of Organization and Informatics; (Department of Computing and Technology); Varaždin
• Defense date and country: 2021-09-24, Croatia
• Scientific / art field, discipline and subdiscipline: SOCIAL SCIENCES; Information and Communication Sciences; Organization and Informatics

Abstract

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.

• Keywords: algoritam; računalna inteligencija; optimizacije; usmjeravanja
• Language: croatian
• URN:NBN: urn:nbn:hr:211:196600
• Study programme: Title: Information and Programming Engineering; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra informatike (magistar/magistra informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-09-27 04:11:59