Otonom kutu istifleme robot hücreleri için meta-sezgisel optimizasyon algoritması geliştirilmesi
Development of a meta-heuristic optimization algorithm for autonomous bin packing robot cells
Yazar: HARUN GEZİCİ
Danışman: PROF. DR. HAYDAR LİVATYALI
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Mekatronik Mühendisliği Ana Bilim Dalı / Mekatronik Mühendisliği Bilim Dalı
Derece: Doktora, 2022
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering ; Mekatronik Mühendisliği = Mechatronics Engineering
Dizin: Ambalajlama = Packaging ; Global optimizasyon yöntemi = Global optimization method ; Metasezgiseller = Metaheuristics ; Tozlaşma = Pollination

Özet:
Kutu paketleme problemleri (KPP) kombinatoryal optimizasyon problemlerindendir. Bu problemin çözümü için literatürde kesin, sezgisel ve meta-sezgisel olmak üzere üç yöntem kullanılmaktadır. Kesin yöntemler kutu sayısının fazla olduğu durumlarda başarılı sonuçlar elde edememektedir. Meta-sezgisel yöntemler ise kabul edilebilir çözümleri makul sürelerde elde edebildikleri için araştırmacılar tarafından son yıllarda daha fazla tercih edilmektedir. KPP'nin bir, iki ve üç boyutlu alt grupları bulunmaktadır. Bu doktora tezinde üç farklı KPP'nin çözümü için üç farklı meta-sezgisel algoritma önerilmiştir. Bir ve iki boyutlu KPP'nin çözümü için Çiçek Tozlaşma Algoritması (ÇTA) ve Genetik Algoritma (GA) iki farklı yöntemle hibritlenmiş ve iki yeni yaklaşım sunulmuştur (1B-ÇTGA, 2B-ÇTGA). Ancak ÇTA ve GA'nın farklı hibrit varyantları, üç boyutlu KPP'nin çözümü için başarılı sonuçlar elde edememiştir. Bu nedenle yeni bir optimizasyon algoritması araştırılmıştır. Mühendislik problemlerinin çözümünde sıklıkla kullanılan ve geçerliliği kanıtlanmış Harris Şahinleri Algoritması (HŞA) yeni yöntem olarak tercih edilmiştir. Öncelikle HŞA'nın geliştirilebilir bir algoritma olduğunu teyit etmek için kaotik haritalar ile değiştirilmiş ve çeşitli test fonksiyonları ile sınanmıştır. Elde edilen sonuçlar HŞA'nın geliştirilebilir olduğunu göstermiştir. Daha sonra HŞA sadeleştirme stratejisi kullanılarak geliştirilmiş ve üç boyutlu KPP'ye uygulanmıştır (3B-HŞA). Önerilen algoritmaların başarımı, literatürden başarılı sonuçlar elde eden rakip algoritmalar ile karşılaştırılmış ve istatistiksel yöntemler ile yorumlanmıştır.
Bir boyutlu KPP'nin çözümü için önerilen 1B-ÇTGA, literatürdeki diğer algoritmalar ile karşılaştırılmıştır. Karşılaştırma için kolay, orta ve zor sınıfları bulunan Scholl veri seti kullanılmıştır. Veri setinin kolay sınıfı için 1B-ÇTGA, minimum yüzde performans (min%f) ve ortalama yüzde performans (ort%f) metriklerinde %26,1 ve %37,7 arasında rakiplerinden daha iyi performans göstermiştir. Veri setinin orta sınıfı için 1B-ÇTGA, min%f ve ort%f metriklerinde %28,7 ve %43,9 arasında rakiplerinden daha iyi performans göstermiştir. Veri setinin zor sınıfı için 1B-ÇTGA, min%f ve ort%f metriklerinde %60,7 ve %73,1 arasında rakiplerinden daha iyi performans göstermiştir.
İki boyutlu KPP'nin çözümü için önerilen 2B-ÇTGA, literatürdeki diğer algoritmalar ile karşılaştırılmıştır. Karşılaştırma için 10 sınıf, 50 alt grup ve 500 örneği bulunan Berkey-Wang ve Martello-Vigo veri seti kullanılmıştır. 2B-ÇTGA, veri setinin 6 sınıfında en iyi sonuçları elde etmiştir. 2B-ÇTGA, veri seti sınıflarının %60'ında en iyi sonuçları elde etmiş ve en yakın rakibinden 3 kat fazla sınıfta başarı sağlamıştır. Ayrıca, 2B-ÇTGA, 50 alt-grubun 33'ünde en iyi sonuçları elde ederek en başarılı algoritma olmuştur. 2B-ÇTGA, alt grupların %66'sını başarı ile çözmüş ve en yakın rakibinden %12 daha başarılı sonuçlar elde etmiştir.
Üç boyutlu KPP'nin çözümü için önerilen 3B-HŞA, 8 sınıf, 32 alt grup ve320 örnekten oluşan bir veri seti kullanılarak, EO, ÇTA, GBO, SOA ve HŞA algoritmaları ile karşılaştırılmıştır. 3B-HŞA en yakın rakibi HŞA'dan konteyner sayısını metriğinde %0,503, çözüm süresi metriğinde ise %5,035 daha iyi performans göstermiştir. Sonuçlar önerilen algoritmaların geçerliliğini teyit etmektedir.

