A two-phase constructive algorithm for the single container mix-loading problem

Abstract

Manufacturers usually store their products in palletized storage units (PSUs). PSUs are convenient for storage but sometimes not cost-effective for transportation because they may result in large empty spaces of waste in containers. To improve the utilization of its containers, a manufacturer is willing to remove products from PSUs (a process called depalletizing) and load the individual products, together with other PSUs, into a container. Once a PSU is depalletized, its products must be loaded into the container. No PSU can be depalletized if the total volume of complete PSUs loaded in the container is not maximized. We introduce this problem as the single container mix-loading problem (SCMLP). Then, we develop a two-phase constructive algorithm for the SCMLP that uses a stochastic beam-search-based method developed for loading items into a given set of spaces as the sub-routine. In the first phase, the stochastic beam-search-based method is called upon to load PSUs into the container. In the second phase, a proper set of PSUs is selected, and the stochastic beam-search-based method is used to load all products of the selected PSUs into the remaining spaces in the container. The performance of our algorithm is demonstrated by experiments conducted on a set of instances generated from the historical data of the manufacturer. Besides, we also used the well-known 1500 single container loading problem instances to test the performance of our stochastic beam-search-based method, and the results showed that our approach is highly competitive with state-of-the-art methods.

1 Introduction

Our team collaborates with an international audio equipment manufacturer to solve problems that had emerged in its logistics process. The Manufacturers usually load their products onto pallets for storage. These loaded pallets are called Palletized Storage Units (PSUs) in the industry. To operate efficiently, a PSU usually consists of identical products. When delivering products, manufacturers load PSUs (instead of individual products) into containers (or trucks). Loading PSUs is convenient; however, large spaces on the tops or sides of the loaded PSUs could be wasted in each container. To improve the utilization of a container, the audio equipment manufacturer is willing to remove products from PSUs (a process called depalletizing) and load the products, together with other PSUs, into the container.

When a container delivered by the manufacturer arrives at its destination, all individual products loaded in it are rearranged into PSUs (a process called repalletizing). This is because moving PSUs from the port (or other unloading areas) to the customer’s warehouse is much more efficient and safe than moving individual products, and customers prefer to store PSUs rather than individual products in their warehouses. Therefore, once a PSU is depalletized, its products must be loaded into the container.

Both depalletizing and repalletizing increase the complexity of the manufacturer’s operations, thus increasing its operational costs. Only when the transportation cost saved by improving the volume utilization of each container is much higher than the operational cost induced by depalletizing and repalletizing would the manufacturer prefer to depalletize PSUs and load products, together with PSUs, into containers. As a result, the partner manufacturer constrains that no PSUs will be depalletized if the total volume of complete PSUs loaded in the container is not maximized.

To summarize, the audio equipment manufacturer would like to depalletize PSUs and load the individual products, together with other PSUs, into a container such that the volume utilization of the container is maximized. Once a PSU is depalletized, its products must be loaded into the container. No PSU should be depalletized if the total volume of complete PSUs loaded in the container is not maximized. We name the resulting optimization problem the Single Container Mix-Loading Problem (SCMLP) and formally define it in Sect. 3.

In Sect. 4, we develop a two-phase constructive algorithm for the SCMLP. The algorithm uses a stochastic beam-search-based method developed for loading items into a given set of spaces as a sub-routine. Beam search is a variant of the branch-and-bound technique. Unlike the traditional beam search, which expands the most promising nodes at each level of a search tree, we add the stochastic process to select the node randomly based on the solution quality of the nodes. In other words, the promising nodes will be given a high probability. In the first phase of our constructive algorithm, the stochastic beam-search-based method is called upon to load PSUs into the container. In the second phase, a proper set of PSUs is selected, considering the remaining volume of the container, and the stochastic beam-search-based method is used to load all products of the selected PSUs into the remaining spaces of the container.

We generate 70 test instances based on historical data provided by the audio equipment manufacturer, and we conduct extensive computational experiments to demonstrate the effectiveness of our approach, as described in Sect. 5.

Commonly, the manufacturer’s products are packaged in cuboid cartons. So, we use cartons to represent products in the following sections. To the best of our knowledge, there is no literature concerned with the single container mix-loading problem. However, the SCMLP can be considered an extension of the Single Container Loading Problem (SCLP). When no PSU can be depalletized, the single container mix-loading problem is reduced to the single container loading problem (SCLP). The 1500 well-studied SCLP instances by Bischoff and Ratcliff (1995) and Davies and Bischoff (1999) are selected for the experiments. The results show that our approach is highly competitive with state-of-the-art methods, and the stochastic strategy improves the results compared to the traditional beam search method. The detailed results are given in Sect. 5.

2 Literature review

The efficient loading of three-dimensional items into three-dimensional containers is a fundamental problem in the freight transportation and logistics industries. A tremendous amount of literature in operations research has been devoted to various container loading problems (Lim et al., 2013; Wang et al., 2013), from single-container versions to multiple-container ones(Wei et al., 2015; Kurpel et al., 2020).

In the Single Container Loading Problem (SCLP), given a fairly large set of small cuboid items and one cuboid container, we have to pack some or all of the items feasibly into the given container, such that the total value of the packed items is maximized. The assortment of small items could be identical, weakly heterogeneous, or strongly heterogeneous. The SCLP is an output maximization problem, according to the typology developed by Wäscher et al. (2007).

