Theory and MethodologyA hybrid genetic algorithm for the container loading problem
Section snippets
Introduction and formulation of the problem
The efficient stowage of goods in means of transport can often be modelled as a container loading problem. In this problem, a set of rectangular packages (boxes) has to be arranged in one or more rectangular containers in such a way that optimum use is made of the available container space. Where necessary, additional constraints must be met, e.g., a weight constraint for the stowed load.
In the literature, container loading problems are differentiated in several ways (cf. Dyckhoff and Finke,
Solution concept
The overall procedural solution concept can be formulated as follows:
- •
The hybrid GA is used to generate stowage plans with a layer-type structure. Each generated solution consists of several vertical, cuboid-shaped and non-overlapping layers parallel to the face walls of the container. The layers follow one another without any gaps. Each layer contains one or more boxes which do not project into adjacent layers.
- •
The height and width of a layer coincide with the corresponding container dimensions.
The basic heuristic
The basic heuristic used to generate and complete stowage plans is derived from the heuristic developed by Gehring et al. (1990). While the general procedure of this heuristic is retained, the heuristic elements and rules are largely replaced.
Layers are generated in two steps:
- •
A layer is initially defined by stipulating a layer-determining box and its rotation variant.
- •
The layer is then filled with the layer-determining box and in general with other boxes. The filling is performed with the core
The genetic algorithm
Since the problem representation used by the GA has already been specified (cf. Section 2), the generic and procedural aspects are now in the foreground. Fig. 7 shows the rough procedure of the GA.
The size of the population npop is held constant during evolution. For reproduction the model of generational replacement is used.
Solutions of a subsequent generation are generated by means of a crossover operator and a mutation operator. The mutation operator has two variants, called standard mutation
The inclusion of required constraints
The given constraints are to be considered under two aspects. Firstly, it must be guaranteed that generated solutions meet “hard” constraints. In addition, certain procedural modifications should ensure that even for constrained problems a high volume utilisation is achieved. The consideration of constraints (C1)–(C5) will now be described in detail.
(C1) Orientation constraint: In order to take account of an orientation constraint (C1) the selection of the rotation variant for a box placing is
Test of the hybrid GA
The following test demonstrates the performance of the hybrid GA in comparison to other methods. In the following, the underlying test problems, the considered methods and the derived numerical results are described.
Concluding remarks
The presented hybrid GA for loading a single container is particularly suitable for strongly heterogeneous problems. The algorithm takes account of some constraints which are relevant in practice. Its good performance and superiority to comparative methods was verified in an extensive test. The use of a time limit kept the required computing times within acceptable limits.
The algorithm includes a hybridisation concept which was recommended by Michalewicz (1992). According to this concept,
References (24)
- et al.
Loading pallets with non-identical items
European Journal of Operational Research
(1995) - et al.
Issues in the development of approaches to container loading
Omega
(1995) - et al.
A computer-based heuristic for packing pooled shipment containers
European Journal of Operational Research
(1990) - et al.
A genetic algorithm for solving the container loading problem
International Transactions of Operational Research
(1997) - et al.
An AND/OR-graph approach to the container loading problem
International Transactions of Operational Research
(1994) - Bortfeldt, A., 1994. A genetic algorithm for the container loading problem. In: Proceedings of the Conference on...
- et al.
Ein Tabu Search-Verfahren für Containerbeladeprobleme mit schwach heterogenem Kistenvorrat
Operations Research Spektrum
(1998) - Davies, A.P., Bischoff, E.E., 1998. Weight distribution considerations in container loading. Working Paper, European...
- et al.
Cutting and Packing in Production and Distribution
(1992)
Genetic Algorithms and Grouping Problems
Cited by (253)
Solving a 3D bin packing problem with stacking constraints
2024, Computers and Industrial EngineeringA Large Neighbourhood Search Algorithm for Solving Container Loading Problems
2023, Computers and Operations ResearchIntegrated warehouse assignment and carton configuration optimization using deep clustering-based evolutionary algorithms
2023, Expert Systems with ApplicationsRobust optimization and data-driven modeling of tissue paper packing considering cargo deformation
2023, Computers and Industrial EngineeringCitation Excerpt :The CLP can be usually distinguished in two categories, which can be either input minimization, where the goal is to pack a pre-determined amount of cargo in as few containers as possible, or output maximization, where a subset of cargo is packed in a fixed amount of containers such that their total value is maximized (Zhao et al., 2016). Efforts in CLP literature have been mainly devoted to developing constraints (Bortfeldt & Wäscher, 2013; Ramos et al., 2018), heuristics (Pisinger, 2002; Toffolo et al., 2017),exact methods (Chen et al., 1995; do Nascimento et al., 2021) and evolutionary algorithms (Bortfeldt & Gehring, 2001; Jamrus & Chien, 2016) to better address and solve complex CLPs. The reader is referenced to the recent works of Zhao et al. (2016) and Silva et al. (2019) for a comparative review of heuristics and exact algorithms, respectively.
The pallet-loading vehicle routing problem with stability constraints: The pallet-loading vehicle routing problem with stability constraints. Second revision
2022, European Journal of Operational Research