Title
Primena fazi logike za rešavanje NP-teških problema rutiranja vozila i lokacije resursa metodama računarske inteligencije
Creator
Radojčić, Nina, 1987-
Copyright date
2018
Object Links
Select license
Bez licence - direktna primena zakona
License description
Ako ne izaberete neku od licenci, vaše zaštićeno delo može biti korišćeno samo u okviru opštih ograničenja autorskih prava. Na taj način ne dozvoljavate komercijalno ni nekomercijalno korišćenje, naročito reprodukciju, distribuciju, emitovanje, dostupnost i obradu dela. Izbor Creative Commons (CC) licence promoviše diseminaciju vašeg dela. Za više informacija: http://creativecommons.org.rs/licence
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Datum odbrane: 11. 6. 2018.
Other responsibilities
mentor
Marić, Miroslav, 1978-
član komisije
Marić, Miroslav, 1978-
član komisije
Pavlović-Lažetić, Gordana, 1955-
član komisije
Stanimirović, Zorica, 1976-
član komisije
Takači, Aleksandar, 1976-
University
Univerzitet u Beogradu
Faculty
Matematički fakultet
Alternative title
Analysis of the incident energy anular distribution of ambiental noise by microphone array
Publisher
[N. Radojčić]
Format
XII, 140 listova
description
Računarstvo-Računarska inteligencija / Computer Science-Computational intelligence
Abstract (sr)
U okviru ove disertacije, tri NP-teˇska problema su razmatrana i reˇsavana razliˇcitim
metodama raˇcunarske inteligencije, sa posebnim akcentom na mogu´cnosti upotrebe
fazi logike za poboljˇsanje performansi metoda. Pored toga prikazana je i mogu´cnost
koriˇs´cenja fazi logike u cilju kreiranja modela koji odgovaraju problemima u praksi.
Prvi problem razmatran u disertaciji je problem rutiranja vozila sa ograniˇcenim
rizikom (engl. Risk-constrained Cash-in-Transit Vehicle Routing Problem - RCTVRP).
RCTVRP predstavlja specijalan sluˇcaj problema rutiranja vozila (VRP).
Kao i kod klasiˇcnog problema VRP, potrebno je da vozila obidu sve klijente tako
da na kraju ukupan predeni put (ili troˇskovi putovanja) bude ˇsto manji. Kod RCTVRP
problema uzima se u obzir i sigurnosni aspekt ruta. Ovaj problem se pojavio
u sektoru koji se bavi prenosom novca i robe od velike vrednosti.
Druga dva problema koja su predmet ove disertacije spadaju u grupu lokacijskih
problema: problem ravnomernog optere´cenja (engl. Load Balancing Problem
- LOBA) i problem maksimizacije minimalnog rastojanja (engl. Max-Min Diversity
Problem - MMDP). LOBA predstavlja diskretni lokacijski problem kod kojeg
je potrebno odabrati snabdevaˇce tako da budu ravnomerno optere´ceni od strane
pridruˇzenih korisnika. Cilj je odrediti skup od odredenog broja snabdevaˇca iz skupa
potencijalnih snabdevaˇca koji ´ce biti uspostavljeni tako da je minimizovana razlika
izmedu najve´ceg i najmanjeg broja korisnika dodeljenih nekom uspostavljenom snabdeva
ˇcu. Ovaj problem se ˇcesto javlja u praksi, na primer, prilikom rasporedivanja
antena za mobilne telefone, ˇskola, izbornih jedinica ili centara za prikupljanje ˇcvrstog
otpada. Problem MMDP je diskretni lokacijski problem kod koga je cilj odabrati
podskup od taˇcno odredenog broja elemenata datog skupa tako da je najmanje rastojanje
izmedu odabranih elemenata maksimalno. MMDP potiˇce iz situacija iz
prakse, na primer, kada je potrebno rasporediti postrojenja tako da ne postoje dva
postrojenja koja su previˇse blizu. MMDP ima primene i u druˇstvenim i bioloˇskim
naukama (na primer u cilju oˇcuvanja ekologije).
U cilju reˇsavanja RCTVRP, GRASP (Greedy Randomized Adaptive Search Procedure)
metod je hibridizovan sa metodom ponovnog povezivanja puta (engl. Path
Reliking - PR). Paˇzljivo odredena fazi modifikacija je implementirana u predloˇzeni
GRASP metod u cilju poboljˇsanja performansi prilikom reˇsavanja RCTVRP problema.
Dodatno, u ovoj disertaciji je predloˇzena nova struktura za PR metod koja
se moˇze primeniti za reˇsavanje drugih problema rutiranja vozila. U cilju smanjenja
vremenske sloˇzenosti predloˇzenog algoritma, implementirana je nova struktura podataka
za RCTVRP. Predloˇzeni fazi GRASP algoritam hibridizovan sa PR metodom
daje bolje rezultate u poredenju sa hibridnom verzijom bez fazi modifikacije. Pored
toga, eksperimentalni rezultati na javno dostupnim test primerima ukazuju da
predloˇzeni metod nadmaˇsuje sve metode koje su do sada primenjivane u dostupnoj
literaturi na RCTVRP problem...
Abstract (en)
In this dissertation, three NP-hard optimization problems are studied and various
computational intelligence methods are considered for solving them, with a
special emphasis on the possibilities of applying fuzzy logic in order to improve the
performances of proposed methods. In addition, it is shown how fuzzy logic can be
incorporated into a model to make it more adequate to real world applications. The
first problem considered is the Risk-Constrained Cash-in-Transit Vehicle Routing
Problem (RCTVRP) that represents a special case of the vehicle routing problem
(VRP). Similar to the classical VRP, the aim is to determine the collection routes
from one depot to a number of customers in order to minimize the overall travel
distance (or cost). Additionally, the safety aspect of the routed risk constraints
are introduced in the case of RCTVRP. The RCTVRP concerns the issue of security
during the transportation of cash or valuable goods (e.g. in the cash-in-transit
industry).
The other two problems studied in this dissertation belong to the class of location
problems: the Load Balancing Problem (LOBA) and the Max-Min Diversity
Problem (MMDP). The goal of the LOBA problem is to locate a fixed number of
facilities, such that the difference between the maximum and minimum number of
customers served by each facility is balanced. The LOBA model is useful in cases
where customers naturally choose the closest facility. The MMDP consists of selecting
a subset of a fixed number of elements from a given set in such a way that
the diversity among the selected elements is maximized. This problem also arises
in real world situations encompassing a variety of fields, particularly the social and
biological sciences.
In order to solve the RCTVRP, a fuzzy GRASP (Greedy Randomized Adaptive
Search Procedure) is hybridized with Path Reliking (PR) methodology. Carefully
adjusted fuzzy modification incorporated into the proposed GRASP for the RCTVRP
improved its performance. Moreover, in this dissertation a new PR structure
is implemented and can be used for other vehicle routing problems. To improve
the algorithm’s time complexity, a new data structure for the RCTVRP is incorporated.
The proposed fuzzy GRASP with PR hybrid shows better computational
performance compared to its non-fuzzy version. Furthermore, computational results
on publicly available data sets indicate that the proposed algorithm outperforms all
existing methods from the literature for solving the RCTVRP...
Authors Key words
raˇcunarska inteligencija, metaheuristike, fazi logika, NP-tåˇski problemi,
kombinatorna optimizacija
Authors Key words
computational intelligence, metaheuristics, fuzzy logic, NP-hard problems,
combinatorial ptimization
Classification
519.8:004.832.28(043.3)
Type
Tekst
Abstract (sr)
U okviru ove disertacije, tri NP-teˇska problema su razmatrana i reˇsavana razliˇcitim
metodama raˇcunarske inteligencije, sa posebnim akcentom na mogu´cnosti upotrebe
fazi logike za poboljˇsanje performansi metoda. Pored toga prikazana je i mogu´cnost
koriˇs´cenja fazi logike u cilju kreiranja modela koji odgovaraju problemima u praksi.
Prvi problem razmatran u disertaciji je problem rutiranja vozila sa ograniˇcenim
rizikom (engl. Risk-constrained Cash-in-Transit Vehicle Routing Problem - RCTVRP).
RCTVRP predstavlja specijalan sluˇcaj problema rutiranja vozila (VRP).
Kao i kod klasiˇcnog problema VRP, potrebno je da vozila obidu sve klijente tako
da na kraju ukupan predeni put (ili troˇskovi putovanja) bude ˇsto manji. Kod RCTVRP
problema uzima se u obzir i sigurnosni aspekt ruta. Ovaj problem se pojavio
u sektoru koji se bavi prenosom novca i robe od velike vrednosti.
Druga dva problema koja su predmet ove disertacije spadaju u grupu lokacijskih
problema: problem ravnomernog optere´cenja (engl. Load Balancing Problem
- LOBA) i problem maksimizacije minimalnog rastojanja (engl. Max-Min Diversity
Problem - MMDP). LOBA predstavlja diskretni lokacijski problem kod kojeg
je potrebno odabrati snabdevaˇce tako da budu ravnomerno optere´ceni od strane
pridruˇzenih korisnika. Cilj je odrediti skup od odredenog broja snabdevaˇca iz skupa
potencijalnih snabdevaˇca koji ´ce biti uspostavljeni tako da je minimizovana razlika
izmedu najve´ceg i najmanjeg broja korisnika dodeljenih nekom uspostavljenom snabdeva
ˇcu. Ovaj problem se ˇcesto javlja u praksi, na primer, prilikom rasporedivanja
antena za mobilne telefone, ˇskola, izbornih jedinica ili centara za prikupljanje ˇcvrstog
otpada. Problem MMDP je diskretni lokacijski problem kod koga je cilj odabrati
podskup od taˇcno odredenog broja elemenata datog skupa tako da je najmanje rastojanje
izmedu odabranih elemenata maksimalno. MMDP potiˇce iz situacija iz
prakse, na primer, kada je potrebno rasporediti postrojenja tako da ne postoje dva
postrojenja koja su previˇse blizu. MMDP ima primene i u druˇstvenim i bioloˇskim
naukama (na primer u cilju oˇcuvanja ekologije).
U cilju reˇsavanja RCTVRP, GRASP (Greedy Randomized Adaptive Search Procedure)
metod je hibridizovan sa metodom ponovnog povezivanja puta (engl. Path
Reliking - PR). Paˇzljivo odredena fazi modifikacija je implementirana u predloˇzeni
GRASP metod u cilju poboljˇsanja performansi prilikom reˇsavanja RCTVRP problema.
Dodatno, u ovoj disertaciji je predloˇzena nova struktura za PR metod koja
se moˇze primeniti za reˇsavanje drugih problema rutiranja vozila. U cilju smanjenja
vremenske sloˇzenosti predloˇzenog algoritma, implementirana je nova struktura podataka
za RCTVRP. Predloˇzeni fazi GRASP algoritam hibridizovan sa PR metodom
daje bolje rezultate u poredenju sa hibridnom verzijom bez fazi modifikacije. Pored
toga, eksperimentalni rezultati na javno dostupnim test primerima ukazuju da
predloˇzeni metod nadmaˇsuje sve metode koje su do sada primenjivane u dostupnoj
literaturi na RCTVRP problem...
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.