If the volume of an item is viewed as its value, the objective of the single container loading problem becomes maximizing the total volume of the packed items or, equivalently, minimizing the unused space in the container (George & Robinson, 1980). Single container loading problems can be further classified by the number of items of each type that can be packed into the container. If the number is limited with a lower and/or an upper bound, it is called a constrained problem; otherwise, it is an unconstrained problem.

The SCLP is a strongly $\mathcal{N}\mathcal{P}$-hard combinatorial optimization problem because the one-dimensional bin packing problem, which is an $\mathcal{N}\mathcal{P}$-hard optimization problem, is a special case (Martello et al., 2000). Therefore, it is not easy to solve the SCLP to optimality. The literature on exact algorithms for SCLP is relatively scarce, and we list some relevant studies as follows.

Martello et al. (2000) developed a branch-and-bound algorithm for SCLP, where only the corner points are considered as the candidate place. Later, Den Boef et al. (2005) pointed out that only considering the corner points is insufficient and proposed a new approach based on constraint programming. Hifi (2004) proposed two exact algorithms for a three-dimensional cutting problem, equivalent to the single container loading problem in the packing context. The first algorithm uses the dynamic programming technique, and it is extended from an approach designed for the two-dimensional version (Gilmore & Gomory, 1966). The second algorithm also adapts a method developed for the two-dimensional version (Hifi & Zissimopoulos, 1996), which is based on a graph search procedure with a depth-first search strategy. Most recently, Fekete et al. (2007) developed a two-level tree search algorithm for solving high-dimensional packing problems, including various container loading problems, to optimality. They first invented a data structure for feasible packing based on graph-theoretic characterizations of interval graphs and then combined the data structure with other heuristics and the lower bounds they computed in earlier research works (Fekete & Schepers, 1997a, b, 2004a, b). They conducted computational experiments for instances with up to 80 small items, and more than 70% of these instances were solved optimally. Silva et al. (2019) provided an up-to-date comparative study concerning the most significant exact methods associated with SCLP.

Lots of heuristics have been developed to handle instances with a larger size; these heuristics can be classified into four groups (Pisinger, 2002; Zhao et al., 2016): wall building approaches (George & Robinson, 1980), stack building approaches (Gehring & Bortfeldt, 1997), cuboid arrangement (or block building) approaches (Eley, 2002), and guillotine cutting approaches (Morabito & Arenales, 1994). This classification can be extended by adding horizontal-layer building approaches (Bischoff & Ratcliff, 1995).

As the wall-building approaches, the container is filled with walls (or vertical layers) of small items across one of its horizontal dimensions. George and Robinson (1980) proposed the first wall-building method. Several variants have been presented since then. Bischoff and Marriott (1990) compared 14 different heuristics based on the framework by George and Robinson (1980). Bischoff and Ratcliff (1995) pointed out that wall-building approaches might produce unstable packing, which is dangerous in transportation. They introduced a horizontal-layer building approach, in which the container is loaded from the floor upwards using layers of up to two types of small items. This approach extends the heuristic method proposed by Bischoff et al. (1995).

After the development of the wall building and horizontal-layer building approaches, stack-building approaches were proposed, in which the container is packed with stacks (or towers/columns) of small items. Gehring and Bortfeldt (1997) developed a two-step stack-building approach. In the first step, small items are stacked into towers, in which each item is fully supported from below by the surface of another item or by the container floor. Then, a genetic algorithm is called upon to arrange the towers into the container, thus solving a two-dimensional packing problem.

All the above three types of building approaches simulate the process of workers packing items into a container manually.

The container in the cuboid arrangement (or block building) approach is filled by cuboid arrangements (or blocks) made up of items (Bortfeldt & Gehring, 1998). Eley (2002) built the block using identical items, developed a greedy search method to arrange the blocks, and then improved the solution found by the greedy method using a tree search approach. Bortfeldt et al. (2003) and Mack et al. (2004) followed this work by using blocks composed of identical items in their heuristic methods. Later, Fanslau and Bortfeldt (2010) improved the performance of cuboid arrangement approaches by introducing blocks with small inner gaps. Zhu and Lim (2012) and Zhang et al. (2012) proved the efficiency of using both blocks of identical items and blocks of different items in heuristic methods. Araya and Riff (2014) improved the results further by replacing the greedy look-ahead heuristic with the beam search. Recently, Araya et al. (2017) introduced a new heuristic function for selecting boxes and got the best results on the 1600 well-known benchmark instances. Araya et al. (2020) extended the beam search approach to the bi-objective container loading problem, where the second objective is maximizing the loaded boxes’ total profit.

Morabito and Arenales (1994) proposed the guillotine-cutting approach. In their approach, the container is partitioned by guillotine cuts into small parts in which only one item can be packed. The result of partitioning the container is called a “guillotine partition pattern", and each guillotine partition pattern can be represented in an AND/OR graph. The best guillotine partition pattern (corresponding to the best solution to the SCLP) can be found by determining the most valuable complete path in the AND/OR graph.

