Metoda promenljivih okolina za rešavanje jedne varijante problema p-hub maksimalnog pokrivanja

Abstract

Razmatran je problem p-hab maksimalnog pokrivanja neograničenih kapaciteta sa jednostrukim alokacijama (engl. Uncapacitated Single Allocation p-hub Maximal Covering Problem - USApHMCP) i binarnim konceptom pokrivanja. Cilj USApHMCP je određivanje optimalnih lokacija za uspostavljanje tačno p habova, tako da se maksimizuje ukupan protok po svim pokrivenim parovima snabdevač-korisnik. U slučaju binarnog pokrivanja, par korisnik-snabdevač se smatra pokrivenim ukoliko cena transporta od čvora-snabdevača do čvora-korisnika nije veća od unapred zadate maksimalne vrednosti (radijusa pokrivanja). Razvijene su dve varijante opšte metode promenljivih okolina (engl. General Variable Neighborhood Search - GVNS ) za rešavanje USApHMCP. Predložene varijante GVNS metode koriste različite procedure u fazi poboljšanja rešenja: sekvencijalnu metodu promenljivog spusta (engl. Sequential Variable Neighborhood Descent) i ugnježdenu metodu promenljivog spusta (engl. Nested Variable Neighborhood Descent). Uticaj ovih procedura poboljšanja ispitan je kroz testiranja na instancama problema koje uključuju do 200 čvorova. Dobijeni rezultati testiranja obe varijante GVNS metode ukazuju da njihovu efikasnost u pogledu kvaliteta rešenja i brzine izvršavanja, kao i superiornost u odnosu na postoje´ce metode iz literature.