REŠAVANJE KLASE MIN-MAX PROBLEMA ROBUSNE DISKRETNE OPTIMIZACIJE SA PRIMENAMA

eBibliothek Repositorium

 
 

REŠAVANJE KLASE MIN-MAX PROBLEMA ROBUSNE DISKRETNE OPTIMIZACIJE SA PRIMENAMA

Zur Kurzanzeige

dc.contributor.advisor Stanimirović, Zorica
dc.contributor.author Mišković, Stefan
dc.date.accessioned 2017-02-13T17:00:18Z
dc.date.available 2017-02-13T17:00:18Z
dc.date.issued 2016
dc.identifier.uri http://hdl.handle.net/123456789/4423
dc.description.abstract In this dissertation, three NP-hard min-max discrete optimization problems are considered. The rst considered problem is multi-period emergency service location problem, the second one is dynamic maximal covering location problem with multiple covering radii, and the third one is uncapacitated multiple allocation p-hub center problem. In many practical situations, input parameters (such as user demands, transportation time or cost) often vary with unknown distributions. Therefore, it is necessary to involve these uncertainties in the deterministic variants of the problems by applying robust optimization approach. Mathematical models for the deterministic and non-deterministic variants of all three problems are developed, except for the deterministic uncapacitated multiple allocation p-hub center problem, which has already been addressed in the literature. In addition, for the rst time in the literature, it was proven that the emergency service location problem is NP-hard. The considered problems and their robust variants have numerous applications, due to the fact that in real-life situations input parameters are often subject to uncertainty. Multi-period emergency service location problem may be used when determining optimal locations for police stations, re brigades, ambulances, and other emergency units in the given region. The dynamic maximal covering location problem with multiple covering radii is useful when choosing the optimal strategy for establishing resources (service centers, suppliers, facilities, etc.) with maximal satisfaction of customer demands in a certain region, by assuming that the service e ciency directly depends on the distance between customer and service center (i.e., the selected coverage radius). The uncapacitated multiple allocation p-hub center problem has signi cant applications in designing telecommunication and transportation networks, postal delivery systems, emergency systems, supply networks, etc. Since exact methods provide optimal solutions only for problem instances of small dimensions, hybrid metaheuristic algorithms are developed to solve both deterministic and robust variants of the considered problems. The proposed hybrid algorithms are obtained by combining particle swarm optimization, with local search heuristic { classical local search or variable neighborhood search method. For dynamic maximal covering location problem with multiple covering radii, a hybridization of metaheuristic algorithm with exact method based on linear programming is developed. All elements of the proposed algorithms are adopted to the problems under consideration. Di erent strategies are implemented for improving the e ciency of proposed algorithms, especially for the calculation of the objective function value and the local search part. The in uence of di erent parameters of hybrid algorithms on the solution quality is analyzed in detail. All parameters are adjusted by using analysis of variance. For all considered problems (both deterministic and robust variant), the performance of the proposed hybrid algorithms is evaluated on adequate test data sets. The proposed algorithms are compared with existing heuristic from the literature and exact methods incorporated in commercial CPLEX solver. The obtained experimental results indicate the e ciency of proposed algorithms in obtaining high quality solutions for all considered test instances. The presented comparative analysis indicates the advantages of the proposed hybrid algorithms over existing methods in the sense of solution quality and/or required computational time, especially in the case of large problem dimensions. The results presented in this paper represent a contribution to the eld of discrete optimization, robust optimization and metaheuristic methods. en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2017-02-13T17:00:18Z No. of bitstreams: 1 Miskovic_Stefan_teza.pdf: 1773429 bytes, checksum: 8cb22e54244662c7db2f8a7966309f6a (MD5) en
dc.description.provenance Made available in DSpace on 2017-02-13T17:00:18Z (GMT). No. of bitstreams: 1 Miskovic_Stefan_teza.pdf: 1773429 bytes, checksum: 8cb22e54244662c7db2f8a7966309f6a (MD5) Previous issue date: 2016 en
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title REŠAVANJE KLASE MIN-MAX PROBLEMA ROBUSNE DISKRETNE OPTIMIZACIJE SA PRIMENAMA en_US
mf.author.birth-date 1987-12-29
mf.author.birth-place Čačak en_US
mf.author.birth-country Srbija en_US
mf.author.residence-state Srbija en_US
mf.author.citizenship Srpsko en_US
mf.author.nationality Srbin en_US
mf.subject.area Computer science en_US
mf.subject.keywords discrete optimization, robust optimization, min-max problems, metaheuristic methods en_US
mf.subject.subarea Optimization en_US
mf.contributor.committee Živković, Miodrag
mf.contributor.committee Marić, Miroslav
mf.contributor.committee Davidović, Tatjana
mf.university.faculty Mathematical Faculty en_US
mf.document.references 163 en_US
mf.document.pages 128 en_US
mf.document.location Beograd en_US
mf.document.genealogy-project No en_US
mf.university Belgrade University en_US

Dateien zu dieser Ressource

Dateien Größe Format Anzeige
Miskovic_Stefan_teza.pdf 1.773Mb PDF Öffnen

Das Dokument erscheint in:

Zur Kurzanzeige