# Bin Packing Under Multiple Objectives - A Heuristic Approximation Approach Martin Josef Geiger

Abstract**— The article proposes a heuristic approximation approach to the bin packing problem under multiple objectives. In**
addition to the traditional objective of minimizing the number of bins, the heterogeneousness of the elements in each bin is minimized, leading to a biobjective formulation of the problem with a tradeoff between the number of bins and their heterogeneousness. An extension of the Best-Fit approximation algorithm is presented to solve the problem. Experimental investigations have been carried out on benchmark instances of different size, ranging from 100 to 1000 items. Encouraging results have been obtained, showing the applicability of the heuristic approach to the described problem.

## I. Introduction

T
HE term "bin packing" describes a class of well-known, classical problems with numerous applications in logistics, operations research and related disciplines. From single dimensional to multi-dimensional problems, various types can be identified in practice. Common to all is the overall task of packing a finite number ofn items into a minimum number of bins (knapsacks) subject to a set of practical constraints and requirements. These include given capacities of the bins, but also other considerations such as irregularly shaped bins, load balancing of the bins, etc.

Numerous approaches including exact, heuristic, and metaheuristic algorithms have been proposed for the resolution of bin packing problems, and a rich literature on packing problems exists, with important classifications by DYCKHOFF
[1] and more recently WASCHER ¨ et al. [2]. While the majority of approaches is dedicated to single-objective models, only minimizing the number of bins used, the multi-objective nature of many of these problems becomes more and more obvious.

Following early work of WASCHER ¨ [3], modern heuristics such as Particle Swarm Optimization have recently been applied to a multi-objective variant of the two-dimensional binpacking problem [4]. For the here considered multi-objective bin-packing problem however, no corresponding studies have been carried out to our knowledge.

The remainder of the article is organized as follows. Section II describes the multi-objective bin packing problem and its' underlying practical application. A heuristic approximation approach is presented in the following Section III. In brief, we propose an extension of the well-known best-fit heuristic, allowing the computation of a set of solutions that constitute an approximation to the set of efficient solutions. Experimental Martin Josef Geiger is with the Department of Industrial Management (510A), University of Hohenheim, 70593 Stuttgart, Germany
(phone: 0049-711-45923462; fax: 0049-711-45923232; email: mjgeiger@unihohenheim.de).

results of the approach to the problem are reported in Section IV, and conclusions are given in Section V.

## Ii. Problem Description

We consider a bin packing problem where a given number ofn items has to be packed inton bins, each of capacityc [5].

Each itemj is characterized by a weightwj and an additional attributeaj . While the weights refer to the size of the items and therefore have to be taken into consideration when filling up a bin to at most its' capacityc, the attributesaj describe properties of the items on a nominal scale. On the basis of this description, a comparison of two items **i, j** is possible such that they are either identical with respect toai andaj, ai=aj or not:ai6=aj . The goal of packing the items into bins can then be modeled as follows.

$$\begin{array}{ll}\mbox{minimize}&z_{1}=\sum_{i=1}^{n}y_{i}\\ \mbox{minimize}&z_{2}=\frac{1}{z_{1}}\sum_{i=1}^{n}u_{i}\\ \mbox{s.t.}&\sum_{j=1}^{n}w_{j}x_{ij}\leq cy_{i}\qquad i\in N=\{1,\ldots,n\},\\ &\sum_{i=1}^{n}x_{ij}=1\qquad j\in N,\\ &y_{i}=0\mbox{or}1\qquad i\in N,\\ &x_{ij}=0\mbox{or}1\qquad i\in N,j\in N,\end{array}$$  where

$$\begin{array}{r c l}{{y_{i}}}&{{=}}&{{\left\{\begin{array}{l l}{{1}}&{{\mathrm{if~bin~}i\mathrm{~is~used}}}\\ {{0}}&{{\mathrm{otherwise}}}\end{array}\right.}}\\ {{x_{i j}}}&{{=}}&{{\left\{\begin{array}{l l}{{1}}&{{\mathrm{if~item~}j\mathrm{~is~assigned~to~bin~}i}}\\ {{0}}&{{\mathrm{otherwise}}}\end{array}\right.}}\\ {{u_{i}}}&{{\mathrm{counts~the~number~of~distinct~attributes~in~bin~}i.}}\end{array}$$

Expression (1) minimizes the number of bins. The second objective given in (2) minimizes the average heterogeneousness of the bins. To do this, the number of distinct attributesui is counted for each bini. Unused bins (yi = 0) have a value ofui = 0. Used bins (yi = 1) have a possible minimum value ofui = 1. This is the case when all items in the particular bin have the identical nominal attribute. The values ofui are bounded by either the number of items assigned to a bin or the number of distinct attributes over all itemsi.