In a departure from all the above approaches, Ngoi et al. (1994) developed an algorithm that does not make use of any item arrangement (e.g., walls, stacks, etc.) and does not constrain the loading sequence (e.g., from back to front, from floor to ceiling, etc.). Their algorithm is based on a spatial representation technique proposed by Ngoi and Whybrew (1993), in which the position and dimensions of each packed item and each empty space are stored in a three-dimensional matrix. The algorithm iteratively selects an item and places it in empty space until specific stopping criteria are satisfied. Similarly, Huang and He (2009); He and Huang (2011) proposed caving degree approaches for the single container loading problem, which do not use any special arrangement of items and do not constrain the loading sequence. They developed a placement rule based on the caving degree, which always favors corners or even caves of the container when packing items, such that the items are packed as compactly as possible.

Lim et al. (2003) also developed an approach that does not involve any special arrangement of items but does stipulate that items should be packed from the floor up. In their Multi-Faced Buildup method, all container walls can be used as a base (or floor) to place items. Additionally, the authors combined the Multi-Faced Buildup technique with a look-ahead strategy to improve the solution quality.

Among all the methods mentioned above, some are classic heuristic methods, while others are advanced. The methods proposed by Bischoff and Ratcliff (1995); Bischoff et al. (1995); Lim et al. (2003) belong to the classic heuristic methods. The advanced heuristic methods include tree search methods (Eley, 2002; Fanslau & Bortfeldt, 2010; Pisinger, 2002; Terno et al., 2000; Zhang et al., 2012), graph search methods (Morabito & Arenales, 1994), the Simulated Annealing algorithms (Mack et al., 2004), the Tabu Search algorithms (Bortfeldt et al., 2003), the Genetic Algorithms (Bortfeldt & Gehring, 2001; Gehring & Bortfeldt, 1997, 2002), and the Greedy Randomized Adaptive Search Procedures (Moura & Oliveira, 2005; Parreño et al., 2008). Commonly, classic heuristic methods are used to construct initial solution(s) for local search methods, such as the Simulated Annealing algorithms, the Tabu Search algorithms, and population-based heuristics (e.g., the Genetic Algorithms). For a comparative review of 3D container loading algorithms, the reader is referred to Zhao et al. (2016).

The SCMLP we proposed is closely related to the Container Loading Problem for Pallets with Infill Boxes (CLPIB) proposed by Sheng et al. (2016). In the CLPIB, the bottoms of each pallet must be fully supported by the container floor or by the top of a single pallet. While in the SCMLP, each pallet could be fully supported by the container floor or any combination of pallets and cartons. Therefore, the space utilization of a container in the SCMLP is higher, and the solution space of SCMLP is larger than those in the CLPIB.

3 Problem definition of SCMLP

We are given a container denoted by C, whose dimensions are L, W, and H and whose volume is $V=LWH$, and a set of PSUs denoted by ${\mathcal {P}}$. Each PSU $p\in {\mathcal {P}}$ has the dimensions $L_p$, $W_p$, and $H_p$ and the volume $V_p=L_pW_pH_p$. We use an indicator $d_p$ to denote whether PSU $p\in {\mathcal {P}}$ can be depalletized. If $d_p$ equals 1, PSU p is depalletizable; otherwise, p is not depalletizable. For example, the cartons in some PSUs are fragile, and a wooden box may be used during palletizing to protect the cartons from being crushed. The PSUs, in this case, are not depalletizable. Each PSU comprises $N_p$ identical cartons, and each carton in the PSU p has the dimensions $l_p$, $w_p$, and $h_p$ and the volume $v_p=l_pw_ph_p$. The set of all cartons in the PSU p is denoted by ${\mathcal {I}}_p$. We use $V_{I_p} = N_pv_p$ to denote the volume of all cartons in p. It should be pointed out that the volume of a PSU may be larger than the total volume of the cartons contained within it ($V_p \ge V_{I_p}$) because gaps between cartons may exist in each PSU.

We define a depalletizable PSU set, denoted by ${\mathcal {D}}$, as a set of PSUs (${\mathcal {D}} \subseteq {\mathcal {P}}$) whose elements are all depalletizable ($d_p = 1,\ \forall p\in {\mathcal {D}}$), and we use the set $\mathcal{D}\mathcal{P}$ to store all of the depalletizable PSU sets. Suppose there are n depalletizable PSUs in the set ${\mathcal {P}}$. In this case, the cardinality of the set $\mathcal{D}\mathcal{P}$ is $2^n$. Note that the empty set belongs to the set $\mathcal{D}\mathcal{P}$.

As described in Sect. 1, in the single container mix-loading problem, we need to select two disjoint subsets of PSUs:

• 1. ${\mathcal {S}}_1 \subseteq {\mathcal {P}}$: ${\mathcal {S}}_1$ is a set of complete PSUs.

• 2. ${\mathcal {S}}_2 \in \mathcal{D}\mathcal{P}$: ${\mathcal {S}}_2$ is a depalletizable PSU set.

Next, we need to load all of the PSUs in ${\mathcal {S}}_1$ and all of the cartons in the set ${\mathcal {I}}=\cup _{p\in {\mathcal {S}}_2} {\mathcal {I}}_p$ into the container C, such that the total volume of the complete PSUs in the set ${\mathcal {S}}_1$ is maximized and the volume utilization of the container C is maximized. The volume utilization of the container C is defined as:

