Robustné modely v distribučných úlohách
Autor práce: RNDr. Zuzana BorčinováŠkoliteľ: doc. RNDr. Štefan Peško, CSc.
Dátum obhajoby: 21.8.2019
Študijný program: 9.2.9 Aplikovaná informatika
Oponent 1: prof. Ing. Ivan Brezina, CSc.
Oponent 2: doc. Ing. Dušan Teichmann, Ph.D.
Slovenský abstrakt:
Distribuˇcné úlohy súvisia s riadením prepravy tovaru a distribúcie služieb od dodávatel’ov
k odberatel’om. Zvyˇcajne sa predpokladá, že všetky vstupné údaje (prepravné náklady,
ˇcas obsluhy, požiadavky a pod.) sú v ˇcase plánovania presne známe. V praxi však tieto dáta
ˇcasto bývajú neisté v dôsledku ich náhodnej povahy, výskytu chýb merania alebo z iných dôvodov.
Neisté dáta môžu spôsobit’, že navrhnuté riešenie sa stane neprípustným. Robustná
optimalizácia hl’adá riešenie, ktoré je imúnne voˇci neistým vstupným údajom, za predpokladu,
že rozdelenie pravdepodobnosti nie je známe. Namiesto toho predpokladáme, že neisté
dáta patria ohraniˇcenej množine neurˇcitostí. Ciel’om robustnej optimalizácie je nájst’ najlepšie
riešenie, ktoré je prípustné pre ich všetky možné hodnoty z tejto množiny. V tejto práci sa
zaoberáme na robustnou okružnou dopravnou úlohou, v ktorej majú byt’ zákazníci s neistými
požiadavkami obslúžení vozidlami s rovnakou kapacitou sústredenými v depe. Navrhli sme
tri stratégie, ktoré pre danú množinu neurˇcitostí hl’adali riešenie s minimálnymi neuspokojenými
požiadavkami a minimálnymi prepravnými nákladmi. Dosiahnuté experimentálne výsledky
ukázali, že nájdené robustné riešenia dokážu minimalizovat’ neuspokojené požiadavky
zákazníkov, priˇcom ich cena je len o málo väˇcšia, než cena optimálneho deterministického
riešenia.
Kl’úˇcové slová: robustná optimalizácia, kapacitná okružná dopravná úloha, neisté požiadavky
zákazníkov, celoˇcíselné a zmiešané lineárne programovanie, paralelný mikrogenetický algoritmus
Anglický abstrakt:
Distribution problems are concerned with the transfer of goods or services between manufacturing
facilities, distribution centers and customers. Usually, we assume that input data
(transportation costs, service times, demands etc.) is precisely known at the time ofproblem
solving. However, in many real-life applications data are subject to uncertainty due to their
random nature, measurement errors or other reasons. This random behavior of the problem
data could cause the proposed feasible solution to become infeasible. Robust optimisation
seeks the solution that is immune to this uncertainty under assumption that probability distribution
is unknown. Instead we assume that the uncertain problem parameters belong to
bounded uncertainty set. The objective of robust optimisation is to find the best solution
which is feasible for any realization of the data from the given uncertainty set. In this work
we consider the robust capacitated vehicle routing problem in which a set of uncertain customers’
demands has to be served by a fleet of homogenous vehicles departing from a depot.
We proposed three robust strategies which aim to minimise transportation costs and unsatisfied
demands for the specific uncertainty set. Our experimental results show that obtained
solutions can minimise unmet demands while incurring a small extra cost over deterministic
optimal solution.
Keywords: robust optimisation, capacitated vehicle routing problem, uncertain customers’
demands, integer and mixed linear programming, parallel micro genetic algorithm
Autoreferát dizertačnej práce
Text práce