İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı

GEZICI, HARUN; LIVATYALI, HAYDAR

doi:10.17341/gazimmfd.764853

İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı

Harun Gezici, (Kırklareli Üniversitesi, Teknik Bilimler Meslek Yüksekokulu, Elektronik ve Otomasyon Bölümü, Kırklareli, Türkiye)

Haydar Livatyalı (Yıldız Teknik Üniversitesi, Makine Fakültesi, Mekatronik Mühendisliği Bölümü, İstanbul, Türkiye)

Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi

23 2

Yıl: 2022 Cilt: 37 Sayı: 3 Sayfa Aralığı: 1523 - 1534 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.764853 İndeks Tarihi: 29-07-2022

İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı

Öz:

İki boyutlu kutu paketleme problemi (2BKPP), kesme ve paketleme problemlerinin (KPP) bir alt dalıdır. Araştırmacılar, 2BKPP’nin çözümünde meta sezgisel algoritmaları sıklıkla kullanmaktadırlar. Bunun nedeni meta sezgisel algoritmaların çok sayıda örneğin bulunduğu vakalarda kabul edilebilir çözümlere makul sürelerde ulaşmasıdır.Bu çalışmada, 2BKPP’nin çözümü için yeni bir melez meta sezgisel algoritma önerilmektedir. Önerilen algoritma çiçek tozlaşma algoritması (ÇTA) ve genetik algoritmanın (GA) hibritlenmesiyle oluşturulmuştur. ÇTA’nın global arama kabiliyetini geliştirmek için yerel arama operatöründe değişik yapılmıştır. Bu çalışma kapsamında önerilen algoritma, son yıllarda yayınlanan altı farklı meta sezgisel algoritma ile karşılaştırılmıştır. Karşılaştırma için 10 sınıf, 50 alt grup ve 500 örneğin bulunduğu bir veri seti kullanılmıştır. Her bir sınıfın ve her bir alt grubun, ortalama konteyner değerleri karşılaştırma parametresi olarak kullanılmıştır. Ayrıca algoritmaların birbirlerine göre performanslarını karşılaştırmak için Friedman testi uygulanmıştır. Önerilen algoritma veri setinin 10 sınıfının 6’sında ve 50 alt grubunun 33’ünde en başarılı sonuçları elde etmiş, Friedman testinde ise 2,6 skor ile en başarılı algoritma olmuştur. Elde edilen sonuçlar önerilen meta sezgisel algoritmanın geçerliliğini teyit etmektedir.

Anahtar Kelime: Kutu Paketleme Problemi Hibritleme Genetik Algoritma Çiçek Tozlaşma Algoritması Kombinatoryal Optimizasyon

Hybrid flower pollination algorithm approach for the two-dimensional bin packing problem

Öz:

