Hipersezgisel yöntemlerle lojistik ağ tasarımı ve optimizasyon
Logistic network design and optimization using hyperheuristic methods
Yazar: VURAL EROL
Danışman: DOÇ. DR. MURAT BASKAK ; PROF. DR. GÜLGÜN KAYAKUTLU
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2017
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Tedârik Zinciri Yönetiminde en çok karşılaşılan problemlerden biri, Lojistik Ağ Tasarımı Problemidir. Bir işletmenin lojistik ağı, tedârikçiler, depolar, dağıtım merkezleri ve perakende mağazalarından ve bunlar arasındaki hammadde, ara ürün ve bitmiş ürün akışlarından oluşmaktadır.
Lojistik Ağ Tasarımı Probleminde genel olarak amaç, müşteri gereksinimleri karşılanırken aynı zamanda sabit mâliyetler ile satınalma, üretim, depolama ve taşıma gibi değişken mâliyetleri de enküçüklemeye çalışmaktır. NP-Zor problem kapsamında ele alınan Lojistik Ağ Tasarımı Problemi için sezgisel ve metasezgisel yöntemler, statik durumlarda etkin çözümler sunmaktadır. Hipersezgisel yöntemler ise problemden bağımsız teknikler olup, çözüm arama süreci ile problem uzayı arasında bir soyutlama sağlarlar.
Bir organizasyonun lojistik ağı, bir kuruluş için tedârikçi, üretim tesisleri, dağıtım merkezleri ve depolar arasındaki her türlü taşıma ve depolama işlemleri ile ilgilidir. Lojistik Ağ Tasarımı (LAT), işletmenin depo, dağıtım merkezi gibi noktalarının tedârikçi, üretim noktaları ve bayi, müşteri, toptancı gibi satış noktaları ile ilişkilendirilmesidir. Bu tez çalışmasında LAT problemleri İleri, Tersine ve Bütünleşik olmak üzere üç başlık altında incelenmiştir. İleri Lojistik Ağ Tasarımında hammadde ve ürünler tedârikçi, fabrika, dağıtım merkezi ve müşteri yoluyla ilerlemektedir. Tersine Lojistik Ağ Tasarımında ise ürün bu yönün tersi bir akışa sahip olup, Bütünleşik LAT'de her iki yöndeki hareket ele alınmaktadır.
Lojistik Ağ Tasarımı Problemleri dört boyutta değerlendirilebilir. Karar Düzeyi olarak stratejik, taktik ve operasyonel, İşlevler olarak lokasyon belirleme, araç rotalama, depo miktarı belirleme, araç sayısı hesaplama vb., Çözüm Yöntemleri olarak sürekli yakınlaştırma, kesin ve sezgisel yöntemler, Uygulama Alanlarına (Sektörler) göre ise otomotiv, lojistik, elektronik vb. olarak sınıflandırılabilir.
Bu tez çalışmasında Lojistik Ağ Tasarımı Problemi ve Hipersezgisel Algoritmalar ayrı başlıklar hâlinde anlatılmış ve literatür araştırmalarına ilişkin ayrıntılı sonuçlar açıklanmıştır. Çalışmada İleri Lojistik Ağ Tasarımı Problemi ile ilgili bir Karma Tamsayılı Programlama Modeli oluşturulmuştur. Lojistik Ağ Tasarımı Probleminde genel olarak amaç, müşteri gereksinimlerinin karşılanması koşuluyla tesislerin sabit mâliyetleri ve satınalma, üretim, depolama ve taşıma gibi değişken mâliyetlerin enküçüklemeye çalışılmasıdır. Problem oldukça geniş ve karmaşık olduğu için literatürde genel olarak belirli alt süreçlere ait problemler üzerinde çalışmalar yapılmıştır. Kurulan Karma Tamsayılı Programlama Modelinde temel olarak tedârikçi seçimi, tesis ve dağıtım merkezi aktifleştirilmesi, hangi fabrikanın, hangi tedârikçiden hammadde alacağı ve hangi dağıtım merkezine ürün göndereceği, müşterilere hangi dağıtım merkezi üzerinden hizmet edileceği ve dağıtım merkezi ile müşteriler arasındaki araç rotaları belirlenmeye çalışılmaktadır.
Günümüzde, özellikle ekonomik nedenlerden dolayı, gerçek yaşamda karşılaşılan ve optimizasyon gerektiren problemler oldukça önem kazanmıştır. Bu tür problemler için kesin modellemeler yapmak karmaşık ve ayrıntılı olduğundan ve aynı zamanda çözümü uzun süreler gerektirdiği için bunlar uygulanabilir değildir. Bu nedenlerle, optimum sonucu garanti etmeyen ancak uygun süreler içerisinde yürütülmesi kolay, fazla kaynak gerektirmeyen ve uygulanabilir çözümler üreten basit sezgisel yöntemlere başvurulmaktadır.
Metasezgisel Yöntemler son yıllarda başarısını kanıtlasa da, yürütülmesi oldukça zor, mâliyetli ve problem özelinde şekillendirilen tekniklerdir. Bir problem için yüksek kaliteli çözümler üreten bir Metasezgisel Algoritma, problemde birtakım değişiklikler yapıldığında başarısız olabilmektedir. Bu yüzden, gerçek yaşamda kullanılacak Metasezgisel yöntemlerin, bu değişikliğe uyum sağlamak üzere elden geçirilmesi gerekmektedir. Hipersezgisel Algoritmalar ise genelleştirilmiş, dayanıklı ve problemden bağımsız, yeniden kullanılabilen yöntemlerdir, Metasezgisel Yöntemlerden daha üst düzeyde soyutlama sağlarlar ve algoritma sürecinde herhangi bir zamanda hangi klasik sezgisel yöntemin uygulanacağına karar veren bir çözüm yaklaşımına sahiptirler. Klasik sezgisel teknikler, optimum, çözümü zor ve uzun süreler gerektiren büyük boyutlu problemler için, kabul edilebilir süre içinde optimuma yakın çözümler üreten, kullanımı kolay ve probleme özgü yöntemlerdir. Hipersezgisel Algoritmalar ise bu basit sezgisel yöntemleri uyumlu bir şekilde organize ederek etkin sonuçlar üretmektedir. Basit bir sezgisel yöntem, her problem için iyi çözümü üretmese de, diğer basit sezgisel tekniklerle uygulandığında kaliteli sonuçlar çıkarabilmekte, diğer bir deyişle çözümün belirli aşamalarında performansı yüksek olabilmektedir. Bu nedenle, sezgisel yöntemleri tek tek kullanmak yerine bütünleşik melez bir yapı oluşturmak, çözüm kalitesini arttırmaktadır.
Hipersezgisel Algoritmalarda basit sezgisel tekniklerin nasıl seçileceğine kılavuzluk eden bir öğrenme mekanizması vardır. Hipersezgisel yöntemler süreç açısından Basit Hipersezgiseller (Sezgisel yöntemleri rassal seçen yöntemler), Seçim Fonksiyonlu Hipersezgiseller (Sezgisel yöntemlere ağırlık verip, bu ağırlığa göre seçim yapan yöntemler), Metasezgisel Yöntemlerle Melezleştirilen Hipersezgiseller (Sezgisel yöntemlerin uygulanma sırasını kodlayıp Metasezgisel kullanarak bu sırayı güncelleyen yöntemler), Öğrenme Tabanlı Hipersezgiseller (Basit sezgisel yöntemlerin daha önceki performanslarını dikkate alarak, hangi yöntemin seçileceğine karar veren uyarlanabilir (adaptif) öğrenme mekanizmasına sahip yöntemler) olmak üzere dörde ayrılabilir.
Bu tez çalışmasında Lojistik Ağ Tasarımı problemi için bir Hipersezgisel Algoritma geliştirilmiş ve Microsoft .NET C# programı üzerinde kodlaması yapılmıştır. Ayrıca tasarlanan Hipersezgisel Algoritmanın farklı boyutlardaki Lojistik Ağ Tasarımı Problemleri için literatürde yer alan Genetik Algoritma ve Tavlama Benzetimi yöntemleri ile de karşılaştırılması yapılmıştır. Literatürde Lojistik Ağ Tasarımı için varolan bir problem kümesi (seti) olmadığı için, bu tezdeki problemler sanal olarak hazırlanmıştır ve problem içindeki parametrelere rassal değerler verilmiştir. Hazırlanan problemlerin düşük boyuttaki olanları için GAMS ortamında Karma Tamsayılı Programlama modeli oluşturularak optimum sonuçlar bulunmuştur, büyük boyutlu problemler için ise algoritmalar süresince bulunan en iyi çözüm dikkate alınmıştır. Geliştirilen Hipersezgisel Algoritmanın karşılaştırılması, optimum sonuca veya bulunan en iyi sonuca yakınlık, çözüm süresi ve bulunan çözümlerin dağılımları üzerinden yapılmıştır. 
Bu çalışmada Hipersezgisel Yöntemlerin daha iyi açıklanabilmesi için ayrıca Gezgin Satıcı Problemi üzerinde iyileştirici sezgiselleri kullanan ve salt iyileştirme gösteren hareketleri kabul eden (Sİ) Basit Hipersezgisel bir algoritma örneği verilmiştir. Bunun yanında geliştirilen Hipersezgisel yöntem kullanılarak bir, iki ve üç rotalı (güzergâhlı) LAT kapsamında basit örnekler üzerinden denemeler yapılmıştır.
Tez kapsamında geliştirilen Hipersezgisel Algoritmanın etkinliğini ölçmek için altı sanal problem tipi oluşturulmuş olup, her tip için üç örnek problem hazırlanmıştır. Bu problemler üzerinden ise Altıparmak ve diğerleri tarafından 2006'da geliştirilen Genetik Algoritma ile Jamayaran ve Ross tarafından 2003 yılında geliştirilen Tavlama Benzetimi yöntemi arasında kıyaslama yapılmıştır. İlk dört problem, Karma Tamsayılı Programlama Modeli kurularak GAMS ortamında çözülmüş ve optimum sonuçlar elde edilmiştir. Diğer iki problem için, büyük olmalarından dolayı GAMS ortamında çözüm oluşturulamamış, algoritmalarca bulunan en iyi çözüm değeri ile karşılaştırmalar yapılmıştır.
Literatürde Lojistik Ağ Tasarımı için bir problem kümesi olmadığı için problem verileri tümüyle rassal olarak üretilmiştir, bu sırada kapasite ve talep kısıtları dikkate alınarak uygun çözümlerin olabilirliği gözönüne alınmıştır. Üretilen problemler için bu çalışmada kurulan Karma Tamsayılı Programlama modeli dikkate alınmış ve senaryolar bu model üzerinden gerçekleştirilmiştir. Bulunan çözüm değerlerinin ayrıca sağlaması yapılarak sürecin kontrolü gerçekleştirilmiştir. Oluşturulan GAMS modelleri, program üzerindeki DICOPT ve BARON modülü ile çözülmüş ve optimum sonuçlar elde edilmiştir.
Bu çalışmada yöntemler, her bir problemde her bir parametre kümesi için yüz kez uygulanmış olup, bulunan çözüm değerleri, en iyi çözümle arasındaki fark, buna ait sapma yüzdesi ve çözüm süreleri hesaplanmıştır. Bu noktada yer alan çözüm sürelerinden kasıt, algoritmanın çalışma süreci boyunca bulduğu en iyi çözüme ulaşma süresidir. Uygulamada Hipersezgisel Algoritma, Genetik Algoritma ve Tavlama Benzetimi yöntemlerince 100 denemede bulunan çözüm değerlerinin ve en iyi çözümün üretilme süresinin kutu grafikleri ile analizi yapılmıştır.
Tez kapsamında gerçek yaşamdan örnek olması açısından îmalat sektöründe Türkiye'nin birçok yerinde tesisleri bulunan ve sektörün lider firmalarından biri seçilerek bir LAT problemi ele alınmıştır. Türkiye'de altı adet kutu fabrikası, dört adet depo, dört dağıtım merkezi ve 700'ü aşkın müşteriye sahip firmada gerçeğe uygun veriler alınarak gerçek yaşamdan bir uygulama gerçekleştirilmiştir. Tez çalışmasında ayrıca uluslararası hızlı taşımacılık alanında faaliyet gösteren bir lojistik firmasında da gerçeğe yakın veriler alınarak bir uygulama yapılmıştır. İngiltere, İtalya, Güney Kore ve Malezya'dan Türkiye'ye gönderilen 270 gönderi ve gönderim noktası olan 80 parsel üzerinde dört katmanlı LAT problemi için çözüm oluşturulmuştur.
Bu tez çalışmasının amacı; gerçek yaşamda karşılaşılan Lojistik Ağ Tasarımı Problemi için literatürde eksikliği giderecek sağlam (robust), esnek ve kaliteli çözümleri kabul edilebilir sürede üreten bir Hipersezgisel Algoritma hazırlamak ve gerçek bir süreç üzerinde uygulamasını yapmaktır. Geliştirilmesi yapılan Hipersezgisel Algoritma, uygun süreler içinde farklı problemlerde en iyi çözümü elde etmiş, sonuçların ayrıntılı analizi yapıldığında diğer algoritmalara göre daha iyi performans göstermiştir.

