Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/2099
Title: Metaheuristički pristup rešavanju problema maksimalnog pokrivanja lokacija
Other Titles: A metaheuristic approach to solving the maximal covering location problem
Authors: Mrkela, Lazar
Stanimirović, Zorica 
Affiliations: Numerical Mathematics and Optimization 
Keywords: location problem;maximal covering;variable neighborhood search;metaheuristics
Issue Date: 2019
Rank: M33
Publisher: Beograd : Fakultet organizacionih nauka
Related Publication(s): Zbornik radova XLVI Simpozijuma o operacionim istraživanjima SYM-OP-IS2019
Conference: Simpozijum o operacionim istraživanjima SYM-OP-IS(46 ; 2019 ; Kladovo)
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.
URI: https://research.matf.bg.ac.rs/handle/123456789/2099
Appears in Collections:Research outputs

Show full item record

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.