Two-dimensional bin packing problem (2DBPP) is a sub-branch of cutting and packaging problems (CPP). Researchers often use meta-heuristic algorithms in the solution of 2DBPP, because in cases where a large number of samples exist, meta-heuristic algorithms reach acceptable solutions in reasonable time. In this article, a novel hybrid meta-heuristic algorithm is proposed for the solution of 2DBPP. The proposed algorithm combines flower pollination algorithm (FPA) and genetic algorithm (GA). In order to improve FPA's global search capability, FPA's local search operator is modified. The proposed algorithm has been compared to six recently published meta-heuristic algorithms. For comparison, a data set containing 10 classes, 50 subgroups and 500 samples was used. Average container values of each class and of each subgroup were used as comparison parameters. In addition, Friedman test was used to evaluate the relative performance of the algorithms. The proposed algorithm achieved the most successful results in 6 of the 10 classes of the data set and 33 of the 50 subgroups. In the Friedman test, it was the most successful algorithm with a score of 2.6. The results confirm the validity of the proposed meta-heuristic algorithm.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. Virk A.K., Singh K., Application of Nature Inspired Algorithms to Optimize Multi-objective TwoDimensional Rectangle Packing Problem, Journal of Industrial Integration and Management, 04 (04), 1950010, 2019.
2. Stoyan Y., Pankratov A., Romanova T., Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization, Journal of the Operational Research Society, 67 (5), 786–800, 2017.
3. Cui Y., Song X., Chen Y., Cui Y.-P., New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers, Journal of the Operational Research Society, 68 (3), 269–280, 2017.
4. Cui Y.-P., Yao Y., Zhang D., Applying triple-block patterns in solving the two-dimensional bin packing problem, Journal of the Operational Research Society, 69 (3), 402–415, 2018.
5. Virk A.K., Singh K., Solving Two-Dimensional Rectangle Packing Problem Using Nature-Inspired Metaheuristic Algorithms, Journal of Industrial Integration and Management, 03 (02), 1850009, 2018.
6. Grandcolas S., Pinto C., A New Search Procedure for the Two-dimensional Orthogonal Packing Problem, Journal of Mathematical Modelling and Algorithms in Operations Research, 14 (3), 343–361, 2015.
7. Lodi A., Monaci M., Pietrobuoni E., Partial enumeration algorithms for Two-Dimensional Bin Packing Problem with guillotine constraints, Discrete Applied Mathematics, 217, 40–47, 2017.
8. Cui Y.P., Cui Y., Tang T., Sequential heuristic for the two-dimensional bin-packing problem, European Journal of Operational Research, 240 (1), 43–53, 2015.
9. Dahmani N., Krichen S., Ghazouani D., A variable neighborhood descent approach for the two-dimensional bin packing problem, Electronic Notes in Discrete Mathematics, 47, 117–124, 2015.
10. Beyaz M., Dokeroglu T., Cosar A., Robust hyperheuristic algorithms for the offline oriented/nonoriented 2D bin packing problems, Applied Soft Computing Journal, 36, 236–245, 2015.
11. Wang Y., Chen L., Two-dimensional residual-spacemaximized packing, Expert Systems with Applications, 42 (7), 3297–3305, 2015.
12. Dyckhoff H., A typology of cutting and packing problems, Ejor, 44 (2), 145–159, 1990.
13. Wäscher G., Haußner H., Schumann H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183 (3), 1109–1130, 2007.
14. Oliveira J.F., Neuenfeldt A., Silva E., Carravilla M.A., A surveyonheuristics for the two-dimensional rectangular strip packing problem, Pesquisa Operacional, 36 (2), 197–226, 2016.
15. Abdel-Basset M., El-Shahat D., El-Henawy I., Solving 0–1 knapsack problem by binary flower pollination algorithm, Neural Computing and Applications, 31 (9), 5477–5495, 2019.
16. Akyol S., Alataş B., Automatic mining of accurate and comprehensible numerical classification rules with cat swarm optimization algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 31 (4), 840–857, 2016.
17. Hopper E., Turton B.C.H., An Empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128 (1), 34–57, 2001.
18. Thomas J., Chaudhari N.S., A new metaheuristic genetic-based placement algorithm for 2D strip packing, Journal of Industrial Engineering International, 10 (1), 1–16, 2014.
19. Chen W., Zhai P., Zhu H., Zhang Y., Hybrid algorithm for the two-dimensional rectangular layer-packing problem, Journal of the Operational Research Society, 65 (7), 1068–1077, 2014.
20. Hong S., Zhang D., Lau H.C., Zeng X., Si Y.-W., A hybrid heuristic algorithm for the 2D variable-sized bin packing problem, European Journal of Operational Research, 238 (1), 95–103, 2014.
21. Gomez J.C., Terashima-Marín H., Evolutionary hyperheuristics for tackling bi-objective 2D bin packing problems, Genetic Programming and Evolvable Machines, 19 (1–2), 151–181, 2018.
22. Zheng J.N., Chien C.F., Gen M., Multi-objective multipopulation biased random-key genetic algorithm for the 3-D container loading problem, Computers and Industrial Engineering, 89, 80–87, 2015.
23. Sim K., Hart E., Paechter B., A lifelong learning hyperheuristic method for bin packing, Evolutionary Computation, 23 (1), 37–67, 2015.
24. Bennell J.A., Soon Lee L., Potts C.N., A genetic algorithm for two-dimensional bin packing with due dates, International Journal of Production Economics, 145 (2), 547–560, 2013.
25. Thapatsuwan P., Pongcharoen P., Hicks C., Chainate W., Development of a stochastic optimisation tool for solving the multiple container packing problems, International, Journal of Production Economics, 140 (2), 737–748, 2012.
26. Gonçalves J.F., Resende M.G.C., A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 145 (2), 500–510, 2013.
27. López-Camacho E., Terashima-Marín H., Ochoa G., Conant-Pablos S.E., Understanding the structure of bin packing problems through principal component analysis, International Journal of Production Economics [Internet], 145 (2), 488–499, 2013.
28. Dokeroglu T., Bayir M.A., Cosar A., Robust heuristic algorithms for exploiting the common tasks of relational cloud database queries, Applied Soft Computing Journal, 30, 72–82, 2015.
29. Dokeroglu T., Cosar A., Optimization of onedimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers and Industrial Engineering, 75 (1), 176–186, 2014.
30. Fernández A., Gil C., Baños R., Montoya M.G., A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing, Expert Systems with Applications, 40 (13), 5169–5180, 2013.
31. Aydilek İ.B., Multi-class classification with modified firefly optimization algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 32 (4), 1097–1108, 2017.
32. Yang X.-S., Karamanoglu M., He X., Flower pollination algorithm: A novel approach for multiobjective optimization, Engineering Optimization, 46 (9), 1222– 1237, 2014.
33. Ram J.P., Babu T.S., Dragicevic T., Rajasekar N., A new hybrid bee pollinator flower pollination algorithm for solar PV parameter estimation, Energy Conversion and Management [Internet], 135, 463–476, 2017.
34. Salgotra R., Singh U., Application of mutation operators to flower pollination algorithm, Expert Systems with Applications [Internet], 79, 112–129, 2017.
35. Liang J.J., Pan Q.K., Tiejun C., Wang L., Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer, International Journal of Advanced Manufacturing Technology [Internet], 55 (5), 755–762, 2011.
36. Tasgetiren M.F., Liang Y.C., Sevkli M., Gencyilmaz G., Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem, International Journal of Production Research, 44 (22), 4737–4754, 2006.
37. Qian B., Wang L., Hu R., Wang W.L., Huang D.X., Wang X., A hybrid differential evolution method for permutation flow-shop scheduling, International Journal of Advanced Manufacturing Technology, 38, 757–777, 2008.
38. Deep K., Mebrahtu H., Nagar A.K., Novel GA for metropolitan stations of Indian railways when modelled as a TSP, International Journal of Systems Assurance Engineering and Management, 9 (3), 639–645, 2018.
39. Adrian A.M., Utamima A., Wang K.J., A comparative study of GA, PSO and ACO for solving construction site layout optimization, KSCE Journal of Civil Engineering, 19 (3), 520–527, 2015.
40. Abdel-Basset M., Manogaran G., Abdel-Fatah L., Mirjalili S., An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems, Personal and Ubiquitous Computing, 22 (5–6), 1117–1132, 2018.
41. Durmaz E.D., Şahin R., NSGA-II and goal programming approach for the multi-objective single row facility layout problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 32 (3), 941-955, 2017.
42. Berkey J.O., Wang P.Y., Two-Dimensional Finite BinPacking Algorithms, The Journal of the Operational Research Society, 38 (5), 423–429, 1987.
43. Martello S., Vigo D., Exact solution of the twodimensional finite bin packing problem, Management Science, 44 (3), 388–399, 1998.

