Araştırma Makalesi
BibTex RIS Kaynak Göster

Solution of Two Dimensional Rectangular Strip Packing Problem Using Heuristic Algorithms

Yıl 2019, Sayı: 17, 315 - 322, 31.12.2019
https://doi.org/10.31590/ejosat.620618

Öz

In this study, a method is proposed for the solution of two-dimensional rectangular strip-packing problem by using bottom-left fill, first-fit decreasing and no-fit polygon heuristic algorithms. The two-dimensional rectangular strip-packing problem (2D-SPP) is the placement of a series of rectangular pieces on a strip with a constant width and infinite height. The goal is to minimize the height required to completely place all the rectangles onto the strip. In order to solve this problem, the bottom-left fill algorithm is used for the placement process and the no-fit polygon method is used to prevent the overlap between the rectangular parts. In addition, after the parts are sorted in descending order by areas, the first-fit decreasing heuristic algorithm is used as the selection algorithm for the placement process. The study has been carried out on 21 different data sets and performance evaluation has been done. As a result of conducted experimental studies, near to optimal solutions were obtained. The experimental results show the effectiveness of the proposed heuristic methods for 2D-SPP.

Kaynakça

  • A. Neuenfeldt, The Two-Dimensional Rectangular Strip Packing Problem, :December 2017 (2017).
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • I. Babaoǧlu, Solving 2D strip packing problem using fruit fly optimization algorithm, Procedia Computer Science, 111:2015 (2017) 52–57.
  • 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.
  • 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.
  • 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)
  • 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.

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

Yıl 2019, Sayı: 17, 315 - 322, 31.12.2019
https://doi.org/10.31590/ejosat.620618

Öz

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.

Kaynakça

  • A. Neuenfeldt, The Two-Dimensional Rectangular Strip Packing Problem, :December 2017 (2017).
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • I. Babaoǧlu, Solving 2D strip packing problem using fruit fly optimization algorithm, Procedia Computer Science, 111:2015 (2017) 52–57.
  • 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.
  • 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.
  • 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)
  • 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.
Toplam 11 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Hüseyin Fırat 0000-0002-1257-8518

Nuh Alpaslan 0000-0002-6828-755X

Yayımlanma Tarihi 31 Aralık 2019
Yayımlandığı Sayı Yıl 2019 Sayı: 17

Kaynak Göster

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. https://doi.org/10.31590/ejosat.620618