$$\begin{aligned} \frac{\sum _{p\in {\mathcal {S}}_1} V_p + \sum _{i\in {\mathcal {I}}} v_i}{V} \end{aligned}$$

(1)

We define that a set of items, either PSUs or cartons, can be loaded into the container if the following geometric constraints are satisfied:

• Containment: Each item must be placed completely within the container.

• Orthogonal placement: Each item must be placed with its edges parallel to those of the container.

• No overlap: Any two items inside the container must be interior-disjointed.

• Full support: The bottom of any item in the container must be fully supported by either the container floor or the tops of other items.

• Orientation restriction: Every item must be placed in one of its allowed orientations. We use three flags ($f^l$, $f^w$, and $f^h$) to indicate whether an item can be placed with its length, width, and height, respectively, aligned with the vertical axis of the container. For example, if $f^h = 1$, the item can be placed with its height aligned with the vertical axis of the container.

  • For any pallet $p\in {\mathcal {P}}$, we have $f_p^l = 0$, $f_p^w = 0$, and $f_p^h = 1$.

  • For any carton $i\in {\mathcal {I}}_p,\ \forall p\in {\mathcal {P}}$, we have $f_i^l = 1$, $f_i^w = 1$, and $f_i^h = 1$.

4 A two-phase constructive method

A two-phase constructive algorithm is developed for the SCMLP. It uses a stochastic beam-search-based method developed for loading items into a given set of spaces as its sub-routine. Beam search is a branch-and-bound technique variant that expands the most promising nodes at each level of a search tree. In the first phase of our constructive algorithm, the stochastic beam-search-based method is called upon to load PSUs into the container. In the second phase, a proper set of PSUs is selected, considering the remaining volume of the container, and the stochastic beam-search-based method is used to load all products of the selected PSUs into the remaining spaces of the container.

Our constructive algorithm is a block-building approach, according to the classification proposed by Pisinger (2002). In block-building approaches, blocks of items, rather than individual items, are loaded into residual spaces.

4.1 A stochastic beam-search based method

Beam search is a tree search method whose search tree is built with a breadth-first strategy. However, in contrast to the breadth-first search, at each level of the search tree, only a predetermined number of nodes are selected by an evaluation function and expanded. This predetermined number is referred to as the beam width. If the beam width is infinite, all nodes will be selected and expanded at each level of the search tree; thus, the beam search is equivalent to the breadth-first search.

Each intermediate node of the search tree represents a partial solution to the problem, and each leaf node represents a complete solution. Beam search does not guarantee termination with an optimal solution because the nodes leading to the optimal solutions may be pruned.

We present a stochastic beam-search-based method that iteratively calls upon a beam search in the following sections. This method solves the problems of loading three-dimensional items into a given set of three-dimensional residual spaces in a container, such that the total volume of loaded items is maximized. Here, the items refer to the PSUs and cartons in the SCMLP. It is a block-building approach in which blocks of identical items, rather than individual items, are loaded into the residual spaces.

4.1.1 Node representation of beam search

Four elements represent each node of the search tree of the beam search we developed:

• A set of remaining items, denoted by I.

• A set of blocks, denoted by B.

• A set of three-dimensional residual spaces in the container C, denoted by R.

• A set of loaded items, denoted by LI.

A block $b\in B$ is the minimum bounding cuboid of an arrangement of items from the set I. The items in block b are identical, and they are arranged in such a way as to satisfy the orthogonal placement constraint, the no-overlap constraint, the full-support constraint, and the orientation restriction described in Sect. 3. We present the method for generating blocks below.

A residual space $r\in R$ is a fully-supported maximal space that does not overlap with any placed blocks in the container C. The maximal space concept was first introduced by Lim et al. (2003) and has been used in several other works (He & Huang, 2011; Parreño et al., 2008; Zhu & Lim, 2012). Figure 1 shows three new residual spaces generated when a block is placed in the residual space r. We describe the generation approach for fully-supported maximal spaces below.

Fig. 1

Three new residual spaces ($r_1$, $r_2$, $r_3$) generated when a block is placed in the residual space r

In the root node of the search tree, I contains all available items, B contains the blocks generated using the items in the set I, R contains all available spaces, and LI includes the already packed items. Each intermediate node of the search tree represents a partial solution to the problem, in which sets I, B, R, and LI are all non-empty. A leaf node represents a complete solution to the problem, in which either I is an empty set meaning all the items are packed, or no item in I can be loaded into any space in R.

Block generation: In existing block-building approaches for container loading problems, two types of blocks are generally used: namely, the simple block and the general block. A simple block consists of identical items, and all items in a simple block are placed with the same orientation. Therefore, each item in a simple block is fully supported from below by either the top of another item or the base of the block. A general block may either be composed of two or more types of items or be composed of identical items with different orientations. Special operations are involved in generating general blocks to satisfy the full-support constraint.

Both simple blocks and general blocks are proven to be effective when loading items into spaces (Bortfeldt et al., 2003; Eley, 2002; Fanslau & Bortfeldt, 2010; Mack et al., 2004; Zhang et al., 2012; Zhu & Lim, 2012). Zhu et al. (2012) observed that using both simple blocks and general blocks are better for solving problems with strongly heterogeneous items while using only simple blocks is better for solving problems with identical or weakly heterogeneous items. We use simple blocks in our stochastic beam-search-based method because the full-support constraint is easily satisfied, and the PSUs and cartons in the SCMLP are weakly heterogeneous.

