Семинар за рачунарство и примењену математику, 26. новембар 2019.

Наредни састанак Семинара биће одржан у уторак, 26. новембра 2019. у сали 301f Математичког института САНУ са почетком у 14:15.

Предавач: Кристина Костић, Математички факултет, Универзитет у Београду

Наслов предавања: РЕШАВАЊЕ ПРОБЛЕМА p-МЕДИЈАНЕ СА РАВНОТЕЖНИМ ОГРАНИЧЕЊИМА ПРИМЕНОМ ХИБРИДНЕ МАТЕХЕУРИСТИЧКЕ МЕТОДЕ

Апстракт:
Локацијски проблеми представљају значајну класу проблема оптимизације са широком применом у пракси, посебно при оптимизацији трошкова у транспортним и телекомуникационим мрежама. Генерално, локацијски проблеми подразумевају одређивање оптималних локација за изградњу објеката који пружају неку врсту услуге, као и придруживање сваког корисника једном или више успостављених услужних центара са циљем минимизације или максимизације одређене функције циља при условима који зависе од карактеристика конкретне мреже. Проблем p-медијане (енгл. p-median problem), један од значајних припадника ове класе проблема, подразумева локацију p услужних објеката и алокацију корисника успостављеним објектима са циљем минимизације транспортних трошкова. У оквиру предавања биће презентована варијанта проблема p-медијане која укључује додатна ограничења са циљем балансирања процеса опслуживања корисника (енгл. p- median problem with balance constraints, p-MBC}). Како p-MBC спада у класу NP-тешких проблема комбинаторне оптимизације, разматран је метахеуристички приступ решавању овог проблема. Прецизније, предложена је хибридизација двеју метахеуристичких метода: похлепне стохастичко-адаптивне процедуре претраге (GRASP) и основне методе променљивих околина (BVNS). Елементи обе методе прилагођени су карактеристикама p-MBC проблема. Хибридна GRASP-BVNS метода је тестирана на познатим инстанцама из литературе, као и на новом скупу генерисаних инстанци. Добијени резултати су упоређени са резултатима егзактног решавача.

 


Оставите ваш коментар:


(опционо)
(неће бити приказано)



Вести и дешавања


Активности на семинарима

све вести