Одељење за математику, 14. април 2011.

• 08. Април, 2011
• Коментари (0)

Наредни састанак Одељења за математику одржаће се у четвртак, 14. априла 2011. у сали 2 САНУ са почетком у 14h.

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

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

Садржај: Хаб локацијски проблеми су у последње две деценије доживели  праву експанзију, највише захваљујући својој широкој примени у пракси.  Мреже хабова (eng. hub networks) су највише заступљене у модерним  транспортним и телекомуникацијским системима, рачунарским и интернет  мрежама. Хабови (eng. hubs) представљају центре консолидације и колекције протока у мрежи између две локације. Коришћењем хабова као  тачака преусмеравања протока и повећавањем транспорта између хабова, капацитет мреже се може искористити доста ефикасније а трошкови транспорта смањити. У оквиру предавања биће разматран хаб локацијски проблем  неограничених капацитета са једноструким алокацијама позиције хабова  (Uncapacitated Single Allocation Hub Location Problem - USAHLP).
Циљ овог NP-тешког проблема комбинаторне оптимизације је следећи:  успоставити скуп хабова и алоцирати не-хаб чворови елементима скупа  успостављених хабова, тако да сума транспортних трошкова у мрежи и
фиксних трошкова лоцирања хабова буде минимална. Биће представљена  математичка формулација USAHLP и предложен хибридни хеуристички алгоритам (HEA) за решавање овог проблема. Дизајниране су две хеуристике локалног претраживања у циљу побољшања локацијског и алокацијског  аспекта проблема, које су затим имплементиране у оквиру еволутивног  концепта за решавање USAHLP. Алгоритам је тестиран на постојећим  инстанцама хаб проблема из литературе, као и на новим инстанцама реалних  димензија (до 900 локација). Добијени експериментални резултати и поређења са другим методама указују на ефикасност предложеног хибридног приступа, посебно у случајевима инстанци реалних димензија. Алгоритам даје оптимална и поправља постојећа најбоља решења из литературе у веома  кратком времену извршавања. Предности HGA посебно долазе до изражаја при  решавању инстанци проблема великих димензија, на којима се постижу  значајна побољшања у погледу и квалитета HGA решења и времена извршавања.

(коаутори на овом истраживању су др Мирослав Марић и Предраг Станојевић са Математичког факултета у Београду)