Solving the 3D container loading problem with metaheuristics

Abstract

Konteyner Yükleme (KY) oldukça ilginç ve çözülmesi çok zor bir problemdir. Bir grup küçük dikdörtgen nesnenin, boyutları bilinen dikdörtgen bir konteynere; konteyner hacminden maksimum şekilde faydalanmak amacıyla yerleştirilmesidir. Yöneylem Araştırması (YA) yazını problemi NP-zor olarak sınıflamaktadır. Problemin karmaşık doğası gereği, bu tezin ilk kısmında sürü zekası tabanlı iki çözüm yaklaşımı ismen Karınca Kolonisi Optimizasyonu (KKO) ve Arı Algoritması (AA) KY problemini çözmek için önerilmiştir. Bu yaklaşımlarla elde edilen sonuçlar yazında mevcut diğer yaklaşımlarla kıyaslanmış ve bu yaklaşımların performansları tartışılmıştır. Önerilen algoritmalarla kıyaslandığında AA'nın performansının daha iyi olduğu görülmüştür. Bunlara ek olarak, bir KY problemine ait doldurma düzeninin belirlenmesi ve görüntülenmesi için bir KY karar destek sistemi de tasarlanmıştır.Tezin ikinci kısmında ise, gerçek bir endüstriyel problemden esinlenen çok-amaçlı bir KY (ÇAKY) problemi tanıtılmıştır. ÇAKY problemin ana amacı; bir grup nesnenin herhangi bir çakışmada olmadan, yüklenen nesnelerin toplam ağırlığını ve konteyner kullanım oranını eş zamanlı maksimize ederek konteynere yüklemektir. Bu iki amaç, bir nesnenin hacminin ağırlığına orantılı olmadığında çoğunlukla birbirine zıttır. Problem seçilmiş çok-amaçlı optimizasyon metotları (Hedef Programlama ve Ağırlıklı-Toplam) ve Tavlama Benzetimi algoritması vasıtasıyla çözülmüştür. Önerilen algoritmalar bir dağıtım firması tarafından sağlanan gerçek veri üzerine test edilmiş ve elde edilen sonuçların firmanın ulaştırma politikasına olumlu etkisi tartışılmıştır.

Container Loading (CL) is a quite interesting and very difficult problem to solve. Given a set of small rectangular items and a rectangular container with known dimensions, the aim is to load the items into the container in such a way that maximum volume utilization of the container is achieved. The Operations Research (OR) literature classifies this problem as NP-hard. Due to the complex nature of the problem, in the first part of this thesis two swarm intelligence (SI) based solution approaches namely Ant Colony Optimization (ACO) and Bees Algorithm (BA) are offered to solve the CL Problem. The results obtained with these approaches are compared with the available approaches in the literature and the performances of these approaches are discussed. Comparison of the proposed approaches in terms of utilization ratio revealed that BA is the best performing algorithm. In addition to this, a CL decision support system - to determine and visualize the packing pattern of a CL problem - is also designed.In the second part, a multi-objective CL (MOCL) problem inspired from a real industrial problem is introduced. The main goal of the MOCL problem is to pack a group of items into the container without any overlap while maximizing the total weight of the packed items and the utilization rate of the container simultaneously. These two objectives are conflicting since the volume of an item is usually not proportional to its weight. The problem is solved via selected multi objective optimization methods (Goal Programming and Weighted-Sum) and the Simulated Annealing algorithm. The proposed algorithms are tested on real data provided by a distribution company and the positive impact of the obtained solution to the company?s transportation policy is discussed.