Abstract:
One of the most common problems in the Supply Chain Management is Logistics Network Design Problem. A company's logistics network consists of suppliers, warehouses, distribution centers and retail stores, as well as raw materials, intermediate products and finished product flows among them.
In the Logistics Network Design Problem, the objective is generally to minimize the fixed costs and the variable costs such as purchasing, production, storage and transportation while meeting the customer requirements. For the Logistic Network Design defined as the NP-hard problem, Heuristics and Metaheuristics methods provide effective solutions in static situations. However, Hyperheuristic methods are independent of the problem and provide an abstraction between the solution search process and the problem solution space.
The logistics network of an organization is concerned with all kinds of transportation and warehousing operations between the supplier, the production facility, the distribution centers and the warehouse for a company. Logistics Network Design is to associate warehouse, distribution center, etc. with the supplier, production points and sales points such as dealers, customers and wholesalers. In this thesis study, Logistics Network Design problems are described under three headings as Forward, Reverse and Integrated. In Forward Logistics Network Design, raw materials and products are progressing through supplier, factory, distribution center and customer respectively. In Reverse Logistic Network Design, the product has a contrary direction in this flow and the movement in both directions is taken into consideration in the Integrated Logistic Network Design.
Logistics Network Design Problems can be evaluated in four perspectives: As Decision dimension; Strategic, Tactic and Operational, as Fuctional dimension; determination of locations, vehicle routes, inventories, vehicle quantities etc., as Solution Methods dimension; exact and heuristic techniques, as Scope of Implementation; automotive, logistics, electronics sectors etc.  are classifications.
In this thesis study, Logistic Network Design Problem and Hyperheuristic Algorithms are described in separate sections as a result of detailed literature research. For Forward Logistic Network Design Problem a Mixed Integer Linear Programming Model was designed and modelled in GAMS software. In Logistics Network Design Problem, the aim is generally to try to minimize the fixed costs of the facilities and to minimize the variable costs such as purchasing, production, storage and transportation provided that customer requirements are met. Since the problem is so complex, the literature studies are generally focused on the problems of certain subprocesses. In the Mixed Integer Linear Programming Model proposed, focus is given to the selection of suppliers, the activation of the factory and the distribution center, the assignments between supplier-factory and factory-distribution centers and the vehicle routes between the distribution centers and the customers.
Nowadays, especially for economic reasons, the problems encountered in real life require optimization and have become very important. It is not feasible to make exact models for such problems because of its complexity and long periods of time for reaching solutions. Thus, simple heuristic methods that do not guarantee optimum results but that are easy to execute within reasonable times to produce feasible solutions are being used.
Although Metaheuristic methods have proven their success in recent years, they are difficult to implement, have high costs and problem-specific structure. A Metaheuristic Algorithm that produces a high-quality solution which can fail due to little changes in the state of the problem. Hyperheuristic Algorithms are generalized, robust and problem independent reusable methods, that provide a higher level of abstraction from Metaheuristics and have a solution approach that decides which classical heuristic method to apply at any time in the algorithm process. Classic heuristics are easy-to-use and problem-specific methods that produce solutions that are close to optimal in acceptable time for large-scale problems which are difficult to optimize and require long time to elapse. Hyperheuristic Algorithms organize these simple heuristic methods in a consistent way and create effective results. While a simple heuristic does not produce a good solution for every problem, it can produce quality results when applied together with other simple heuristic techniques, in other words the performance of the solution can be high at certain stages. Hence, rather than using individual heuristic methods, creating an integrated hybrid structure using a Hyperheuristic approach increases the quality of the solution.
Hyperheuristic Algorithms have a learning mechanism that guides how to choose simple heuristic techniques. Hyperheuristic methods can be classified as: Simple Hyperheuristics (random selection of heuristic methods), Hyperheuristics with choice functions (selection of heuristics according to heuristic weights), Hybrid Hyperheuristics with Metaheuristic methods (encoding the sequence of heuristic methods and selection of heuristics by this sequence using Metaheuristics), Learning based Hyperheuristics (adaptive learning mechanisms that decide which method to choose by considering their previous performance).
In this thesis, the proposed Hyperheuristic Algorithm for Logistic Network Design problem was developed on Microsoft .NET C # programming language. Moreover the suggested Hyperheuristic Algorithm was compared with the use of Genetic Algorithm and Simulated Annealing algorithms. There is no Logistic Network Design example of integrated functions is found in literature, that is why the virtually prepared problems and random parameters are used for comparisons. For the low dimensional problems, optimum solutions were produced by Mixed Integer Linear Programming model created in GAMS software and for the large problems the best solution found during the algorithms was taken into consideration. The comparison for the algorithms is based on the closeness to the best solution found, the solution time and the distributions of the solutions produced.
In order to clarify the procedure, a Simple Hyperheuristics was applied on Travelling Salesman Problem which accepts only better movements in solution. Furthermore, the proposed Hyperheuristic method was applied to simple Logistic Network Design Problems that have one, two and three stages.
The virtual Logistic Network Design Problem data are produced randomly considering feasible solutions by checking capacity and demand constraints. Since there is no problem sets for Logistic Network Design in the literature, the Mixed Integer Linear Programming model designed in this study was taken into account and the scenarios were realized through this model. Algorithm processes were checked by controlling solutions values seperately. The generated GAMS models were solved with the DICOPT and BARON modules on the program and optimum results were obtained.
In this study, the methods were applied hundred times for each parameter set of problems and the solution values, the differences among the best solutions, the percentage of deviation and the solution time were recorded. The duration of solution is the execution time of finding the best solutions during the running process. Analysis of Hyperheuristic Algoritm, Genetic Algorithm and Simulated Annealing approaches are carried out with box graphs of 100 experiment values and the execution times.
As a case study of the proposed algorithm, applications of one of the leading packaging companies is chosen, as it has distributed facilities in many regions. The company has six factories, four warehouses, four distribution centers and more than 700 customers which is implemented as a real life case. The second case is taken from a global logistics firm operating in fast transportation sector. A solution for the four layered Logistic Network Design problem was created for 80 parcels, 270 shipments sent from the UK, Italy, South Korea and Malaysia to Turkey. Both of these real life cases showed better performances with the proposed Hyperheuristic Algorithm.
The aim of this study is to fill the gap in literature for a robust and flexible method that produces good quality solutions in acceptable times for the Logistic Network Design Problem using this Hyperheuristic approach. In the thesis, proposed Hyperheuristic Algorithm has obtained the best solutions for different problems within best solution durations and has performed better than Genetic and Simulated Annealing algorithms. This study will be a lead for finding fast solutions for a complex network company.