A simple block of item $i\in I$ can be generated by replicating the item i for $n_l$, $n_w$, and $n_h$ times along the length, width, and height, respectively, of the block. Therefore, all simple blocks composed of item i can be generated by enumerating all possible values of $n_l$, $n_w$, and $n_h$. Note that a single item i is also a simple block. The algorithm to generate simple blocks will be called upon only once at the beginning of the stochastic beam-search-based method, and all the simple blocks form the set B of the root node of the search tree. Simple blocks with the same dimensions and containing the same set of items are considered to be duplicates, so only one of these is stored, and the others are deleted. Simple blocks too large to be loaded into any residual space in the root node are also deleted.

Residual space generation: The residual spaces in the container C are fully-supported maximal spaces in our beam search. When no block is placed in a container, the whole space within the container is a fully-supported maximal space. Once a block is placed at a corner of the residual space r, three fully-supported maximal spaces are generated by (1) performing a guillotine cut parallel to the length of r (see $r_1$ in Fig. 1); (2) performing a guillotine cut parallel to the width of r (see $r_2$ in Fig. 1); and (3) cutting a space above the block, such that the base of the space is the top of the block (see $r_3$ in Fig. 1). Note that the spaces $r_1$ and $r_2$ in Fig. 1 overlap.

Due to overlapping between fully-supported maximal spaces, it may intrude into other residual spaces when a block is placed at a corner of residual space. Figure 2 shows an example in which a block b is placed in the residual space $r_1$ and intrudes into the residual space $r_2$.

Fig. 2

A block b intrudes into the residual space $r_2$ when it is placed in the residual space $r_1$

Once a block b is placed in a residual space, the intruded residual spaces must be updated. We first perform, at most, two guillotine cuts parallel to the length of r, which will result in two fully-supported maximal spaces (see $r_2$ and $r_4$ in Fig. 3). Next, we perform, at most, two guillotine cuts parallel to the width of r, resulting in two fully-supported maximal spaces (see $r_1$ and $r_3$ in Fig. 3). Finally, we cut a space above the block, such that the base of the space is the top of the block (see $r_5$ in Fig. 3). No space below the block will be generated because of the full-support constraint. Therefore, we will get, at most, five fully-supported maximal spaces when updating an intruded residual space. Figure 3 demonstrates the five new residual spaces generated when a block b intrudes into the residual space r.

Fig. 3

Five new residual spaces ($r_1$, $r_2$, $r_3$, $r_4$, and $r_5$) generated when a block b intrudes into the residual space r

4.1.2 Child node generation of beam search

Consider an intermediate node whose elements are I, B, R, and LI. We call this a parent node. One child of the parent node is generated by placing a block $b\in B$ into a residual space $r\in R$.

Space selection:

Each residual space is a cuboid and has eight corners. Each corner of the residual space r is associated with a corner of the container C (see Fig. 4). For example, the front-left-bottom corner of r is related to the front-left-bottom corner of C. The Manhattan distance between a corner of the residual space r and the corresponding corner of the container C is defined as $|x_1-x_2 |+|y_1-y_2 |+ |z_1-z_2 |$, where ($x_1$,$y_1$,$z_1$) is the coordinate of the corner of r and ($x_2$,$y_2$,$z_2$) is the coordinate of the corner of C (see Fig. 4). The corner of r with the smallest Manhattan distance from its corresponding corner of C is called the anchor corner, and the smallest Manhattan distance is called the anchor distance.

Fig. 4

The relationship between the corners of the residual space r and the corners of the container C

When generating a child of an intermediate node, the beam search selects the usable residual space of R with the smallest anchor distance. Ties are broken by larger volume of the residual space. A usable residual space is a residual space that is large enough to accommodate at least one block of B.

Block selection:

Given the selected residual space $r\in R$, we use function $f(b,r)=V-(V_{waste}+V_{loss})$ to evaluate each block $b\in B$. The block with the largest value of f(b, r) is selected. This function was introduced by Zhu and Lim (2012). V is the total volume of all the items in block b. $V_{waste}$ is the difference between the volume of block b and V. $V_{loss}$ is the lower bound of the unusable volume of the residual space r. The unusable volume of the residual space r is the difference between the volume of r and the maximum total volume of items in I that can be loaded into r.

If the block b cannot be loaded into the residual space r, the function f(b, r) returns negative infinity; otherwise, $V_{loss}$ is computed as follows. We first calculate the remaining length (width, height) of the residual space r that can be used after placing the block b and denote this length (width, height) by l (w, h). Next, we find the dimensions of each item $i\in I$ that can be placed along the length (width, height) of the residual space r and store all these dimensions in the set $L_r$ ($W_r$, $H_r$). Then, we solve the (one-dimensional) knapsack problem, in which the capacity of the knapsack is l (w, h) and the set of items to be packed in the knapsack is $L_r$ ($W_r$, $H_r$), using the standard Dynamic Programming (DP) algorithm proposed by Martello and Toth (1990) which runs in pseudo-polynomial time. Suppose the optimal solution value returned by the dynamic programming algorithm is $l_{max}$ ($w_{max}$, $h_{max}$). In this case, $V_{loss}$ is equal to $V(r)-(l(b)+l_{max})\times (w(b)+w_{max})\times (h(b)+h_{max})$, where V(r) is the volume of the residual space r and l(b), w(b), and h(b) are the length, width, and height, respectively, of the block b.

