Naslov (srp)

Primena fazi logike za rešavanje NP-teških problema rutiranja vozila i lokacije resursa metodama računarske inteligencije

Autor

Radojčić, Nina, 1987-

Doprinosi

Marić, Miroslav, 1978-
Marić, Miroslav, 1978-
Pavlović-Lažetić, Gordana, 1955-
Stanimirović, Zorica, 1976-
Takači, Aleksandar, 1976-

Opis (srp)

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...

Opis (srp)

Računarstvo-Računarska inteligencija / Computer Science-Computational intelligence Datum odbrane: 11. 6. 2018. null

Opis (eng)

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...

Jezik

srpski

Datum

2018

Licenca

© All rights reserved