Metaheuristički pristup rešavanju problema maksimalnog pokrivanja lokacija

Abstract

Problem maksimalnog pokrivanja lokacija (engl. Maximal Covering Location problem, MCLP) je klasični NP-težak lokacijski problem. Polazeći od zadatog skupa lokacija korisnika i skupa potencijalnih lokacija snabdevača, cilj MCLP je odabrati p lokacija za uspostavljenje snabdevača tako da se maksimizuje ukupna potražnja pokrivenih korisnika. Korisnik se smatra pokrivenim od strane snabdevača, ukoliko je njihovo međusobno rastojanje manje od zadatog radijusa pokrivanja. MCLP ima značajnu primenu pri optimizaciji telekomunikacijskih i transportnih mreža, sistema za reagovanje u hitnim situacijama, mreža snabdevanja, itd. Kako u praksi ove mreže najčešće uključuju veliki broj korisnika, u ovom radu predložena je varijanta Metode promenljivih okolina (engl. Variable Neighborhood Search, VNS) kao metaheuristički pristup za rešavanje MCLP. Performanse predložene VNS metode su ispitane na realnim test instancama i rezultati su upoređeni sa najboljim poznatim rešenjima iz literature.

The Maximal Covering Location Problem (MCLP) is a classical NP-hard location problem. Starting from the given set of user locations and a set of potential locations of suppliers, the goal of the MCLP is to choose p locations of suppliers such that the total demand of covered users is maximized. A user is considered covered by a supplier, if the distance between them is less than the given coverage radius. MCLP has important applications in optimization of telecommunication and transportation networks, emergency response systems, supply networks, etc. Since these networks often involve large number of users, we propose a variant of Variable Neighborhood Search method (VNS) as a metaheuristic approach to MCLP. The performance of the proposed VNS method is evaluated on real-life test instances and the obtained results are compared with best known solutions from the literature.