Prihlásenie

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

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