Once the block b is placed at the anchor corner of the selected residual space r, all four elements of the parent node (I, B, R, and LI) are updated. The updated elements are inherited by the child node generated by placing b in r.

Updating the Item Set I , the Block Set B , and the Loaded-Item Set LI : All items in b will be deleted from I and inserted into LI. Some blocks in B are also deleted because there are not enough items in I to form these blocks.

Updating the Residual-Space Set R : Once the block b is placed in the residual space r, new residuals will be generated according to the method described in Sect. 4.1.1. The residual space r will be deleted from the set R, and all newly generated residual spaces will be inserted into R. Due to the overlapping nature of the fully-supported maximal spaces, some spaces may be completely contained by other residual spaces. Therefore, a process is called upon to delete these completely contained residual spaces once new residual spaces are inserted into R. Some spaces are too small to accommodate any block in the updated block set B. These small residual spaces are marked as unusable but not deleted from R.

4.1.3 Node evaluation of beam search

In beam search, at each level of the search tree, only a number (beam width) of child nodes are selected for further expansion based on an evaluation approach. In our beam search, we use a greedy strategy to construct a complete solution from a given child node and use the total volume of loaded items in the complete solution to evaluate the child node.

The greedy strategy works as follows. Given a child node (I, B, R, LI) representing a partial solution to the SCMLP, a complete solution $(I^\prime ,B^\prime ,R^\prime ,LI^\prime )$ is constructed by iteratively calling upon the four operations:

• Select the usable residual space $r\in R$ with the minimum anchor distance.

• Select the block $b\in B$ with the maximum value of the function f(b, r).

• Place the selected block b in the selected residual space r.

• Update the item set, the block set, the residual-space set, and the loaded-item set into $I^\prime$, $B^\prime$, $R^\prime$, and $LI^\prime$.

This continues until no item remains in $I^\prime$, no usable residual space remains in $R^\prime$, or no item can be loaded into any usable residual space. Then, the evaluation function of the given child node is the volume utilization (the percentage of loaded items’ volume to that of the container) in the corresponding complete solution, which is denoted by $g(LI^\prime )$.

4.1.4 The stochastic beam-search based method

Our stochastic beam-search-based method is described in Algorithm 1, which iteratively calls upon the stochastic beam search presented in Algorithm 2.

Algorithm 1

The Stochastic Beam-Search Based Method

The input of the stochastic beam-search-based method includes a set of three-dimensional items I and a set of three-dimensional residual spaces R. bestSol is used to store the best complete solution found by the method, and it consists of four elements, $I_{best}$, $B_{best}$, $R_{best}$, and $LI_{best}$, which represent the set of remaining items, the set of blocks composed of items in $I_{best}$, the set of remaining residual spaces, and the set of loaded items, respectively. The beam width of our beam search is represented by the parameter w. w also determines the search effort because it limits the number of child nodes that can be generated and evaluated to be, at most, $w^2$, as presented in Algorithm 2. w is increased to $\lceil \sqrt{2} w \rceil$ after each execution of Algorithm 2, such that the search effort is doubled.

The stochastic beam search iteratively called upon in our beam-search-based method is described in Algorithm 2.

Algorithm 2

The Stochastic Beam-Search

The root node is initialized with the four elements I, B, R, and LI. A set N is used to store all of the nodes at the current level of the search tree. Each iteration in Algorithm 2 executes the following operations: 1) w child nodes of each node $n_i\in N$ are generated using process GenerateChildNodes shown as Algorithm 3, and all $w^2$ child nodes are stored in set $N^\prime$; 2) only w nodes in set $N^\prime$ are selected to compose the next level of the search tree using process Greedy shown as Algorithm 4. Note that $w^2$ child nodes will be generated for the root node, such that each level of the search tree has the same number of children (Araya & Riff, 2014). bestSol stores the best complete solution found by Algorithm 4.

The method for generating w child nodes of a given node $(I_i, B_i, R_i, LI_i)$ is presented in Algorithm 3.

Algorithm 3

Generate w Child Nodes of Node ($I_i, B_i, R_i, LI_i$)

A residual space $r\in R_i$ with the minimum anchor distance is selected, with details described in Sect. 4.1.2. Blocks in $B_i$ are ranked in descending order based on the value of f(b, r) (see Sect. 4.1.2), and the first w blocks in the rank are selected. If the number of available blocks in $B_i$ is smaller than w, all blocks in $B_i$ are selected. Then, at most w child nodes of $(I_i, B_i, R_i, LI_i)$ are generated by placing each selected block at the anchor corner of the selected residual space r.

