Digitalni repozitorijum
Univerziteta u Beogradu
{{ mc.sd.lang | uppercase }}
Метахеуристичке методе вишекритеријумске оптимизације и примене на дискретне локацијске проблеме : докторска дисертација
Mrkela, Lazar,
Davidović, Tatjana, 1964-
Stanimirović, Zorica, 1976-
Marić, Miroslav, 1978-
Radojičić Matić, Nina, 1987-
У овоj дисертациjи разматрана су два дискретна локациjска про-блема и њихове двокритериjумске вариjанте. Разматран jе проблем максимал-ног покривања локациjа са преференциjама корисника и ограничењима буџетаза отварање обjеката. Ова вариjанта проблема максималног покривања ниjе досада разматрана у литератури. За разлику од класичног проблема максимал-ног покривања, проблем разматран у овоj дисертациjи укључуjе преференциjекорисника ка локациjама, при чему се сваки корисник додељуjе локациjи коjунаjвише преферира, а коjа има отворен обjекат. Поред тога, различите локациjеимаjу различите цене постављања обjеката, а расположиви буџет jе ограничен.Оваj проблем jе решаван методом променљивих околина, а добиjени резултатису упоређени са резултатима егзактног решавача на модификованим инстан-цама из литературе. Додатно, решавана jе и постоjећа вариjанта проблемамаксималног покривања коjа уместо ограниченог буџета укључуjе ограничењана броj обjеката коjе треба отворити.Разматран jе и проблем постављања регенератора у оптичким мрежама.Код оптичких мрежа квалитет сигнала опада са растоjањем, те jе потребно по-ставити скупе уређаjе коjи ће опоравити сигнал. У овоj дисертациjи разматранjе постоjећи модел, где jе скуп локациjа за постављање регенератора и скупкорисничких чворова различит и проблем се назива уопштеним. Уопштенипроблем постављања регенератора у оптичким мрежама jе такође решаван ме-тодом променљивих околина, а резултати су упоређени са наjбољим доступнимиз литературе.Дефинисане су и двокритериjумске вариjанте наведених проблема. Код про-блема максималног покривања локациjа, преференциjе корисника су укљученекао тежински фактори у укупноj покривеноj потражњи, што чини прву функ-циjу циља. Друга функциjа представља броj непокривених корисника и тежида оствари правичност у моделу. Код проблема постављања регенератора уоптичким мрежама, претпоставка jе да, услед ограниченог буџета, ниjе могућеобезбедити несметану комуникациjу између свих парова корисничких чворова.Сваки пар има додељену тежину, а сума тежина повезаних парова чини првуфункциjу циља. Друга функциjа циља jе цена постављања регенератора. Дво-критериjумске вариjанте су решаване прилагођеном вишекритеириjумском ва-риjантом методе променљивих околина, а приказани су резултати поређења сауопштеним еволутивним алгоритмима.
Рачунарство и информатика - Рачунарска интелигенциjа / Computer Science - Computational Intelligence Datum odbrane: 22.04.2025.
This dissertation examines two discrete location problems and their bi-objective variants. The first problem under consideration is the maximal coveringlocation problem with user preferences and budget constraints imposed on facilityopening. This variant of the maximal covering problem has not been previouslystudied in the literature. Unlike the classical maximal covering problem, the variantproposed in this dissertation includes user preferences for locations, where users areassigned to the location with opened facility that they prefer the most. Additionally,different locations have different costs for establishing facilities, and the availablebudget for opening facilities is limited. This problem is solved using the VariableNeighborhood Search (VNS) method, and the results were compared with the onesobtained by an exact solver on modified instances from the literature. Furthermore,an existing variant of the maximal covering problem is also addressed, which imposesthe limit on the number of opened facilities instead of limiting the budget for openingfacilities.The second problem examined is the regenerator placement in optical networks.In optical networks, signal quality degrades with distance, necessitating the place-ment of costly devices to restore the signal. This dissertation studies an existingmodel where the set of possible regenerator locations and the set of user nodes aredifferent, defining the problem as generalized. The generalized regenerator place-ment problem in optical networks is also solved using the Variable NeighborhoodSearch method, with results compared to the best available solutions from the lit-erature.Bi-objective variants of these problems are defined as well. For the maximalcovering location problem, user preferences are included as weighted factors in thetotal covered demand, forming the first objective function. The second objectivefunction represents the number of uncovered users and aims to ensure fairness inthe model. In the regenerator placement problem for optical networks, it is assumedthat, due to budget constraints, uninterrupted communication between all pairs ofuser nodes may not be feasible. Each pair is assigned a weight, and the sum of theweights of connected pairs constitutes the first objective function, while the secondobjective function represents the cost of placing regenerators. These bi-objectivevariants are solved using an adapted multi-objective version of the Variable Neigh-borhood Search method, and the results are compared with general evolutionaryalgorithms.
srpski
2024
Ovo delo je licencirano pod uslovima licence
Creative Commons CC BY-NC-ND 3.0 AT - Creative Commons Autorstvo - Nekomercijalno - Bez prerada 3.0 Austria License.
http://creativecommons.org/licenses/by-nc-nd/3.0/at/legalcode
OSNO - Opšta sistematizacija naučnih oblasti, Operaciono istraživanje
OSNO - Opšta sistematizacija naučnih oblasti, Računarsko programiranje. Aplikativni programi
multi-objective optimisation, maximal covering location problem, re- generator location problem, metaheuristics, variable neighborhood search, evolu- tionary algorithms
OSNO - Opšta sistematizacija naučnih oblasti, Operaciono istraživanje
OSNO - Opšta sistematizacija naučnih oblasti, Računarsko programiranje. Aplikativni programi
вишекритериjумска оптимизациjа, проблем максималног по- кривања локациjа, проблем оптималног постављања регенератора, метахеури- стике, метода променљивих околина, еволутивни алгоритми
177314057
9902