Abstract:
Bin packing problems (BPP) are combinatorial optimization problems. There are three methods including the exact, heuristic, and meta-heuristic ones for the solution of BPP in the literature. The exact method is not capable to generate successful results in cases where the number of the boxes are high. Meta-heuristic methods have been preferred by researchers as they present acceptable solutions in reasonable times. The BPP has one, two, and three dimensional categories. In this dissertation, three different meta-heuristic algorithms are proposed for the three bin packing problems. For the solution of the one and two dimensional BPP, flower pollination (FPA) and genetic algorithms (GA) are hybridized using two alternative methods (1D-FPGA, 2B-FPGA). However, the combined FPA and GA method failed to generate successful results for the solution of the three-dimensional BPP. Therefore, a new optimization algorithm is investigated. Harris hawks optimization algorithm (HHO), which is frequently used for the solution of various engineering problems with confirmed validity is chosen as basis of the new method. To prove the improvement potential of HHO, it is modified with chaotic maps and then tested through various test functions. The results indicate that HHO is improvable. Next, by adapting a simplification strategy, HHO is improved (3D-HHO) and applied to the three-dimensional BPP. The proposed algorithm is compared to the competitive algorithms that have successful results in literature. The results are interpreted through statistical methods.
1D-FPGA, proposed for the solution of one dimensional KPP, is compared to other algorithms. Scholl data set, which has easy, medium, and difficult classes, is used for the comparison. 1D-FPGA, for the easy class of the data set, performs better than its competitors by 26,1% and 37,7% in the minimum min%f and average percentage metrics avg%f. For the medium class of the data set, 1D-FPGA outperforms its competitors by 28,7% and 43.9% in min%f and avg%f metrics. For the difficult class of the data set, 1D-FPGA, outperforms its competitors by 60,7% and 73,1% in min%f and avg%f metrics.
2D-FPGA which is proposed for the solution of two dimensional KPP is compared to other algorithms in the literature. For the comparison, Berkey-Wang and Martello-Vigo data sets which have 10 classes, 50 subgroups, and 500 samples are used. 2D-FPGA has the best results in 6 classes of the data set. 2D-FPGA has the best results in 60% of the data set classes and is three times more successful than its closest competitor. Moreover, 2D-FPGA is the most successful algorithm as it has the best results in 33 subgroups out of 50. 2D-FPGA solves 66% of the subgroups successfully and has 12% more successful results than its closest competitor.
3D-HHO which is proposed for the solution of three dimensional KPP is compared to EO, FPA, GBO, SOA, and HHO algorithms by using a data set with 8 classes, 32 sub-groups, and 320 samples. 3D-HHO outperforms HHO, its closest competitor, by 0,503% in container number metric while by 5,035% in solution time metric. The results confirm the credibility of the proposed algorithms. The improved performance confirms the validity of the proposed algorithms.