Geliştirilmiş SPEA2 ile Envanter Probleminin Çözümü

Abstract

Optimizasyon problemleri hemen hemen her ticari ve akademik disiplini ilgilendirmektedir. Optimizasyon probleminin tanımı, belirli kısıtlar altında belirli karar değişkenlerinin değerlerini tayin ederek bir amaç fonksiyonunun optimize etmektir. Bu problemlerin bir türü de envanter optimizasyonudur. Envanter optimizasyonu, herhangi bir envantere sahip olan tüm ticari kuruluşlar için büyük önem taşımaktadır. Öyle ki, envanter optimizasyonu direkt olarak finansal kazanca ve müşteri memnuiyetine etki etmektedir. Bunu yanı sıra envanter optimizasyonu tedarik zincirinin diğer alanlarıyla etkileşim halindedir. Üretim biriminden ham madde temin etmek, ambar yerleri ile sayısını belirlemek, ulaşım türleri, tedarikçi seçimi, genel orta vade üretim planı, promosyon seçimi bu alanların bazılarıdır. Matematiksel olarak modellenmiş olan farklı envanter problemlerinin farklı amaç fonksiyonları, kısıtlamaları ve karar değişkenleri vardır. Giderleri minimize etmek, karı maksimize etmek, envanter yatırımlarında gelen kar dönüş oranını maksimize etmek, bir parametre için tek bir mükemmel sonuç elde etmek bunlardan bazılarıdır. Ayrıca envanter üzerindeki insan kontrol faktörünün optimal değerini bulmak, belirsiz bir gelecekte zarara uğramamak için belirli bir esneklik derecesine sahip olmak, kurum içindeki politik anlaşmazlıkları minimize etmek, bazı yöneticilerin kurum içindeki yerini garanti altına almak gibi amaç fonksiyonlarıda olabilir. Envanter optimizasyonundaki kısıtlamalar ise tedarikçi, pazarlama veya şirket iç politikalarından kaynaklanmaktadır. Maksimum sipariş miktarı, optimum müşteri memnuniyeti, maksimum iş gücü bu kısıtlamara bazı örneklerdir. Karar değişkenleri ile kısıtlamar arasında mutlak bir çizgi yoktur. Bazı envanter modellerindeki kısıtlamalar diğer modellerde karar değişkeni olabilmektedir. Bir ürünün fiyatına veya sipariş miktarına karar vermek, karar değişkeni olarak modellenebilir.Envater problemleri matematiksel olarak modellenirken amaç sayısı, dönem sayısı, ürün sayısı gibi parametreleri dikkate alınır. Bu tez çalışmasında üç farklı envanter modeli üstünde deneyler yapılmıştır. İlk model çok amaçlı tek dönemli çok ürünlü bir modeldir. İkinci modelin çok amacı tek dönemi ve tek ürünü vardır. Üçüncü model ikinci modelin çok ürünlü türevidir. Bu üç model gerçek hayatta, birden çok bozulabilir ürüne sahip olan süpermarket envanterlerini, bir sezon sonunda modası geçen ürünlere sahip butiklerin envanterlerini ve yeni teknolojilerin gelişmesiyle işe yaramaz hale gelen son teknoloji ürünlerinden oluşan envanterleri kapsamaktadır. Bu sebepten ötürü bu çalışmada modellenen envanterler, gerçek hayatta kullanılan envanterlerin büyük bir çoğunluğunu temsil etmektedir.Bu modeller farklı veri setlerine göre, farklı parametrelerle, farklı optimizasyon algoritmlarına göre çözülmüşlerdir. Bu problemlerin çözümünde en popüler yöntemler, metasezgisel algoritmalar ailesine ait olan evrimsel algoritmalardır. Bilim dünyasında en güvenilen ve saygı duyulan evrimsel algoritmalar SPEA ve NSGA ailesine ait olan algoritmlardır. Bu sebepten dolayı, bu çalışmada bu ailelere ait olan algoritmalar kullanılmıştır. Bu algoritmaların performansları belirli performans metrikleri ile karşılaştırılmıştır. Öncelikle ilk envanter modeli, bu ailelerin en yeni versiyonları olan SPEA2 ve NSGA-III algoritmları ile çözülmüştür. Algoritmların bu problem üstünde gösterdiği performans, üç performans metriği ile ölçülmüştür. Karşılaştırma sonucu SPEA2'nin daha iyi bir performans sergilediği gözlemlenmiştir. Bunun üzerine SPEA2'nin geliştirilip envanter optimizasyonunun çözümünde kullanılmasına karar verilmiştir. NSGA-II algoritması da yeni SPEA2 ile kıyaslanması amacıyla geliştirilip daha iyi hale getirilmiştir. İkinci ve üçüncü envanter modelleri yeni SPEA2, yeni NSGA-II, SPEA2, NSGA-II ve bir sürü algoritması olan OMOPSO ile çözülmüştür. Çözüm işlemleri farklı iterasyon ve popülasyon sayıları için 10'ar kez gerçekleştirilmiştir.Bu üç problemin yanı sıra algoritmalar üç farklı test problemi üzerinde denemiştir. Algoritmların gösterdiği performansın ölçülmesi için aynı performans metrikleri kullaılmıştır. Karşılaştırma sonuncunda geliştirilmiş SPEA2 algoritmasının her problemin her çözümü için diğer algoritmalarda daha iyi performans sergilediği gözlenmiştir. Geliştirilmiş NSGA-II ise geliştirilmiş SPEA2 algoritmasından sonra en iyi performansı sergilemiştir. Bu deney sonucunda geliştirilmiş SPEA2 algoritmasının çok amaçlı envanter optimizasyonu için en uygun çözüm olduğu görülmüştür.En sonunda, geliştirilmiş olan SPEA2 algoritması gerçek bir problem üzerinde denenmiştir. Bu problem çok amaçlı tek dönemli çok ürünlü bir modeldir. Bu envantere sahip olan firma herhangi bir optimizasyon yöntemi kullanmamaktadır. Optimizasyon firmanın bir satış dönemi için yapılmıştır. Dönem başında optimizasyon yapılmadan elde edilecek karar değişkeni değerleri kaydedilmiştir ama uygulamaya konmamıştır. Optimizasyon yapılarak bulunan karar değişkenleri gerçek hayatta uygulamaya konulmuştur. Dönem sonunda optimize edilen envanterin karı ile envanter optimize edilmemiş olsaydı elde edilecek olan kar karşılaştırılmıştır. Bu karşılaştırma sonucunda gözlenen, geliştirilmiş SPEA2 algoritması ile yapılan optimizasyonun, optimizasyon yapılmamasından daha karlı olduğudur. Elde edilen bu kar oranı günümüz ticari şartları bakımından büyük bir orandır.

