Yıl 2019, Cilt , Sayı 17, Sayfalar 315 - 322 2019-12-31

Sezgisel Algoritmalar Kullanılarak İki Boyutlu Dikdörtgen Şerit Paketleme Probleminin Çözümü

Hüseyin FIRAT [1] , Nuh ALPASLAN [2]


    Bu çalışmada, alt sol dolgu, ilk uygun azalan ve uygun olmayan çokgen sezgisel algoritmaları kullanılarak iki boyutlu dikdörtgen şerit paketleme probleminin çözümü üzerine bir yöntem önerilmektedir. İki boyutlu dikdörtgen şerit paketleme problemi (2D-SPP), sabit genişlik ve sonsuz yüksekliğe sahip bir şerit üzerine bir dizi dikdörtgen parçanın yerleştirilmesidir. Amaç, tüm dikdörtgenleri tamamen şeridin içine yerleştirmek için gereken yüksekliği en aza indirgemektir. Bu problemin çözümünde, yerleştirme işlemi için alt sol dolgu algoritması, dikdörtgen parçalar arasında oluşabilecek çakışmayı önlemek için uygun olmayan çokgen yöntemi kullanılmıştır. Ayrıca, parçalar alanlarına göre azalan sırada sıralandıktan sonra yerleştirme işlemi için kullanılacak olan seçim algoritması olarak da ilk uygun azalan sezgisel algoritması kullanılmıştır. 21 farklı veri seti üzerinde çalışmalar gerçekleştirilmiş ve performans değerlendirilmesi yapılmıştır. Gerçekleştirilen deneysel çalışmalar sonucunda optimal çözüme yakın sonuçlar elde edilmiştir. Deneysel sonuçlar, 2D-SPP için önerilen sezgisel yöntemlerin etkinliğini göstermektedir.

Alt sol dolgu algoritması, Uygun olmayan çokgen yöntemi, İlk uygun azalan sezgisel algoritması, Şerit paketleme problemi
  • [1] A. Neuenfeldt, The Two-Dimensional Rectangular Strip Packing Problem, :December 2017 (2017).
  • [2] D. Zhang, L. Shi, S. C. H. Leung, and T. Wu, A priority heuristic for the guillotine rectangular packing problem, Information Processing Letters, 116:1 (2016) 15–21.
  • [3] G. Wäscher, H. Haußner, and H. Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research, 183:3 (2007) 1109–1130.
  • [4] D. Zhang, Y. Kang, and A. Deng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers and Operations Research, 33:8 (2006) 2209–2217.
  • [5] D. Zhang, L. Wei, S. C. H. Leung, and Q. Chen, A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem, INFORMS Journal on Computing, 25:2 (2013) 332–345.
  • [6] V. M. Kotov and D. Cao, A heuristic algorithm for the non-oriented 2D rectangular strip packing problem, Buletinul Academiei de Stiinte a Republicii Moldova. Matematica, 66:2 (2011) 81–88.
  • [7] I. Babaoǧlu, Solving 2D strip packing problem using fruit fly optimization algorithm, Procedia Computer Science, 111:2015 (2017) 52–57.
  • [8] E. Hopper and B. C. H. Turton, Empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128:1 (2001) 34–57.
  • [9] K. Daoden and T. Thaiupathump, Applying shuffled frog leaping algorithm and bottom left fill algorithm in rectangular packing problem, Proceedings of 2017 IEEE 7th International Conference on Electronics Information and Emergency Communication, ICEIEC 2017, July 2017 (2017) 136–139.
  • [10] E. Albayrak, İki boyutlu dikdörtgen şekilli stok kesme problemleri için sezgisel-metasezgisel algoritma ve yazılım geliştirme, Balikesir, ocak - 2013, (2013)
  • [11] E. K. Burke, G. Kendall, and G. Whitwell, A New Placement Heuristic for the Orthogonal Stock-Cutting Problem, Operations Research, 52:4 (2004) 655–671.
Birincil Dil tr
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Orcid: 0000-0002-1257-8518
Yazar: Hüseyin FIRAT (Sorumlu Yazar)
Ülke: Turkey


Orcid: 0000-0002-6828-755X
Yazar: Nuh ALPASLAN
Ülke: Turkey


Tarihler

Yayımlanma Tarihi : 31 Aralık 2019

APA Fırat, H , Alpaslan, N . (2019). Sezgisel Algoritmalar Kullanılarak İki Boyutlu Dikdörtgen Şerit Paketleme Probleminin Çözümü . Avrupa Bilim ve Teknoloji Dergisi , (17) , 315-322 . DOI: 10.31590/ejosat.620618