| Sažetak | U ovom radu je implementiran algoritam računalne inteligencije koji rješava problem usmjeravanja vozila (eng. Vehicle routing problem, VRP). Algoritam je implementiran u jeziku C++, u okruženju Microsoft Visual Studio 2019. Korišten je mravlji algoritam, preciznije MMAS algoritam na kojemu su kasnije provođeni eksperimenti na primjercima problema A-n32-k5, A-n55-k9, A-n63-k9, A-n80-k10, B-n35-k5, B-n45-k5, B-n50-k7, B-n78-k10, E-n101-k14, E-n22-k4, E-n30-k3, E-n33-k4, E-n51-k5, F-n45-k4, F-n72-k4, M-n101-k10, P-n16-k8 i P-n40-k5. Cilj istraživanja je bio postići napredak algoritma kroz vrijeme, odnosno njegovo učenje i konstrukciju optimalnog rješenja. Problem usmjeravanja vozila je kombinatorni problem koji odgovara na pitanje: „Koji je optimalni skup ruta za flotu vozila kako bi se nešto prikupilo ili isporučilo na određene lokacije?“. Radi se o generalizaciji dobro poznatog problema trgovačkog putnika (TSP). VRP se često izravno primjenjuje u industriji, a sektor prijevoza čini osjetan udio BDP-a primjerice u EU. Cilj rada je rješavanje NP-teškog problema koji standardnim matematičkim metodama nije rješiv u razumnom vremenu, a korištenjem mravljeg algoritma može se dobiti približno optimalno rješenje koje će biti prihvatljivo. Prvi put se VRP pojavio u radu Georgea Dantziga i Johna Ramsera 1959. godine u kojem je opisan prvi algoritamski pristup koji je primijenjen na problem isporuke benzina. Godine 1964.,Clarke i Wright poboljšali su Dantzigov i Ramserov pristup koristeći pohlepnog algoritma nazvanog algoritam štednje. U problemu usmjeravanja vozila (VRP), dan nam je skup kupaca s poznatim zahtjevima, skup vozila i početna točka kretanja. Problem je osmisliti najjeftinije rute za vozila koje prolaze i završavaju u početnoj točki kretanja kako bi uslužile korisnike ovisno o ograničenjima kapaciteta vozila. Cilj je zadovoljiti svakog kupca, odnosno posjetiti ga jedanput i ispuniti njegove zahtjeve, a pri tome koristiti više vozila kako bi se troškovi puta smanjili. Nakon provedenih eksperimenata došao sam do zaključka kako MMAS algoritam pronalazi dobra rješenja za veliki broj instanci problema. Proveli smo 23 različitih eksperimenata čiji su rezultati unutar 10% razlike od optimalno prikazanih, dok smo za 1 primjer dobili bolje rješenje od znanstveno predstavljenog te smo za 9 eksperimenta dobili optimalno rješenje. Lokalna optimizacija često uvelike doprinosi poboljšavanju rješenja, ali algoritam bez lokalne optimizacije ne daje nužno uvijek najgore rezultate. Lokalna optimizacija je veće instance problema uvelike usporila, ali je bila nužna strategija za korištenje uz listu favorita. |
