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

Abstract

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.

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.