Metaheuristic methods for multi-objective optimization and applications to discrete location problems

[Л. Мркела]

157 стр.

Рачунарство и информатика - Рачунарска интелигенциjа / Computer Science - Computational Intelligence

У ово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антом методе променљивих околина, а приказани су резултати поређења са уопштеним еволутивним алгоритмима.

This dissertation examines two discrete location problems and their bi- objective variants. The first problem under consideration is the maximal covering location problem with user preferences and budget constraints imposed on facility opening. This variant of the maximal covering problem has not been previously studied in the literature. Unlike the classical maximal covering problem, the variant proposed in this dissertation includes user preferences for locations, where users are assigned to the location with opened facility that they prefer the most. Additionally, different locations have different costs for establishing facilities, and the available budget for opening facilities is limited. This problem is solved using the Variable Neighborhood Search (VNS) method, and the results were compared with the ones obtained by an exact solver on modified instances from the literature. Furthermore, an existing variant of the maximal covering problem is also addressed, which imposes the limit on the number of opened facilities instead of limiting the budget for opening facilities. 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 existing model where the set of possible regenerator locations and the set of user nodes are different, defining the problem as generalized. The generalized regenerator place- ment problem in optical networks is also solved using the Variable Neighborhood Search 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 maximal covering location problem, user preferences are included as weighted factors in the total covered demand, forming the first objective function. The second objective function represents the number of uncovered users and aims to ensure fairness in the model. In the regenerator placement problem for optical networks, it is assumed that, due to budget constraints, uninterrupted communication between all pairs of user nodes may not be feasible. Each pair is assigned a weight, and the sum of the weights of connected pairs constitutes the first objective function, while the second objective function represents the cost of placing regenerators. These bi-objective variants are solved using an adapted multi-objective version of the Variable Neigh- borhood Search method, and the results are compared with general evolutionary algorithms.

вишекритериjумска оптимизациjа, проблем максималног по- кривања локациjа, проблем оптималног постављања регенератора, метахеури- стике, метода променљивих околина, еволутивни алгоритми

multi-objective optimisation, maximal covering location problem, re- generator location problem, metaheuristics, variable neighborhood search, evolu- tionary algorithms

004.421:519.8(043.3)

Tekst