APA	GEZICI H, LIVATYALI H (2022). İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. , 1523 - 1534. 10.17341/gazimmfd.764853
Chicago	GEZICI HARUN,LIVATYALI HAYDAR İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. (2022): 1523 - 1534. 10.17341/gazimmfd.764853
MLA	GEZICI HARUN,LIVATYALI HAYDAR İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. , 2022, ss.1523 - 1534. 10.17341/gazimmfd.764853
AMA	GEZICI H,LIVATYALI H İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. . 2022; 1523 - 1534. 10.17341/gazimmfd.764853
Vancouver	GEZICI H,LIVATYALI H İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. . 2022; 1523 - 1534. 10.17341/gazimmfd.764853
IEEE	GEZICI H,LIVATYALI H "İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı." , ss.1523 - 1534, 2022. 10.17341/gazimmfd.764853
ISNAD	GEZICI, HARUN - LIVATYALI, HAYDAR. "İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı". (2022), 1523-1534. https://doi.org/10.17341/gazimmfd.764853

APA	GEZICI H, LIVATYALI H (2022). İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37(3), 1523 - 1534. 10.17341/gazimmfd.764853
Chicago	GEZICI HARUN,LIVATYALI HAYDAR İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37, no.3 (2022): 1523 - 1534. 10.17341/gazimmfd.764853
MLA	GEZICI HARUN,LIVATYALI HAYDAR İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.37, no.3, 2022, ss.1523 - 1534. 10.17341/gazimmfd.764853
AMA	GEZICI H,LIVATYALI H İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(3): 1523 - 1534. 10.17341/gazimmfd.764853
Vancouver	GEZICI H,LIVATYALI H İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2022; 37(3): 1523 - 1534. 10.17341/gazimmfd.764853
IEEE	GEZICI H,LIVATYALI H "İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 37, ss.1523 - 1534, 2022. 10.17341/gazimmfd.764853
ISNAD	GEZICI, HARUN - LIVATYALI, HAYDAR. "İki boyutlu kutu paketleme probleminin çözümü için hibrit çiçek tozlaşma algoritması yaklaşımı". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37/3 (2022), 1523-1534. https://doi.org/10.17341/gazimmfd.764853