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

Yıl 2022, , 1523 - 1534, 28.02.2022

Harun Gezici , Haydar Livatyalı

https://doi.org/10.17341/gazimmfd.764853

Ö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 Kelimeler

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

Kaynakça

• 1. Virk A.K., Singh K., Application of Nature Inspired Algorithms to Optimize Multi-objective Two-Dimensional 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. Beyaz M., Dokeroglu T., Cosar A., Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems, Applied Soft Computing Journal, 36, 236–245, 2015.
• 8. 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.
• 9. Dokeroglu T., Cosar A., Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers and Industrial Engineering, 75(1), 176–186, 2014.
• 10. 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.
• 11. 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.
• 12. 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.
• 13. 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.
• 14. Wang Y., Chen L., Two-dimensional residual-space-maximized packing, Expert Systems with Applications, 42(7), 3297–3305, 2015.
• 15. Dyckhoff H., A typology of cutting and packing problems, Ejor, 44(2), 145–159, 1990.
• 16. 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.
• 17. 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.
• 18. 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.
• 19. 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.
• 20. 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.
• 21. 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.
• 22. 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.
• 23. 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.
• 24. Gomez J.C., Terashima-Marín H., Evolutionary hyper-heuristics for tackling bi-objective 2D bin packing problems, Genetic Programming and Evolvable Machines, 19(1–2), 151–181, 2018.
• 25. Zheng J.N., Chien C.F., Gen M., Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem, Computers and Industrial Engineering, 89, 80–87, 2015.
• 26. Sim K., Hart E., Paechter B., A lifelong learning hyper-heuristic method for bin packing, Evolutionary Computation, 23(1), 37–67, 2015.
• 27. 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.
• 28. 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.
• 29. 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.
• 30. 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, 145(2), 488–499, 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), 2017.
• 42. Berkey J.O., Wang P.Y., Two-Dimensional Finite Bin-Packing Algorithms, The Journal of the Operational Research Society, 38(5), 423–429, 1987.
• 43. Martello S., Vigo D., Exact solution of the two-dimensional finite bin packing problem, Management Science, 44(3), 388–399, 1998.