Algorithm 4 describes the method for selecting w nodes from the set of child nodes of the current level of the search tree ($N^\prime$). For each child node $n_i=(I_i,B_i,R_i,LI_i)\in N^\prime$, we iteratively call upon Algorithm 3 with $w=1$ until all items in $I_i$ are loaded or no item in $I_i$ can be loaded into any residual space in $R_i$. The resultant node is a leaf node $leaf_i=(I_i^\prime ,B_i^\prime ,R_i^\prime ,LI_i^\prime )$ representing a complete solution, and it is evaluated using the function $g(LI_i^\prime )$ (see Sect. 4.1.3). Then, we rank all the nodes $n_i\in N^\prime$ into descending order based on the value of $g(LI_i^\prime )$. Unlike the traditional beam search method, we randomly select the first w/2 nodes in the rank and select the left w/2 nodes. The probability of selecting node $n_i$ is calculated by $e^{-10dv}$, where dv is the volume utilization difference between $LI_1^\prime$ and $LI_i^\prime$. In other words, the node whose complete solution has a larger volume utilization will be selected with a higher probability. Since each leaf node corresponds to a complete solution, we update the best solution bestSol with the first node in the ranking, if necessary. Note that if the cardinality of $N^\prime$ is smaller than w, all nodes of $N^\prime$ are selected.

Algorithm 4

Select w Nodes Using a Greedy Strategy

4.2 The two-phase constructive algorithm

We develop a two-phase constructive algorithm for the single container mix-loading problem described in Algorithm 5.

Algorithm 5

The Two-Phase Constructive Method

The inputs of the algorithm are the given set of PSUs (${\mathcal {P}}$) and the given container (C). In the first phase of our constructive algorithm, the stochastic beam-search-based method (Algorithm 1) is called upon to load PSUs in ${\mathcal {P}}$ into the given container C, such that the total volume of loaded complete PSUs is maximized. At the end of the first phase, if all of the given PSUs are loaded into the container or if there is no residual space in the container, the algorithm returns the solution found in the first phase (solP1) and terminates; otherwise, the algorithm continues with the second phase. Note that all the unusable residual spaces generated during the beam search are not deleted (see Sect. 4.1.2), so no residual space in the container means no usable or unusable residual space exists in the container.

In the second phase of the algorithm, we first store all the depalletizable PSUs that are not loaded into the container in the set D and store all the residual spaces in the container in the set R; meanwhile, we mark all the unusable residual spaces in R as usable. Suppose the total volume of all the residual spaces in R is $V_R$. If $V_R$ is smaller than the smallest carton volume of depalletizable PSU in I, no PSU in I can be loaded into any residual space in R; therefore, the algorithm returns the solution solP1 and terminates; otherwise, the second phase continues with a binary search.

The binary search determines the maximum volume of PSUs whose cartons can be loaded into the residual spaces in R. In each iteration of the binary search, first, Algorithm 6 is called upon to solve the integer programming problem SC and depalletize all the PSUs, which are selected by solving SC, into cartons.

Algorithm 6

Select PSUs in $I^*$ and Depalletize Them into Cartons

$$\begin{aligned} {\textbf {SC}}(V_R, D, factor): \quad \text {Maximize} \quad&\sum _{p\in D} V_{I_p}x_p&\end{aligned}$$

(2)

$$\begin{aligned} \text {Subject to} \quad&\sum _{p\in D} V_{I_p}x_p \le factor \times V_R \end{aligned}$$

(3)

$$\begin{aligned}&x_p \in \{0,1\}, \forall p\in D \end{aligned}$$

(4)

Next, the stochastic beam-search-based method is used again to load cartons selected by Algorithm 6 into the residual spaces in R. If all the cartons can be loaded into the residual spaces in R, the current best solution to the single container mix-loading problem (tempSol) is generated, and we increase lb of the binary search in the expectation of finding a better solution; otherwise, we decrease ub of the binary search to increase the chance that the newly depalletized cartons can be totally loaded into the residual spaces in R.

5 Computational experiments

Our two-phase constructive algorithm was implemented as a sequential algorithm in Java (JDK 7 updated 21, 64-bit edition), and no multi-threading was explicitly used. All experiments described in this section were conducted on a computer with an Intel® Xeon(R) Gold 6146 CPU clocked at 3.20 gigahertz with 16 gigabytes of RAM, running a Windows Server 2016 (64-bit) operating system. The commercial integer linear programming solver used was the IBM ILog CPLEX Optimization Studio 12.2 (64-bit) with its default settings.

Since there is no standard benchmark data for the single container mix-loading problem, we generated 70 SCMLP instances based on historical data provided by the audio equipment manufacturer to test the effectiveness of our approach. The details are presented in Sect. 5.1. The stochastic beam-search-based method described in Sect. 4.1 can solve the single container loading problem. Therefore, we test stochastic beam-search-based method on well-known SCLP benchmark instances and report its performance in Sect. 5.2. We demonstrate the performance of the two-phase constructive algorithm for all SCMLP instances in Sect. 5.3.

5.1 Test instances generation

We collected 12-month purchase order data from the audio equipment manufacturer in Hong Kong. Most orders consist of N types of PSUs, with N coming from the set $\{1,2,3,4,5,6, 7, 8, 9, 11\}$. Each PSU contains identical products packaged in cartons. Information about each PSU is provided, including the dimensions of the PSU, the dimensions of the cartons in the PSU, and the number of cartons in the PSU. The 40-foot standard container, with dimensions of 12045 mm by 2309 mm by 2379 mm, is used for each order.