Optimization problem holds importance for almost all scientific and trade disciplines. By definition, optimization problem is maximizing or minimizing an objective function under constraints with certain decision variables. Optimization problems may or may not have constraints and they may have one or more objective functions. Optimization problems with more than one objective function are known as a multi-objective optimization problems. Obtimization problems with more than or equal to three objectives are known as many-objective optimization problems. While it is possible for a single objective problem to have a single best answer, solving a multi-objective function is a more complicated task. Multi-objective optimization problems generally have more than one correct solution for each decision varibale. Therefore, Pareto optimization concept is used for deciding the correct solutions for the optimization problem.A Pareto solution is a solution which cannot be further improved for an objective without detoriating another one. Typically, while solving a multi-objective problem the algorithm yields numerous Pareto solutions. Then the decision maker decides which solution or solutions are going to be used. Statistical methods like TOPSIS are common techniques used by the decision maker to order the Pareto solutions. The algorithm which is used to solve the problem generates the values for the decision variables and the objective functions. The values yielded for the decision variables are known as the Pareto optimal set. The values yielded for the objective functions are known as the Pareto front. Multi-objective inventory problems are no exception to the structure described above. They have multiple objective functions, decision variables and constraints. When they are solved, multiple Pareto solutions are yielded. Inventory problems hold great significance to inventory managers because they are directly tied to financial gains and customer satisfaction. Moreover the inventory problem often interacts with other areas of operational research. Investing in raw materials, production rate, service and maintenance activities, warehouse specifications, trasportation, pricing and choosing the suppliers are among these areas. The objective functions for inventory problems include but are not limited to are maximizing the profit, minimizing losses, maximizing service rate and customer satisfaction. The constraints may depend on the supplier, internal politics, or marketing limitations. Limits to order sizes are supplier constraints. Tolerable service level is the most important marketing constraint. Budget and workload constraints are some of the most important internal constraints. While designing a model for the inventory problem at hand, there are some classifications to be considered. The inventory model may have single or multiple objectives. Products may be perishable or their shelf-life may be unlimited. There may be multiple products or a single product. The model may have a single period or it may span multiple periods. In a multiple period model, the items in stock may carry over to the next period or they may become obsolote at the end of a single period. The demand for products may be deterministic or stochastic. There may be single or multiple warehouse locations. The order cost may or may not depend on the size of the order and so on.In this study, three different inventory models are designed. The first model is a multi-objective single-period multi-item inventory model. Its objectives are maximizing the profit and warehouse occupancy level. Warehouse lavel and ordering budget are constraints. Order size is the decision variable. The objectives for the second model are maximizing the profit and service level. Order amount and selling price are the decision variables. There are constraints on the order amount and the selling price. The third model is identical to the second model except it has multiple items. These three models correspond to retail stores with multiple perishable items or garment stores with items which goes out of style at the end of each period. It can also cover some specific high technology items which can become obsolote with the emerging of new technologies. Therefore, the models presented in this paper cover most of the inventory models encountered in real life.Inventory problems and other optimization problems are traditionally solved with metaheuristic optimization algorithms. They can also be solved with exact algorithms or specific heuristics but metaheuristics, especially evolutionary algorithms are known to perform better. Metaheuristic algorithms can be classified into solution based or population based algorithms. Solution based algorithms include local search and simulated annealing methods. Local search algorithms may have a hard time finding the globally optimum solutions while simulated annealing methods may not yield a diverse set of solutions. Simulated annealing also has an asymptotic time complexity Therefore as the number of objectives and decision variables increase, time complexity increases exponentially. Swarm based algorithms and tabu search algorithms are the two other main subdivisions of population based algorithms other than evolutionary algorithms. Tabu search displays poorer performance as the number of objectives increases and has a hard time searching continuous search spaces. It also has a higher time and space complaxity compared to other methods. This makes it a poor candidate for hybridization with other algoirthms. Swarm based algorithms do not allow for much parameter manipulation. They also need to run multiple times for yielding a good solution and even then they may not reach the true Pareto front. These reasons has lead to evolutionary algorithms to be preferred over other optimization algorithms.There are three kinds of evolutionary algorithms: Pareto based, indicator based and decomposition based algorithms. Indicator based algorithms search towards the parts of the solution plane with the guidance of a performance indicator based metric. Their most important disadvantage is their fastly growing time complexity as the number of the objective functions increases. Since most of the metrics use a reference set to compare the performance of the algorithm, indicator based algoirhtms may perform poorly according to the choice of the reference points. IBEA, HypE, MO-CMA-ES are some of the indicator based algorithms. Decomposition based algorithms require a priori based knowledge. Since they use aggregation techniques, the number of weights used increase exponentially. NSGA-III and MOEA/D are some of the decomposition based algorithms. Pareto based algorithms are very practical beacuse they require only a few paramteres and can work with large number of objectives without any problems.The main working mechanism of all the Pareto based algorithms are similar. They use a two step selction mechanism. First, the solutions are chosen according to their Pareto dominance and then they are selected based on the density of solutions on the search plane. NSGA-II and SPEA2 are regarded as the two benchmark Pareto based algorithms. Therefore, in this study algorithms belonging to SPEA and NSGA family are researched.SPEA2 algorithm has a strength based selection mechanism A solution's strength is the number of other solutions it dominates. The fitness of a solution is calculated with regards to the number of solutions it dominates and the strength of the solutions it is dominated by. Also SPEA2 keeps an archive of nondominated solutions for carrying them on to the next generation. The archive size is fixed. If the number of nondominated solutions exceed the archive limit, a truncation operator eliminates some of the solutions. If there are vacant spots in the archive, then they are filled with the best dominated solutions. Moreover, SPEA2 uses a spreading preservation mechanism which eliminates solutions form the most crowded parts of the solution space. This causes the algorithm to have a better spread value.The main distinct feature of NSGA-II is its nondominated sorting mechanism. After the evaluation of solutions with regards to the objective functions, the algotihm sorts the solutions according to their fitness values. Then the solutions are sorted into layers according to their fitness values. The nondominated solutions form the first layer, the best group of dominated solutions form the second layer, the second best group of nondominated solutions form the third layer and so on. Selection is made with bias towards the better layers. The selection mechanism is based on binary tournament selection. As in other evolutionary algorithms, NSGA-II has recombination and mutation operators.The performance of multi-objective evolutionary algorithms are measured using specialized metrics. These metrics usually work on the basis of the convergence or diversity of the obtained solutions. For a better performance assesment, metrics which measure the diversity and the convergence of the solutions should be used together. The metrics can further be classified as unary and binary metrics. Unary metrics are measured indepenedently of the other algorithm being compared. Binary metric compares two or more algorithm based on their performance for solving a single problem. Using one unary metric for each objective function is enough for a good performance estimation. Hypervolume, generational distance and spacing are used in this study. Hypervolume works by calculating the size of the solution space dominated by the obtained solutions. It measures both the convergence and the diversity of the solutions. Generational distance measures the Euclidian distance between solutions and therefore it is a convergence metric. Spacing measures the spread of solutions across the solution space. It is a diversity metric. All three of these metrics ar unary metrics.In the first part of the study a multi-objective singe-period multi-item objective function is modeled. Then the model is solved with SPEA2 and NSGA-III for 10000 iterations for 10 consecutive times. The two algorithms are compared according to their hypervolume, generational distance and spacing values.The results display that SPEA2 perfoms better than NSGA-III. Therefore, the second half of the study is focused on SPEA2.In the second part of the study, SPEA2 algorithm is improved with modifications made on its truncation, selection and reproduction schemes. Similar improvements on NSGA-II have been made for comparison purposes. The improved algorithms along with SPEA2, NSGA-II and OMOPSO which is a swarm based algorithm are compared. The comparative analysis is made based upon the performance they display on three test problems and two inventory models. The test problems used are Fonseca, Binh and WFG problems. The first inventory model is a multi-objecive single-period single-item inventory model with profit and service level maximization as objectives. There are constraints on both of these objectives and the decision variables are order amount and selling price. The second model is the same as the first model but the latter has multiple items. The problems where solved with the novel SPEA2, the novel NSGA-II, SPEA2, NSGA-II and OMOPSO algorithms. The problems were solved for 1000, 5000, 10000 population sizes for 10 times with 1000 iterations. Hypervolume, generational distance and spacing metrics are measured for each algorithm. The results display that the novel SPEA2 outperforms the other four algorithms in every problem instance. Also, the novel NSGA-II perfoms worse than the novel SPEA2 but performs better than the other three algorithms.In the last part of the study, the novel SPEA2 algorithm, with its proven success, is applied to a real world inventory optimization problem. It is a multi-objective single-period multi-item inventory problem. The problem has two objectives, one constraint and one decision variable. The inventory managers aim to find the optimal order amount without exceeding the warehouse capacity for maximizing the profit and the service rate. The optimization algortithm is applied for one period. At the beginning of the period the order amount is decided with the help of an improved SPEA2 based application. The order amount which would have been made without the help of the optimization application is also recorded. At the end of the period the real profit and the would have been profit are compared. It is observed that the optimized profit is greater than the unoptimized profit by a large margin.