In this paper, the author proposes a heuristic algorithm to solve the one-dimensional bin-packing problem with additional constraints. The proposed algorithm has been applied to solve a practical vehicle-allocation problem. The experimental results show that the proposed heuristic provides optimal or near-optimal results, and performs better than the first fit decreasing algorithm, modified to incorporate additional constraints.
A
well-known one-dimensional bin-packing problem solves for minimum number of bins
to pack `N' items subject to various constraints, viz., an item should be accommodated
in a single bin, etc. This is an NP-hard problem (Coffman et al., (1978))
and many authors have developed algorithms to solve the classical (single-dimensional
items and with no additional constraints) bin-packing problem. Eilon and Christofides
(1971) had developed a heuristic procedure to solve the problem with different
objective viz., minimize the number of bins/slack; minimize the un-accommodated
number/value of items; and a combination of both. Later, Johnson et al.,
(1974) developed the First Fit Decreasing (FFD) and Best Fit Decreasing (BFD)
algorithms to solve the one-dimensional bin-packing problem. They also calculated
the upper bound as {(11/9) * N + 4} vehicles, where,`N' is the optimal number
of bins. Recently, Gupta et al. (1999) developed the minimum bin slackness
algorithm to solve the bin-packing problem. They have also utilized local search
method and showed that their algorithm provides better results than FFD algorithm.
There
are many extensions in the classical bin-packing algorithm to model real-world
situations. Some of the extension areas are packing two-dimensional (Martello
and Vigo (1998)) and three-dimensional (Martello et al., (2002)) items,
calculating bounds of various bin-packing problems (Fekete et al., (2001),
Fleszar et al., (2002), Labbe et al., (2003), etc.), and incorporating
additional constraints (Robb and Trietsch (1999), Ralphs et al., (2003),
etc.).
Other
extension areas of bin-packing problems deal with constraints like, grouping of
items for packing and maximum number of items allowed in a bin. Anily and Federgruen
(1991) solved the problem where items are clubbed into various groups for services
i.e., packing. They utilized the concept in vehicle routing problems, partitioning
problems etc. Rhee (1993) considered the maximum number of items per bin and demonstrated
that the difference between the expected number of bins is of the order of square
root of `N', when the maximum numbers of items is changed from two to three. The
benefit diminishes when they considered higher values of number of items. |
