An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem

In this paper we consider the two-dimensional (2D) rectangular packing problem, where a fixed set of items have to be allocated on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left (BL) stability, are hybridised with three meta-heuristic algorithms (genetic algorithms (GA), simulated annealing (SA), naı̈ve evolution (NE)) and local search heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms, their performance is compared to random search (RS) and heuristic packing routines.     

The Three-Dimensional Pallet Chart: An Analysis of the Factors Affecting the Set of Feasible Layouts for a Class of Two-Dimensional Packing Problems

The two-dimensional orthogonal packing problem of packing identical rectangles into a large containing rectangle is important in pallet loading and has recently received much attention in O.R. publications. In this paper, we examine the conditions under which the set of feasible layouts remains unchanged and show that these conditions can be represented by a series of planes in three-dimensional space. We call this representation the three-dimensional pallet chart because it is an extension of the two-dimensional pallet charts presently used in many practical situations. The strength of this result is demonstrated by three examples of its use. Accurate two-dimensional charts are produced from the three-dimensional version with a minimum of calculation, and a complete sensitivity analysis to changes in box and pallet dimensions can be carried out visually by viewing the chart at different angles. Finally, the result is used to generate a new procedure for determining the maximum number of rectangles which can be fitted. This method is shown to be accurate for over 90% of observations in a random sample of 5000—an improvement of 20% over previous methods.     

Port space allocation with a time dimension

In the Port of Singapore, as in many other ports, space has to be allocated in yards for inbound and transit cargo. Requests for container space occur at different times during the planning period, and are made for different quantities and sizes of containers. In this paper, we study space allocation under these conditions. We reduce the problem to a two-dimensional packing problem with a time dimension. Since the problem is NP-hard, we develop heuristic algorithms, using tabu search, simulated annealing, a genetic algorithm and ‘squeaky wheel’ optimization, as solution approaches. Extensive computational experiments compare the algorithms, which are shown to be effective for the problem.     

Two-Dimensional Finite Bin-Packing Algorithms

Given a set of rectangular pieces, the two-dimensional bin-packing problem is to place the pieces into an open-ended bin of infinite height such that the height of the resulting packing is minimized. In this paper we analyse the performance of two-dimensional bin-packing heuristics when applied to the special case of packing into finite bins. We develop new bin-packing heuristics by adapting the bottom-left packing method and the next-fit, first-fit and best-fit level-oriented packing heuristics to the finite-bin case. We present our implementation of these algorithms, and compare them to other finite-bin heuristics. Our computational results indicate that the heuristics presented in this paper are suitable for practical use, and behave in a manner which reflects the proven worst-case bounds for the two-dimensional open-ended bin-packing problem.     

The G4-Heuristic for the Pallet Loading Problem

A new heuristic for the well-known (two-dimensional orthogonal) pallet loading problem (PLP) is proposed in this paper. This heuristic, referred to as G4-heuristic, is based on the definition of the so-called G4-structure of packing patterns. The G4-structure is a generalization of the common used block structure of packing patterns which requires the same orientation of packed boxes within each block. The G4-heuristic yields in approximately 99% of the test instances an optimal solution and solves all instances exactly where at most 50 boxes are contained in an optimal packing. Although the algorithm is pseudo-polynomial the computational experiments reported show that also instances with more than 200 packed boxes in an optimal solution can be handled with a small amount of computational time. Moreover, so far there is not known any instance where the gap between optimal value and the value obtained by the G4-heuristic is larger than one box.     

New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems

We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.     

Exact algorithms for the two-dimensional strip packing problem with and without rotations

We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90° rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.     

Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems

A popular approach when using a genetic algorithm in the solution of constrained problems is to exploit problem specific information by representing individuals as ordered lists. A construction heuristic is then often used as a decoder to produce a solution from each ordering. In such a situation further information is often available in the form of bounds on the partial solutions. This paper uses two two-dimensional packing problems to illustrate how this information can be incorporated into the genetic operators to improve the overall performance of the search. Our objective is to use the packing problems as a vehicle for investigating a series of modifications of the genetic algorithm approach based on information from bounds on partial solutions.     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

An Algorithm to Optimize the Layout of Boxes in Pallets

The problem of Optimum Pallet Layout at Rowntree Mackintosh Ltd is discussed. Production constraints reduce this three-dimensional box packing problem into the two-dimensional problem of packing large numbers of identical rectangles orthogonally into fixed-size containing rectangles. The exact solution procedure was found to require prohibitive amounts of computer time. A non-exact procedure is therefore described, its validity demonstrated, and the results obtained exhibited graphically in the form of a Pallet Layout Chart. This work has been implemented at Rowntree Mackintosh Ltd where improved pallet layouts and better design of new box shapes have resulted in cash savings.