We generated 70 SCMLP instances. Each instance is generated as follows. We first set a target value V for the total volume of PSUs in the instance. The target volume is randomly generated so that it is larger than the volume of the 40-foot standard container. We then uniformly randomly select N types of PSUs from the orders provided by the manufacturer and initialize their quantities to 1. Next, we uniformly randomly select one type from the N types of PSUs and increase its quantity by 1. We repeatedly increase the quantity of each type of PSU until the total volume of all PSUs in the instance exceeds the target volume V. The manufacturer did not provide information regarding which PSUs are depalletizable; therefore, we randomly set some PSU types in the instance to be depalletizable. Furthermore, we suppose that each PSU in the instance can only be rotated along its height, but that any carton contained in the PSU is fully rotatable.

5.2 Analysis of the stochastic beam-search based method

The stochastic beam-search-based method (SBSM) (Algorithm 1) can be used to solve the Single Container Loading Problem (SCLP) with the full-support constraint. The input of the stochastic beam-search-based method is the set of items and the container given by the SCLP. Several algorithms are designed to solve the SCLP with the full-support constraint in the literature. We compare our approach with the following state-of-the-art ones. The computational environments of each approach are shown in Table 1.

• BSG-CLP: a beam-search-based approach developed by Araya and Riff (2014).

• CLA-SS(W): a container loading algorithm with static stability developed by Ramos et al. (2016).

• BSG-VCS: a beam-search-based approach using a new heuristic function for selecting boxes developed by Araya et al. (2017).

Table 1 Computational environments

These authors tested their algorithms on the well-known benchmark data sets BR1–BR15. BR1–BR7 were generated by Bischoff and Ratcliff (1995). BR8–BR15 were proposed by Davies and Bischoff (1999). There are 100 instances in each of the 15 sets. These data sets can be divided into two groups based on the heterogeneity of items: each instance in BR1–BR7 consists of weakly heterogeneous items, and each instance in BR8–BR15 consists of strongly heterogeneous items.

We ran our method on BR1–BR15 and compared its performance with the abovementioned methods. The time limit is set to 150 s. The comparison is summarized in Table 2, where SBSM is our stochastic beam-search-based method. To test the effect of our stochastic strategy, we implemented another version of our approach by removing the stochastic strategy. In other words, similar to BSG-CLP and BSG-VCS, we select the most promising w nodes at each level of the tree search process. The modified approach is denoted as BSM. The first column presents the name of the test data set. Columns 150 s and 30 s represent the volume utilization obtained by the corresponding algorithm averaged over 100 instances of the corresponding data set by 150 and 30 s, respectively. The last three rows report the average volume utilization of instances over different sets.

Table 2 Comparison between SBSM and the best existing algorithms for the SCLP with the full-support constraint

Table 2 shows that our stochastic beam-search-based method outperforms the existing algorithms for the single container loading instances with heterogeneous items. Besides, the results of SBSM are slightly better than those of BSM. Since these instances are well studied in the literature, the improvement of SBSM compared to BSM demonstrates the effect of our stochastic strategy, although the improvement is slight. Besides, the SBSM can get different solutions than BSM by setting different random seeds, which can diversify the search space without losing solution quality.

5.3 Computational results

We set the stochastic beam search’s time limit to 500 s and performed the two-phase constructive algorithm on the 70 SCMLP instances. Table 3 summarizes the final results. Each row in the table reports the instance, the number of PSU types involved in the instance, the volume utilization of the solution found in the first phase of the algorithm ($Util_1$), the volume utilization of the final solution found by the algorithm ($Util_2$), and the number of PSUs that are depalletized in the final solution. The last row is the average result of 70 instances. Note that only complete PSUs are loaded into the container in the solution found in the first phase of the constructive algorithm. Table 3 shows that the volume utilization is increased by approximately $3\%$ by packing cartons into the container.

Table 3 Results of performing the two-phase constructive algorithm on the 70 test instances

6 Conclusion

We investigated the Single Container Mix-Loading Problem, inspired by the requirements of an international audio equipment manufacturer in Hong Kong. The manufacturer stores its products in Palletized Storage Units (PSUs). When delivering products, loading PSUs, rather than individual products, into containers (or trucks) is convenient; however, large spaces in each container could be wasted. To improve the utilization of a container, the manufacturer is willing to depalletize PSUs and load the individual products, together with other PSUs, into a container. Once a PSU is depalletized, all of its products must be loaded into the container, and no PSU can be depalletized if the total volume of complete PSUs loaded in the container is not maximized.

We developed a two-phase constructive algorithm for the SCMLP. The algorithm uses a stochastic beam-search-based method as its sub-routine, which iteratively calls upon a beam search. In the first phase of our constructive algorithm, the stochastic beam-search-based method is called upon to load complete PSUs into the container. In the second phase, a proper set of PSUs is selected considering the remaining volume of the container, and the stochastic beam-search-based method is used to load all products depalletized from the selected PSUs into the remaining spaces of the container.

We generated 70 test instances based on historical data provided by the audio equipment manufacturer, and we reported the solutions to the test instances found by the two-phase constructive algorithm for further reference.