Büyük boyutlu kutulama problemleri için bir algoritma önerisi
An algorithm for large scale bin packing problem
Yazar: SEZGİ TEKİL
Danışman: YRD. DOÇ. VİLDAN ÖZKIR
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2017
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Kutulama problemi, kullanılan kutu sayısını en aza indirmek amacıyla, çeşitli hacimlerdeki nesnelerin çeşitli hacimlerdeki kutulara yerleştirilmesi problemidir. Kutulama problemi NP-hard problemi olmasına rağmen, büyük boyuttaki problemler için ileri düzeydeki algoritmalarla optimal çözümler bulunabilmektedir.
Kutulama problemleri bir nevi kesim problemidir. Kutulama problemlerinin özel diğer bir hali de, her bir nesne hacmi ve değeri ile karakterize edildiğinde yalnızca bir kutunun azami değerde nesne ile doldurulması problemi sırt çantası problemi olarak bilinmektedir. Kutulama problemlerinin birçok varyasyonları vardır; 2B kutulama, lineer kutulama, ağırlıkça paketleme, maliyetçe yerleştirmeve benzerleri gibi. Ayrıca, kapları doldurma, ağırlık kapasite kısıtları ile kamyon yükleme, FPGA yarı iletken çip tasarımı, medya ve teknoloji haritalama, dosya yedeklerini oluşturmak gibi birçok kutulama uygulamaları vardır.
Kutulama problemlerinin karşımıza çıktığı diğer bir alanda konteyner atama problemleridir. Günümüzde teknolojinin gelişmesi ve küreselleşme ile artan ticaret hacmi, lojistik operasyonlarının optimizasyonunu zorunlu hale getirmiştir. Bu operasyonları yüksek hızda, yüksek doğrulukta ve düşük maliyetle yürütmek için matematiksel optimizasyon araçları ve modelleri sıklıkla kullanılmaktadır. Konteyner yükleme problemleri, sık karşılaşılan lojistik optimizasyon problemlerinden biridir. Optimum sonuçlara ulaşabilmek için kesin çözüm veren algoritmaların kullanılmasının yanı sıra, büyük boyutlu problemlerin çözümünde kesin algoritmalar yetersiz kalabilmektedir. Bu çalışmada, bir filtre fabrikasının lojistik operasyonları incelenerek, ticari araçların ve konteynerlerin karmaşık yük ve yükleme planlarının optimizasyonu amaçlanmaktadır. Kutulama algoritmaları, konteyner sayısının azaltılması ve yükleme hızının arttırılması amacıyla geliştirilecek ve uygun optimal kararların alınması için önerdiğimiz 2B-CAMFA modeli uygulanacaktır.
,2B-CAMFA

Abstract:
In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. Despite the fact that the bin packing problem has an NP-hard computational complexity, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms.
The bin packing problem can also be seen as a special case of the cutting stock problem. When the number of bins is restricted to 1 and each item is characterised by both a volume and a value, the problem of maximising the value of items that can fit in the bin is known as the knapsack problem. There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in Field-programmable gate array semiconductor chip design.
Recently, the technology is improving day by day and the globalization results in increasing of international trade. Because of these improvements, logistic operation must be faster than the past. For keeping on these operations with low cost, higher accuracy and rapidity, the mathematical optimization tools and models are highly used. Container loading problem is also one of the logistic operations. Due to get optimum results we must apply appropriate algorithms but in some cases these algorithms are not enough for solutions of three dimensional bin packing problems. In this study, we investigate the logistic operations of a filter factory and for the commercial vehicles and container's' complex load and loading plan. By improving the work load speed and decreasing the number of container in bin packing problems, we will implement the 2D Combinatorial Area Fitting Algorithm 2D-CAMFA model that we recommend to make appropriate optimum decisions. We also compare the solutions of Self-Best Fit Algorithm with 2D-CAMFA model.