Problem rutiranja sa zalihama: modeliranje i analiza performansi

Abstract

Problem rutiranja sa zalihama (IRP, engl. Inventory Routing Problem) je relativno nova oblast koja osvaja sve više pažnje u poslednjih nekoliko godina u međunarodnoj istraživačkoj zajednici. Ova doktorska disertacija predstavlja rezultat višegodišnjeg istraživanja na temu IRP‐a, a čiji je naučni doprinos potvrđen sa dva rada publikovana u referentnim međunarodnim časopisima (Popović i ostali 2012, Vidović i ostali 2014). Takođe, po saznanjima kandidata, IRP do sada nije posmatran u Srbiji od strane drugih istraživača što dodatno ukazuje na značaj ove doktorske disertacije (pogotovu što je IRP koncept praktično primenljiv u Srbiji). IRP se može posmatrati kao nadogradnja problema rutiranja vozila gde se istovremeno uzima u obzir i upravljanje zalihama, obično u planskom periodu od više dana. Osnovni preduslov za primenu IRP‐a jeste koncept upravljanja zalihama od strane snabdevača (VMI, engl. Vendor Managed Inventory), a koji podrazumeva primenu modernih informaciono komunikacionih tehnologija. Cilj ove doktorske disertacije jeste sagledavanje različitih koncepata IRP‐a, kao i modeliranje jedne klase IRP‐a u kojoj se koriste vozila sa podeljenim tovarnim prostorom (komorama). Kao rezultat predloženih modela IRP‐a dobija se plan distribucije u nekom planskom periodu, odnosno količinu robe koja se isporučuje (iz jednog depoa ka više korisnika) po danima planskog perioda sa rutama kretanja vozila, pri čemu se minimizuju ukupni troškovi rutiranja vozila i posedovanja zaliha. U doktorskoj disertaciji je predstavljen matematički model linearnog programiranja (MILP, engl. mixed integer linear programming) za dobijanje optimalnog rešenja instanci malih dimenzija. IRP je NP težak problem (NP, engl. Nondeterministic Polynomial time) i rešavanje realnih problema (instanci velikih dimenzija) primenom MILP modela nije moguće u prihvatljivom vremenu rada računara. Za potrebe rešavanja instanci velikih dimenzija, predstavljena je heuristika promenljivog pretraživanja okolina (VNS, engl. Variable Neighbourhood Search) koja se uspešno koristi za rešavanje različitih problema kombinatorne optimizacije. U predstavljenim modelima se koristi deterministička postavka IRP‐a Problem rutiranja sa zalihama: modeliranje i analiza performansi Dražen Popović (podrazumeva se deterministička potrošnja kod korisnika) radi pojednostavljena problema i omogućavanja dobijanja rešenja. U realnim sistemima, potrošnja ima stohastičan karakter i ovo pojednostavljenje može dovesti do neželjenih efekata, pre svega do nedostatka ili viška zaliha i do neplaniranih promena pri realizaciji plana isporuke. Analizu primenljivosti rešenja problema sa determinističkim ulazima na realan sistem sa stohastičkom prirodom moguće je izvršiti uz upotrebu simulacije, koja je takođe predstavljena u doktorskoj disertaciji. Na osnovu rezultata prikazanih u doktorskoj disertaciji, VNS heuristika daje rešenja bliska optimalnim za instance problema manjih dimenzija, sa prihvatljivim vremenom rada računara za instance svih dimenzija (vreme rada računara je manje od 10 minuta za rešavanje bilo koje instance). Takođe, predložena VNS heuristika se može efikasno koristiti za dobijanje plana distribucije u sistemu koji se bazira na VMI konceptu, pri čemu je moguća analiza kvaliteta (na osnovu skupa predloženih performansi) različitih struktura sistema distribucije. Prilikom sprovođenja simulacije, stohastička potrošnja ima za posledicu mogućnost pojave dva negativna događaja koja predstavljaju i dve dodatne performanse za ocenu kvaliteta rešenja: nedostatak zaliha usled neplanirano velike potrošnje, kao i potreba za hitnim isporukama radi dopune zaliha. Ključne reči: Uže naučne oblasti: "Rukovanje materijalom i eko logistika", "Industrijska logistika, lanci snabdevanja i skladišni sistemi". UDK brojevi: 621.86:519.8(043.3) 339.132.6:519.8(043.3)

Inventory Routing Problem (IRP) is a relatively new field that is gaining increasing attention in recent years by the international research community. This doctoral dissertation is the result of past several years of research on the subject of IRP, whose scientific contribution was confirmed with two papers published in international journals of high SCI value (Popovic et al. 2012, Vidovic et al. 2014). Also, to the best of our knowledge, IRP has not been observed in Serbia by other researchers which additionally indicate the importance of this doctoral dissertation (especially as the IRP concept is practically applicable in Serbia). IRP can be observed as an extension to the vehicle routing problem in a sense of taking into consideration the inventory management segment, usually in the planning horizon of several days. The basic prerequisite for the implementation of IRP is the Vendor Managed Inventory (VMI) concept, which implies the application of modern information and communication technologies. The aim of this doctoral dissertation is to review the different concepts of IRP, as well as modeling one class of IRP with vehicles that have compartments. Developed IRP models gives the solution in the form of distribution plan over a planning horizon, i.e. the amount of goods to be delivered (from one depot to multiple users) and vehicles' routes in each day of a planning horizon, while minimizing total cost of routing and inventories. In this doctoral dissertation, a mixed integer linear programming (MILP) model is developed to optimally solve the small scale problem instances. IRP is a NP (Nondeterministic Polynomial time) hard problem and solving real scale problems (large scale problem instances) using MILP model is not possible in acceptable computing time. For the purpose of solving large scale problem instances, original Variable Neighbourhood Search (VNS) heuristic model is developed. Both models use deterministic data input (consumption is assumed to be deterministic) to simplify the problem and enable the solving of the problem instances. In real systems, consumption has stochastic character and this Problem rutiranja sa zalihama: modeliranje i analiza performansi Dražen Popović simplification may lead to adverse effects, primarily as shortage or excess of inventories and unplanned changes in the realization of the delivery plan. Applicability analysis of the deterministic solutions to the real life case with stochastic nature can be made with the use of simulation, which is also presented in this doctoral dissertation. Based on the results shown in this doctoral dissertation, VNS heuristics provides solutions close to optimal for the small scale problem instances, while computational time for all instance is acceptable (less than 10 minutes to solve any instance). Also, the proposed VNS heuristics can be effectively used to obtain a distribution plan in a system which is based on the VMI concept, with quality analysis (based on a set of proposed performances) of different distribution system variants. In the proposed simulation, stochastic consumption can result in the possibility of two negative events which represent two additional performances for evaluating the quality of solutions: inventories shortage due to unplanned high consumption, and the need for urgent deliveries to minimize the inventories shortage.