Seminar za računarstvo i primenjenu matematiku, 26. novembar 2019.

Naredni sastanak Seminara biće održan u utorak, 26. novembra 2019. u sali 301f Matematičkog instituta SANU sa početkom u 14:15.

Predavač: Kristina Kostić, Matematički fakultet, Univerzitet u Beogradu

Naslov predavanja: REŠAVANjE PROBLEMA p-MEDIJANE SA RAVNOTEŽNIM OGRANIČENjIMA PRIMENOM HIBRIDNE MATEHEURISTIČKE METODE

Apstrakt:
Lokacijski problemi predstavljaju značajnu klasu problema optimizacije sa širokom primenom u praksi, posebno pri optimizaciji troškova u transportnim i telekomunikacionim mrežama. Generalno, lokacijski problemi podrazumevaju određivanje optimalnih lokacija za izgradnju objekata koji pružaju neku vrstu usluge, kao i pridruživanje svakog korisnika jednom ili više uspostavljenih uslužnih centara sa ciljem minimizacije ili maksimizacije određene funkcije cilja pri uslovima koji zavise od karakteristika konkretne mreže. Problem p-medijane (engl. p-median problem), jedan od značajnih pripadnika ove klase problema, podrazumeva lokaciju p uslužnih objekata i alokaciju korisnika uspostavljenim objektima sa ciljem minimizacije transportnih troškova. U okviru predavanja biće prezentovana varijanta problema p-medijane koja uključuje dodatna ograničenja sa ciljem balansiranja procesa opsluživanja korisnika (engl. p- median problem with balance constraints, p-MBC}). Kako p-MBC spada u klasu NP-teških problema kombinatorne optimizacije, razmatran je metaheuristički pristup rešavanju ovog problema. Preciznije, predložena je hibridizacija dveju metaheurističkih metoda: pohlepne stohastičko-adaptivne procedure pretrage (GRASP) i osnovne metode promenljivih okolina (BVNS). Elementi obe metode prilagođeni su karakteristikama p-MBC problema. Hibridna GRASP-BVNS metoda je testirana na poznatim instancama iz literature, kao i na novom skupu generisanih instanci. Dobijeni rezultati su upoređeni sa rezultatima egzaktnog rešavača.

 



Nažalost nije moguće ostaviti komentar.