A Hybrid Methodology Using Heuristic Methods for Two-Dimensional Cutting and Packing Problem with Rectangular Pieces

Year 2019, Volume: 22 Issue: 4, 979 - 988, 01.12.2019

Hüseyin Fırat Nuh Alpaslan , Davut Hanbay

https://doi.org/10.2339/politeknik.487602

Cited By: 1

Abstract

The cutting and packing problem is the process of
cutting small pieces of certain sizes and proportions from materials used for
different purposes in industries. Because this problem cannot be expressed by
mathematical models, combinational optimization in multidimensional space is
utilized for the solution. The aim of this problem is to increase the usability
of the material used for the placement process and to minimize the trim loss.
In this study, a solution is presented to two-dimensional regular cutting and
packing problem by a combined method consisting of improved bottom-left,
bottom-left fill placement algorithms, no-fit polygon and first fit decreasing
heuristic algorithms. The improved bottom-left placement algorithm for the
placement of parts starting from the bottom-left part according to a certain
permutation order, bottom-left fill algorithm for the placement of suitable
pieces to the available free spaces in placement model, no-fit polygon method
for preventing the geometric overlap between the parts and the first fit
decreasing heuristic algorithm is used as the selection algorithm after
ordering from large to small according to the parts areas. Placement process
and performance evaluation was performed for 11 different test data. As a
result of the studies carried out with combined heuristic methods, it is seen
that there is a placement without any waste in P2 and P10 placement models.
This shows that the optimal solution is obtained. In other placement models, a
trim loss was obtained between 4.54% and 16.7%. The experimental results show
the effectiveness of the proposed heuristic methods for the solution of the
cutting and packing problem.

Keywords

Cutting and packing problem, no-fit polygons, improved bottom-left and bottom-left fill placement theorem, first-fit decreasing heuristic algorithm

Dikdörtgen Parçalar ile İki Boyutlu Kesme ve Paketleme Problemi için Sezgisel Yöntemler Kullanılan Bir Hibrit Metodoloji

Abstract

Kesme ve paketleme problemi,
endüstrilerde farklı amaçlar için kullanılan malzemelerden belirli büyüklük ve
oranlarda küçük parçaların kesilmesi işlemidir. Bu problem, matematiksel
modellerle ifade edilemediğinden dolayı, çözüm için çok boyutlu uzayda
kombinasyonel optimizasyon kullanılır. Bu problemin amacı, yerleştirme işlemi
için kullanılan malzemenin kullanılabilirliğini arttırmak ve fire oranını
minimize etmektir. Bu çalışmada, iki boyutlu düzenli kesme ve paketleme problemine,
geliştirilmiş alt-sol, alt-sol dolgu yerleşim algoritmaları, uygun olmayan
çokgen ve ilk uygun azalan sezgisel algoritmalarından oluşan birleştirilmiş bir
yöntem ile çözüm sunulmuştur. Parçaların belirli bir permütasyon sırasına göre
alt-sol kısımdan başlayarak yerleşimi için geliştirilmiş alt-sol yerleşim
algoritması, yerleşim modelinde mevcut boş alanlara uygun parçaların
yerleştirilmesi için alt-sol dolgu algoritması, parçalar arasında geometrik
çakışmayı önlemek için uygun olmayan çokgen yöntemi ve parçalar alanlarına göre
büyükten küçüğe doğru sıralandıktan sonra seçim algoritması olarak da ilk uygun
azalan sezgisel algoritması kullanılmaktadır. 11 farklı test verisi için
yerleştirme işlemi gerçekleştirilmiş ve performans değerlendirilmesi yapılmıştır.
Birleştirilmiş sezgisel yöntemlerle gerçekleştirilen çalışmalar sonucunda P2 ve
P10 yerleşim modellerinde firesiz bir yerleşim olduğu görülmektedir. Bu da
optimal çözümün elde edildiğini göstermektedir. Diğer yerleşim modellerinde
ise, % 4.54 ile % 16.7 aralığında fire oranı elde edilmiştir. Deneysel
sonuçlar, kesme ve paketleme probleminin çözümü için önerilen sezgisel
yöntemlerin etkinliğini göstermektedir.  

Keywords

Kesme ve paketleme problemi, uygun olmayan çokgenler, alt-sol ve alt-sol dolgu yerleşim teoremi, ilk uygun azalan sezgisel algoritması

References

• [1] Söke A. and Bingül Z., “İki Boyutlu Giyotinsiz Kesme Problemlerinin Benzetilmiş Tavlama Algoritması ile Çözümlerinin İncelenmesi A Study of Simulated Annealing Algorithm for Solutions of Two Dimensional Non-Guillotine Cutting Problems", Journal of Polytechnic, 8: 25–35, (2005)
• [2] Burke E. K., Hellier R. S. R., Kendall G. and Whitwell G., “Complete and robust no-fit polygon generation for the irregular stock cutting problem”, European Journal of Operational Research, 179: 27–49, (2007)
• [3] Dyckhoff H., “A typology of cutting and packing problems”, European Journal of Operational Research, 44: 145–159, (1990)
• [4] Dowsland K. A., Vaid S. and Dowsland W. B., “An algorithm for polygon placement using a bottom-left strategy”, European Journal of Operational Research, 141: 371–381, (2002)
• [5] Lo Valvo E., “Meta-heuristic Algorithms for Nesting Problem of Rectangular Pieces”, Procedia Engineering, 183: 291–296, (2017)
• [6] Gomes A. M. and Oliveira J. F., “Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming,” European Journal of Operational Research, 171: 811–829, (2006)
• [7] Albayrak E., "İki Boyutlu Dikdörtgen Şekilli Stok Kesme Problemleri için Sezgisel-Metasezgisel Algoritma ve Yazılım Geliştirme", Yüksek Lisans Tezi, Balıkesir Üniversitesi Fen Bilimleri Enstitüsü, (2013)
• [8] Jakobs S., “On genetic algorithms for the packing of polygons,” European Journal of Operational Research, 88: 165–181, (1996)
• [9] Liu D. and Teng H., “An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles,” European Journal of Operational Research, 112: 413–420, (1999)
• [10] Soke A. and Bingul Z., “Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems,” Engineering Applications of Artificial Intelligence, 19: 557–567, (2006)
• [11] Soke A. ,"Genetik Algoritma ve Benzetilmiş Tavlama ile İki Boyutlu Giyotinsiz Kesme Problemlerine Olasılıksal Yaklaşım", Yüksek Lisans Tezi, Kocaeli Üniversitesi Fen Bilimleri Enstitüsü, (2003)
• [12] Junior B. A., Pinheiro P. R. and Saraiva R. D., “A hybrid methodology for nesting irregular shapes: Case study on a textile industry ?,” IFAC Proceedings Volumes (IFAC-PapersOnline), 6: 15–20, (2013)
• [13] Fırat H. , "İmalat Sektöründe Parça Yerleştirme ve Kesme Probleminin Optimizasyonu", Yüksek Lisans Tezi, İnönü Üniversitesi Fen Bilimleri Enstitüsü, (2018)
• [14] Ergün K. , "Kesme ve Paketleme Problemleri ve Araştırmaya Yönelik Bir Metot Geliştirilmesi ve Bu Metodun Etkinliğinin Sınanması", Yüksek Lisans Tezi, Balıkesir Üniversitesi Fen Bilimleri Enstitüsü, (2004)