Solution of Two Dimensional Rectangular Strip Packing Problem Using Heuristic Algorithms

Abstract

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.

Keywords

• Bottom-left fill algorithm
• No-fit polygon method
• First fit decreasing heuristic algorithm
• Strip packing problem

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

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

Anahtar Kelimeler

• Alt sol dolgu algoritması
• Uygun olmayan çokgen yöntemi
• İlk uygun azalan sezgisel algoritması
• Şerit paketleme problemi

Kaynakça

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.