yash8005 / three-dimensional-bin-packing-problem

The Three-Dimensional Bin Packing Problem (3BP) consists of allocating, without overlapping, a given set of three dimensional rectangular items to three-dimensional identical finite bins. The problem is NP hard in the strong sense, and finds many industrial applications. We in this process have made used to heuristic approach rather than greedy algorithm.

Three-Dimensional-Bin-Packing-Problem

ABSTRACT

The Three-Dimensional Bin Packing Problem (3BP) consists of allocating, without overlapping, a given set of three dimensional rectangular items to three-dimensional identical finite bins. The problem is NP hard in the strong sense, and finds many industrial applications. We in this process have made used to heuristic approach rather than greedy algorithm.

INTRODUCTION

Given a set of n three-dimensional rectangular items, each characterized by width wj, height hj and depth dj and an unlimited number of identical three-dimensional rectangular containers (bins) having width 2.3m, height 3 m and depth 12 m, the Three-Dimensional Bin Packing Problem (3BP) consists of orthogonally packing, without overlapping, all the items into the minimum number of bins. It is assumed that the items have fixed orientation, i.e., they cannot be rotated. We will call base of an item (resp. bin) its wj * hj (resp. W*H) side. We assume, without loss of generality, that all the input data are positive integers, and that wj <2.3m, hj <3m and dj <12m

Three-dimensional packing problems have relevant practical interest in industrial applications such as, e.g., cutting of foam rubber in arm-chair production, container and pallet loading, and packaging design. Although 3BP is a simplified version of real-world problems, in many cases it arises as a sub problem.

In our project we have approached it with heuristic algorithm in this the solution yielded may not be the best or efficient with respect to the problem but it is one of many solutions possible for the problem while in greedy algorithm the output obtained is generally the more efficient and optimum for the problem