# A Flexible Reinforced Bin Packing Framework with Automatic Slack Selection

Authors: Ting Yang; Fei Luo; Joel Fuentes; Weichao Ding; Chunhua Gu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The slack-based algorithms are popular bin-focus heuristics for the bin packing problem (BPP). The selection of slacks in existing methods only consider predetermined policies, ignoring the dynamic exploration of the global data structure, which leads to nonfully utilization of the information in the data space. In this paper, we propose a novel slack-based flexible bin packing framework called reinforced bin packing framework (RBF) for the one-dimensional BPP. RBF considers the RL-system, the instance-eigenvalue mapping process, and the reinforced-MBS strategy simultaneously. In our work, the slack is generated with a reinforcement learning strategy, in which the performance-driven rewards are used to capture the intuition of learning the current state of the container space, the action is the choice of the packing container, and the state is the remaining capacity after packing. During the construction of the slack, an instance-eigenvalue mapping process is designed and utilized to generate the representative and classified validate set. Furthermore, the provision of the slack coefficient is integrated into MBS-based packing process. Experimental results show that, in comparison with fit algorithms, MBS and MBS’, RBF achieves state-of-the-art performance on BINDATA and SCH_WAE datasets. In particular, it outperforms its baseline MBS and MBS’, averaging the number increase of optimal solutions of 189.05% and 27.41%, respectively.


---

## Body

## 1. Introduction

As a classical discrete combinatorial optimization problems [1, 2], the bin packing problem (BPP) [3, 4] aims to minimize the number of used bins to pack items and it is NP-hard [5, 6]. In the past few decades, four main approaches have been extensively studied to resolve the BPP, such as exact approaches [7–9], approximation algorithms [4, 10], heuristic algorithms, and metaheuristic algorithms [11, 12]. The exact algorithms typically prune the lower bound information to address the BPP, which is suitable for small-scale instances. When the scale of datasets increases, the BPP becomes challenging to the approximation algorithms. The implementation of the metaheuristic algorithms is difficult due to the rigorous requirements on parameter adjustment and calculation complexity [13]. In the contrast, the heuristic algorithm is a popular bin packing method due to its efficiency on solving NP-hard problems.As one of typical heuristic algorithms, the minimum bin slack (MBS) is particular useful to problems where an optimal solution requires most of the bins, if not all, to be exactly filled [14]. It is also useful for solving the problems where the sum of requirements of items is less than or equal to twice the bin capacity. In MBS, the selection of the packing sequence of the items is based on a predetermined strategy, which ignores the sampling deviation between the data of the items to be packed and cannot explore the global data space.Therefore, the MBS algorithm may quickly fall into local optimal solutions ignoring the exploration of global item space in the training process. In the stage of iterative training, the deviation of the locally optimal solution is accumulated continuously, and the global optimal solution space is shifted steadily. It may result in a significant difference between the algorithm’s packing result and the optimal solution, which may lead to the failure to achieve the desired performance [14].In order to solve the problems of MBS described above, we propose a reinforced bin packing framework, dubbed RBF, to resolve the BPP, where a reinforcement learning (RL) method, i.e., the Q-learning algorithm, is exploited to select a high-quality slack for the packing process. The RBF treats Q-learning as a prior data spatial information detector. To ingeniously select data samples as representatives of the datasets, it explores an intrinsic spatial distribution of sample bins by interacting with the environment and estimating the optimal slack of the global bins. The learned slacks are finally exploited in the improved MBS algorithm to pack items.The proposed RBF can be distinguished from previous work in terms of the following characteristics:(1)
The reinforced learning algorithm is exploited to generate the slack automatically, which is further integrated to the MBS algorithm. With high-quality slacks, automatically, rather than manual design or empirical speculation, our method prevents the bin packing process from falling into a local optimal solution, which is a quite challenging problem especially for the large-scale dataset.(2)
The instance-eigenvalue mapping function is introduced to efficiently select representative and classified validate set of the input instances based on their similarity. This enables RBF to reduce the learning cost while generating a dynamic slack during the packing process.The rest of this paper is organized as follows. Related work is presented in Section2. The formulation of the BPP is depicted in Section 3. In Section 4, we briefly overview the design of the RBF and then detail its key components, such as the RL-system, the reinforced-MBS strategy, and the instance mapping process. Experimental results and theoretical analyses are presented in Section 5. Finally, conclusions are drawn in Section 6.


## 2. Related Work

Existing methods that address the BPP can be roughly classified into four major categories: the exact approaches [15–20], the approximation algorithms [4, 21, 22], the heuristic algorithms [14, 23–27], and the metaheuristic algorithms [11–13, 28–30]. In recent years, the RL-based methods [31–35] have also been proposed to resolve the BPP.


### 2.1. Exact Approaches

The exact approaches establish mathematical model and obtain the optimal solution of the problem by solving the mathematical model through optimization algorithms. CPLEX [36] solved the problem with mixed integer programming. Polyakovskiy and M’Hallah [15] characterized the properties of the two-dimensional nonoriented BPP with due dates, which packed a set of rectangular items, and experimentally proved that a tight lower bound enhanced an existing bound on maximum lateness for 24.07% of the benchmark instances. Since the quality of the solution depends on whether the model is reasonable or not, they are only applicable to small-scale instances.Subsequent improvements focused on reconsideration about constraints in a novelty manner. Chitsaz et al. [18] proposed an algorithm to separate the subcontour elimination constraints of fractional solutions to solve production, inventory, and inbound transportation decision problems. The inequalities and separation procedures were used in a branch-and-cut algorithm. A similar idea was proposed in Mara’s work [20], where an exact algorithm was proposed based on the classic ϵ-constraint method. The method addressed N single-objective problems by using reduction with test sets instead of an optimizer. Besides, one classic method belonging to this group was the arc-flow formulation method [9] which represented all the patterns in a very compact graph based on an arc-flow formulation with side constraints and can be solved exactly by general-purpose mixed integer programming solvers. Generally, when the scale of the problem becomes larger, the phenomenon of “combinatorial explosion” will lead to heavy computational overhead in the optimization process. It is difficult for the exact algorithm to be applied to large-scale combinatorial optimization problems.


### 2.2. Approximation Algorithms

Approximation algorithms are popular because their time complexity is polynomial, while they do not guarantee to find the optimal solution. Typical approximation algorithms include greedy algorithms and local search. Based on the observation and arrangement of Earth observation satellites, the authors in [21] proposed an index-based multiobjective local search to solve multiobjective optimization problems. Kang and Park [37] considered the problem of variable-size bin packaging and described two greedy algorithms. The objective was to minimize the total cost of used bins when the unit size cost per bin did not increase as the bin size increased. Moreover, the survey [38] presented an overview of approximation algorithms for the classical BPP and pointed out that although the approximation algorithms are universal, there is always a gap between the solution and the optimal solution under the polynomial time complexity. However, approximation algorithms are commonly subjective to polynomial time and cannot give guarantees of solutions.


### 2.3. Heuristic Algorithms

Heuristic algorithms are based on the intuitive and empirical design. Several new heuristics for solving the one-dimensional bin packing problem are presented [39]. Coffman and Garey [10] reviewed various heuristic algorithms, such as NF (Next Fit), FF (First Fit), BF (Best Fit), and WF (Worst Fit) [23]. These are typical online packing algorithms [40, 41] and are called as fit algorithms. Their corresponding offline packing algorithms are NFD [24], FFD, BFD, and WFD [23], which differ significantly from online packing algorithms in which offline algorithms rely on overall information for sorting. The fit algorithms, for example, FF, WF, and BF, give priority for further packing to the bins that have already been packed with items, and a new bin will be activated only when there are no suitable nonempty bins for the current item. The strategy adopted by the fit algorithms ensures that each arriving item can always find a bin to be accommodated. However, it cannot guarantee that the item is the target item for optimum solution under the current situation. To address the issue, Cupta and Ho [14] proposed MBS, which mainly centered on bins and tried its best to find the collection of items that fill the bins. One problem with this method is that its sequence selection strategy often falls in the local region of the input space, which makes it hard for accurate estimation of the slack. Thus, it may result in a locally optimal solution. To solve the above problems, some methods have been proposed. Fleszar and Hindi [42] found that one effective hybrid method integrated perturbation MBS’ and a good set of lower bounds into variable neighbourhood search (VNS), so as to improve its ability in reasonably short processing times. However, due to the complexity and uncertainty of combinatorial optimization problems, heuristic algorithms that rely on empirical criteria are not always reliable.


### 2.4. Metaheuristic Algorithms

Metaheuristic algorithms are widely used to find optimal solutions for solving problem of BPP. Early typical representatives include genetic algorithms [28] and simulated annealing algorithms [29]. The former is a promising tool for the BPP and one significant improvement is mainly used: grouping genetic algorithms (GGAs). Dokeroglu and Cosar [43] proposed a set of robust and scalable hybrid parallel algorithms. In GGA-CGT (grouping genetic algorithm with controlled gene transmission) [44], the transmission of the best genes in the chromosomes was promoted while keeping the balance between selection pressure and population diversity. Kucukyilmaz and Kiziloz proposed island-parallel GGA (IPGGA) in [45]. It realized the choice of communication topology, determined the migration and assimilation strategies, adjusted the migration rate, and exploited diversification technologies. Crainic et al. [46] proposed a two-level tabu search for the three-dimensional BPP by reducing the size of the solution space. Kumar and Raza [47] incorporated the concept of Paretos optimality for the BPP with multiple constraints and then proposed a family of solutions along the trade-off surface. However, due to the lack of particle diversity in the later stage of genetic algorithms as well as PSO algorithms, premature convergence always occurs [28].


### 2.5. RL-Based Methods

Machine learning has been extensively studied to resolve the NP-hard BPP by scholars in recent years. Ruben Solozabal’s model tackled the BPP with RL. It trained multistacked long short-term memory cells to perform a recurrent neural network agent, which could embed information from the environment. The performance of the model was just comparable to the FF algorithm when introducing neural network overhead. Inspired by Pointer Network [48], a deep learning technology was successfully applied to learn and optimize the placing order of items [32], solved the classic TSP problem [33], and tackled the 3D BPP. These methods utilized RL to ensure the solution would not converge to local optimum, while they attempted to exploit neural networks [49] in the RL to solve the BPP, which increased the computational cost and time complexity. Heuristic algorithms rely on empirical criteria to consider predetermined strategies and ignore the dynamic exploration of the global data space in BPP. RL-based methods can intelligently mine data information from the environmental space through trial and error. Perhaps, it can help the existing heuristic algorithms to fully explore the effective information in the sample space, which inspired our method.


## 2.1. Exact Approaches

The exact approaches establish mathematical model and obtain the optimal solution of the problem by solving the mathematical model through optimization algorithms. CPLEX [36] solved the problem with mixed integer programming. Polyakovskiy and M’Hallah [15] characterized the properties of the two-dimensional nonoriented BPP with due dates, which packed a set of rectangular items, and experimentally proved that a tight lower bound enhanced an existing bound on maximum lateness for 24.07% of the benchmark instances. Since the quality of the solution depends on whether the model is reasonable or not, they are only applicable to small-scale instances.Subsequent improvements focused on reconsideration about constraints in a novelty manner. Chitsaz et al. [18] proposed an algorithm to separate the subcontour elimination constraints of fractional solutions to solve production, inventory, and inbound transportation decision problems. The inequalities and separation procedures were used in a branch-and-cut algorithm. A similar idea was proposed in Mara’s work [20], where an exact algorithm was proposed based on the classic ϵ-constraint method. The method addressed N single-objective problems by using reduction with test sets instead of an optimizer. Besides, one classic method belonging to this group was the arc-flow formulation method [9] which represented all the patterns in a very compact graph based on an arc-flow formulation with side constraints and can be solved exactly by general-purpose mixed integer programming solvers. Generally, when the scale of the problem becomes larger, the phenomenon of “combinatorial explosion” will lead to heavy computational overhead in the optimization process. It is difficult for the exact algorithm to be applied to large-scale combinatorial optimization problems.


## 2.2. Approximation Algorithms

Approximation algorithms are popular because their time complexity is polynomial, while they do not guarantee to find the optimal solution. Typical approximation algorithms include greedy algorithms and local search. Based on the observation and arrangement of Earth observation satellites, the authors in [21] proposed an index-based multiobjective local search to solve multiobjective optimization problems. Kang and Park [37] considered the problem of variable-size bin packaging and described two greedy algorithms. The objective was to minimize the total cost of used bins when the unit size cost per bin did not increase as the bin size increased. Moreover, the survey [38] presented an overview of approximation algorithms for the classical BPP and pointed out that although the approximation algorithms are universal, there is always a gap between the solution and the optimal solution under the polynomial time complexity. However, approximation algorithms are commonly subjective to polynomial time and cannot give guarantees of solutions.


## 2.3. Heuristic Algorithms

Heuristic algorithms are based on the intuitive and empirical design. Several new heuristics for solving the one-dimensional bin packing problem are presented [39]. Coffman and Garey [10] reviewed various heuristic algorithms, such as NF (Next Fit), FF (First Fit), BF (Best Fit), and WF (Worst Fit) [23]. These are typical online packing algorithms [40, 41] and are called as fit algorithms. Their corresponding offline packing algorithms are NFD [24], FFD, BFD, and WFD [23], which differ significantly from online packing algorithms in which offline algorithms rely on overall information for sorting. The fit algorithms, for example, FF, WF, and BF, give priority for further packing to the bins that have already been packed with items, and a new bin will be activated only when there are no suitable nonempty bins for the current item. The strategy adopted by the fit algorithms ensures that each arriving item can always find a bin to be accommodated. However, it cannot guarantee that the item is the target item for optimum solution under the current situation. To address the issue, Cupta and Ho [14] proposed MBS, which mainly centered on bins and tried its best to find the collection of items that fill the bins. One problem with this method is that its sequence selection strategy often falls in the local region of the input space, which makes it hard for accurate estimation of the slack. Thus, it may result in a locally optimal solution. To solve the above problems, some methods have been proposed. Fleszar and Hindi [42] found that one effective hybrid method integrated perturbation MBS’ and a good set of lower bounds into variable neighbourhood search (VNS), so as to improve its ability in reasonably short processing times. However, due to the complexity and uncertainty of combinatorial optimization problems, heuristic algorithms that rely on empirical criteria are not always reliable.


## 2.4. Metaheuristic Algorithms

Metaheuristic algorithms are widely used to find optimal solutions for solving problem of BPP. Early typical representatives include genetic algorithms [28] and simulated annealing algorithms [29]. The former is a promising tool for the BPP and one significant improvement is mainly used: grouping genetic algorithms (GGAs). Dokeroglu and Cosar [43] proposed a set of robust and scalable hybrid parallel algorithms. In GGA-CGT (grouping genetic algorithm with controlled gene transmission) [44], the transmission of the best genes in the chromosomes was promoted while keeping the balance between selection pressure and population diversity. Kucukyilmaz and Kiziloz proposed island-parallel GGA (IPGGA) in [45]. It realized the choice of communication topology, determined the migration and assimilation strategies, adjusted the migration rate, and exploited diversification technologies. Crainic et al. [46] proposed a two-level tabu search for the three-dimensional BPP by reducing the size of the solution space. Kumar and Raza [47] incorporated the concept of Paretos optimality for the BPP with multiple constraints and then proposed a family of solutions along the trade-off surface. However, due to the lack of particle diversity in the later stage of genetic algorithms as well as PSO algorithms, premature convergence always occurs [28].


## 2.5. RL-Based Methods

Machine learning has been extensively studied to resolve the NP-hard BPP by scholars in recent years. Ruben Solozabal’s model tackled the BPP with RL. It trained multistacked long short-term memory cells to perform a recurrent neural network agent, which could embed information from the environment. The performance of the model was just comparable to the FF algorithm when introducing neural network overhead. Inspired by Pointer Network [48], a deep learning technology was successfully applied to learn and optimize the placing order of items [32], solved the classic TSP problem [33], and tackled the 3D BPP. These methods utilized RL to ensure the solution would not converge to local optimum, while they attempted to exploit neural networks [49] in the RL to solve the BPP, which increased the computational cost and time complexity. Heuristic algorithms rely on empirical criteria to consider predetermined strategies and ignore the dynamic exploration of the global data space in BPP. RL-based methods can intelligently mine data information from the environmental space through trial and error. Perhaps, it can help the existing heuristic algorithms to fully explore the effective information in the sample space, which inspired our method.


## 3. Formulation of the BPP

The classic one-dimensional BPP is formalized as follows. It is assumed that there aren items to be packed into bins with equal capacity C. The general objective is to find a packing way to arrange all items J1,J2,…,Jn with the minimum number of bins, of which the formal mathematical description can be defined as z:(1)minz=∑i=1nyi.Therein,yi represents the indicator whether the ith bin is used or not. A value of 1 indicates that the bin is used, and a value of 0 indicates that it is not used. Note that once the bin Bi is used, the total load of the items placed in Bi cannot exceed the capacity of C. Thus, we have(2)s.t.∑j=1nwjxij≤Cyi,i=1,…,n,where wj means the load of the jth item and xij is an indicator whether the jth item is packed into the ith bin or not. Especially, xij = 1 if the jth item is placed into the ith container, otherwise xij = 0. Furthermore, an equally fundamental constraint is that each item is just placed into one bin:(3)∑i=1nxij=1j=1,…,n.The detailed explanation of parameters for the formalization is defined in Table1.Table 1
Decision variables.
VariableTypeMeaningBiDiscreteTheith binJjDiscreteThejth itemzDiscreteThe objective function of the number of bins usedCConstantThe capacity of the binwjConstantThe load of thejth itemxijBinaryIndicator whether thejth item is packed into the ith bin or notyiBinaryIndicator whether theith bin is used or not


## 4. Design of RBF

In this section, the design of the proposed RBF framework is presented. First, the overview of the RBF is outlined, and then, the details of its key components, such as the RL-system, the reinforced-MBS strategy, and the instance mapping process, are presented.


### 4.1. Overview

The classical MBS algorithm follows two steps:(1)
Utilize lexicographic search optimization procedure [14], also referred as the L algorithm, to find the item set Jj that should be allocated to the bin Bi(2)
Utilize Step 1 to traverse all items to be packed and the minimum bin slack isC−∑j=1nwj, where wj is the load of the packed jth itemThe steps above means that the slack is utilized to jump out of the optimal local trap randomly in the classical MBS algorithm, while the exact distribution of the sample space is ignored. To resolve the instability of the random slack, a new bin packing framework, RBF, is presented, where the slack is learnable and adjusted according to the samples’ structure.The framework of RBF is illustrated in Figure1, which consists of a RL-system, a reinforced-MBS strategy, and an instance-eigenvalue mapping process, and defined as follows:(1)
RL-system: the RL-system is used to generate a suitable slack by a reinforcement learning strategy, where the best action selection strategy is controlled by Q-agent(2)
Reinforced-MBS strategy: with the provision of the slack coefficient from the RL-system, the reinforced-MBS strategy is exploited to resolve the packing process(3)
Instance-eigenvalue mapping: instead of using the whole dataset directly, the instance-eigenvalue mapping is utilized to generate the representative and classified validate set for the RL-system based on the similarity of the input instancesFigure 1
The framework of the RBF.The main idea of RBF is to utilize the RL-system to learn the slack according to the spatial variation of the sample dataset, and then, the slack can be adapted to the distribution of bins and the remaining items in the data space during the iterative packing process. With the instance-eigenvalue mapping, the representative and classified validate set of the input instances is generated. The validate set is further integrated into the RL-system, where an adaptive slack is generated by theQ-agent. The coefficient of the slack is finally applied in the reinforced-MBS strategy for the packing process.


### 4.2. Instance-Eigenvalue Mapping

To reduce the amount of calculation for the slack, the representative items are selected for theQ-agent, which can learn the data space without traversing all instances. Here, an instance classification method, called as instance-eigenvalue mapping, is proposed and defined as(4)yxi=x^i−xminixmaxi−xmini,where x is an given instance, x^i is the average value of the items in the ith instance in the dataset, xmini and xmaxi, respectively, represent the minimum value and maximum value of the items in the ith instance, and yxi denotes the instances eigenvalue of the ith instance.According to the value of the instance-eigenvalue, the whole instances are reordered. The datasetU can be divided into K different subsets U1,U2,…,Uk. The last instance of each subset is taken to form a validation set. Then, the validation set is utilized to iteratively learn the slack. Therefore, at each time step t in RBF, instead of using the whole instances, Q-agent utilizes the validation set to reduce the repetitive work of the system.


### 4.3. RL-System

The validate set is integrated into the RL-system with aQ-learning algorithm [50], where Q-agent is utilized to learn the appropriate strategy and then improve the MBS strategy by selecting high-quality slack.The process of the RL-system can be described as Markov decision processes (MDP) which is represented as a tupleS,A,P,R,γ. In the decision-making process of MDP, S is the state set, A is an action set, P is the transition probability between states, R is the return value after taking a certain action to reach the next state, and γ is the discount factor. To be adaptive to the packing circumstances, for example, the current distribution of containers and the remaining items, we proposed a slack learning algorithm and the detailed process is shown in Algorithm 1, where the parameters are illustrated in Table 2. By observing the current state St of the environment, Q-agent selects one action At that maximizes the value of reward function Rt according to the state observed. With Q-agent continually interacting with the environment, we explore an suitable data selection strategy of the slack coefficient. The algorithm returns both a reward r and a new state St+1 to Q-agent in each packing iteration, of which the change of states depends on the state transition probability pSt+1|St,At:(5)pSt+1|St,At=pss′a=pSt+1=s′|St=s,At=a.Algorithm 1: Slack learning algorithm combined with RL.
Input: training dataitemList with n items, container list BinList with capacity C, remaining capacity Residual Capacity of the bin, learning rate α, discount factor γ, and the iterative number MAX−EPISODE.(1)
InitializeQ-table;(2)
for episode in range MAX−EPISODEdo(3)
St=0(4)
Initialize container listBinList [1, ȷ, n];(5)
is_terminated=False;(6)
while not is_terminated do(7)
According to stateSt and Q-table, use epsilon greedy strategy to select actions At;(8)
Residual Capacity [1, i, n] =  BinList [1, j, n]−itemList [1, k, n];(9)
Calculate immediate RewardRt+1 and get next State St+1;(10)
getQpredictSt,At from QSt,At;(11)
ifSt+1 is not “terminal” then(12)
QtargetSt,At=Rt+1+γ∗maxaQSt+1,At;(13)
else(14)
QtargetSt,At=Rt+1;(15)
is_terminated=True;(16)
end if(17)
Updateϵ;(18)
BinList [1, j, n] = BinList [1, j, n]−ϵ;(19)
end while(20)
QSt,At:=QSt,At+α∗QtargetSt,At−QpredictSt,At;(21)
St=St+1, At=At+1;(22)
end forOutput:Q-table, ϵ.Table 2
Parameters and corresponding descriptions.
ParameterDescriptionAtAction taken at time steptStState at time steptRtReward at time steptAa set of actionsSa set of statesRInstant rewardPTransition probability between statesGtThe sum of reward at time steptαLearning rateγThe discount factorQπs,aState-action value functionϵSlackSOLNumber of bins used by the concrete algorithmOPTNumber of bins contained in the optimal solution of each bin packing instanceUnrealized SOLNumber of feasible optimal solution instances that the algorithm does not achieveGapDeviation percentage between the solution reached by each algorithm and the optimal solutionCRtCompetition ratioThe agent receives the performance-driven rewardRt, and then, the sum of discount reward at time step t is represented as Gt:(6)Gt=Rt+1+γRt+2+⋯=∑k=0∞γkRt+k+1.Therein,γ∈0,1, and it defines the weight of future reward and discount reward in the sum of reward. The closer γ is to 0, the more incentive is to consider short-term benefits. The closer γ is to 1, the more incentive is to consider long-term benefits.The goal of theQ-agent at each time step t is to select an action At that can maximize future discount rewards Gt by finding an optimal policy π∗. Here, π∗ is the strategy of taking the optimal action At at state St, while π is the strategy of taking action At at state St. Under the policy π, Qπs,a is defined as the expectation of the state-action value function. When the agent takes At at St, Qπs,a is represented as(7)Qπs,a=EπGt|st=s,at=a,where Eπ is the expected function.The maximum state-action functionQ∗s,a over all policies is represented in(8)Q∗s,a=maxπQπs,a.The update rule ofQSt,At value is shown in(9)QSt,At=QSt,At+α∗Rt+1+γ∗maxaQSt+1,At−QSt,At,where α∈0,1 is the learning rate of the RL agent.At each time stept, Q-agent observes the current state St and selects the action At from a discrete set of behaviors A=1,2,…,k, where the value of k is equal to the number of the items to be packed. At the beginning, the action At is randomly initialized, that is to say, the action At corresponding to the random number between 1 and k is selected. Then, the RL-system selects the action At that can maximize the QSt,a value at each time step t:(10)At=maxaQSt,a.The agent uses a greedy learning strategy [51] to choose actions. It selects actions according to the optimal value of Q table with 1−θ probability and randomly selects with θ probability.The state is represented as the remaining space capacity of the bin after each round of packing. At each time stept, the remaining items prefer to be packed into as few bins as possible. When the bin is full, the agent is given a reward Rt. If the bin is overflowing, the agent is punished severely and it is told that state like this is not allowed.The slackϵ is defined as(11)ϵ=a+d/r,Therein,d is a constant, r is the immediate reward achieved by Q-agent, and a represents the initial value in the first iteration process. By returning the reward value Rt, the slack ϵ is adjusted in each packing round accordingly. The slack ϵ can be changed in a range with the change of the reward value Rt. Ultimately, the new round of environment is updated as the subtraction of bin capacity C and slack ϵ.Q-agent captures this intuition through performance-driven rewards Rt. At each time step t, the agent’s reward is defined as t. Therein, countn is the number of bins that are exactly filled, countC−ϵ is the number of bins that are filled in the slack space, α is the weight coefficient of positive reward, Countm is the number of overflowing bins, β is the punishment coefficient of negative reward less than 0, and ι is a constant to regulate the value of the entire reward function Rt.


### 4.4. Reinforced-MBS Algorithm

By introducing the slack learned by the RL agent into the MBS, we propose the Reinforced-MBS algorithm. Therein,slack is defined as(12)slack=minvalue∗ω,where ω is the slack parameter learned by the agent applying RL. It is calculated as ω=C−ϵ/C by minimizing the number of used bins on the validation set. Then, the coefficient of slack is passed into our reinforced-MBS algorithm. In detail, the idea of the reinforced-MBS algorithm is shown in Algorithm 2.Algorithm 2: Reinforced-MBS algorithm.
Input: training dataitemList with n items, container list BinList with capacity C; set S, σ=σ1,σ2,…,σs, for t=1,…,n, s=n(1)
Initializek=1, ω=C−ϵ/C;(2)
generate random Slack∈0,min−value∗ω;(3)
fori=1 to |itemList|do(4)
Use the improvedL dictionary search procedure to find the set of items that should be allocated to the bin of k(5)
ifσ=∅then Pack S=S1,S2,…,Sk into the bins 1,2,…,k;(6)
else(7)
k=k+1(8)
end if(9)
end for(10)
CompetitionRatio=SOL/OPTOutput: bins 1,2,…,k with item set S1,S2,…,Sk, CompetitionRatio.In Algorithm2, the improved L dictionary search procedure is utilized to find the set Sk of items that should be assigned to the bin Bk during the iterative process. The improved L dictionary search procedure is shown in Algorithm 3.Algorithm 3: Improved L dictionary search procedure.
Input:ti for i  = 1,…,s; C; k  = 1, σ=σ1,σ2,…,σj, where tσ1≥tσ2≥⋯≥tσs; α=0; π=π1,π2,…,πj=σ1,σ2,…,σj.(1)
Generate Slack∈0,min−value∗ω.(2)
Step 1:(3)
if 0 ≤ C−Pπ≤Slackthen(4)
ifSk =  π, go to Step 3.(5)
else(6)
Find the arrangement of the number of the last item in the temporary item list in the original item list, that is, to findq makes σq=πj.(7)
ifPπ<Cthen(8)
j=j+1(9)
ifPπ>αthen(10)
α=Pπ, prepare for packing Sk=π(11)
end if(12)
Step 2:(13)
ifq<sthen(14)
πj=σq+1, go to Step 1.(15)
else(16)
ifj=1then(17)
go to Step 3(18)
else(19)
j=j−1. Find q makes σq=πj, go to Step 2.(20)
end if(21)
end if(22)
else(23)
go to Step 2(24)
end if(25)
end if(26)
Step 3: Place the items in Sk into the Kth bin.Output:S=S1,S2,…,Sk.


## 4.1. Overview

The classical MBS algorithm follows two steps:(1)
Utilize lexicographic search optimization procedure [14], also referred as the L algorithm, to find the item set Jj that should be allocated to the bin Bi(2)
Utilize Step 1 to traverse all items to be packed and the minimum bin slack isC−∑j=1nwj, where wj is the load of the packed jth itemThe steps above means that the slack is utilized to jump out of the optimal local trap randomly in the classical MBS algorithm, while the exact distribution of the sample space is ignored. To resolve the instability of the random slack, a new bin packing framework, RBF, is presented, where the slack is learnable and adjusted according to the samples’ structure.The framework of RBF is illustrated in Figure1, which consists of a RL-system, a reinforced-MBS strategy, and an instance-eigenvalue mapping process, and defined as follows:(1)
RL-system: the RL-system is used to generate a suitable slack by a reinforcement learning strategy, where the best action selection strategy is controlled by Q-agent(2)
Reinforced-MBS strategy: with the provision of the slack coefficient from the RL-system, the reinforced-MBS strategy is exploited to resolve the packing process(3)
Instance-eigenvalue mapping: instead of using the whole dataset directly, the instance-eigenvalue mapping is utilized to generate the representative and classified validate set for the RL-system based on the similarity of the input instancesFigure 1
The framework of the RBF.The main idea of RBF is to utilize the RL-system to learn the slack according to the spatial variation of the sample dataset, and then, the slack can be adapted to the distribution of bins and the remaining items in the data space during the iterative packing process. With the instance-eigenvalue mapping, the representative and classified validate set of the input instances is generated. The validate set is further integrated into the RL-system, where an adaptive slack is generated by theQ-agent. The coefficient of the slack is finally applied in the reinforced-MBS strategy for the packing process.


## 4.2. Instance-Eigenvalue Mapping

To reduce the amount of calculation for the slack, the representative items are selected for theQ-agent, which can learn the data space without traversing all instances. Here, an instance classification method, called as instance-eigenvalue mapping, is proposed and defined as(4)yxi=x^i−xminixmaxi−xmini,where x is an given instance, x^i is the average value of the items in the ith instance in the dataset, xmini and xmaxi, respectively, represent the minimum value and maximum value of the items in the ith instance, and yxi denotes the instances eigenvalue of the ith instance.According to the value of the instance-eigenvalue, the whole instances are reordered. The datasetU can be divided into K different subsets U1,U2,…,Uk. The last instance of each subset is taken to form a validation set. Then, the validation set is utilized to iteratively learn the slack. Therefore, at each time step t in RBF, instead of using the whole instances, Q-agent utilizes the validation set to reduce the repetitive work of the system.


## 4.3. RL-System

The validate set is integrated into the RL-system with aQ-learning algorithm [50], where Q-agent is utilized to learn the appropriate strategy and then improve the MBS strategy by selecting high-quality slack.The process of the RL-system can be described as Markov decision processes (MDP) which is represented as a tupleS,A,P,R,γ. In the decision-making process of MDP, S is the state set, A is an action set, P is the transition probability between states, R is the return value after taking a certain action to reach the next state, and γ is the discount factor. To be adaptive to the packing circumstances, for example, the current distribution of containers and the remaining items, we proposed a slack learning algorithm and the detailed process is shown in Algorithm 1, where the parameters are illustrated in Table 2. By observing the current state St of the environment, Q-agent selects one action At that maximizes the value of reward function Rt according to the state observed. With Q-agent continually interacting with the environment, we explore an suitable data selection strategy of the slack coefficient. The algorithm returns both a reward r and a new state St+1 to Q-agent in each packing iteration, of which the change of states depends on the state transition probability pSt+1|St,At:(5)pSt+1|St,At=pss′a=pSt+1=s′|St=s,At=a.Algorithm 1: Slack learning algorithm combined with RL.
Input: training dataitemList with n items, container list BinList with capacity C, remaining capacity Residual Capacity of the bin, learning rate α, discount factor γ, and the iterative number MAX−EPISODE.(1)
InitializeQ-table;(2)
for episode in range MAX−EPISODEdo(3)
St=0(4)
Initialize container listBinList [1, ȷ, n];(5)
is_terminated=False;(6)
while not is_terminated do(7)
According to stateSt and Q-table, use epsilon greedy strategy to select actions At;(8)
Residual Capacity [1, i, n] =  BinList [1, j, n]−itemList [1, k, n];(9)
Calculate immediate RewardRt+1 and get next State St+1;(10)
getQpredictSt,At from QSt,At;(11)
ifSt+1 is not “terminal” then(12)
QtargetSt,At=Rt+1+γ∗maxaQSt+1,At;(13)
else(14)
QtargetSt,At=Rt+1;(15)
is_terminated=True;(16)
end if(17)
Updateϵ;(18)
BinList [1, j, n] = BinList [1, j, n]−ϵ;(19)
end while(20)
QSt,At:=QSt,At+α∗QtargetSt,At−QpredictSt,At;(21)
St=St+1, At=At+1;(22)
end forOutput:Q-table, ϵ.Table 2
Parameters and corresponding descriptions.
ParameterDescriptionAtAction taken at time steptStState at time steptRtReward at time steptAa set of actionsSa set of statesRInstant rewardPTransition probability between statesGtThe sum of reward at time steptαLearning rateγThe discount factorQπs,aState-action value functionϵSlackSOLNumber of bins used by the concrete algorithmOPTNumber of bins contained in the optimal solution of each bin packing instanceUnrealized SOLNumber of feasible optimal solution instances that the algorithm does not achieveGapDeviation percentage between the solution reached by each algorithm and the optimal solutionCRtCompetition ratioThe agent receives the performance-driven rewardRt, and then, the sum of discount reward at time step t is represented as Gt:(6)Gt=Rt+1+γRt+2+⋯=∑k=0∞γkRt+k+1.Therein,γ∈0,1, and it defines the weight of future reward and discount reward in the sum of reward. The closer γ is to 0, the more incentive is to consider short-term benefits. The closer γ is to 1, the more incentive is to consider long-term benefits.The goal of theQ-agent at each time step t is to select an action At that can maximize future discount rewards Gt by finding an optimal policy π∗. Here, π∗ is the strategy of taking the optimal action At at state St, while π is the strategy of taking action At at state St. Under the policy π, Qπs,a is defined as the expectation of the state-action value function. When the agent takes At at St, Qπs,a is represented as(7)Qπs,a=EπGt|st=s,at=a,where Eπ is the expected function.The maximum state-action functionQ∗s,a over all policies is represented in(8)Q∗s,a=maxπQπs,a.The update rule ofQSt,At value is shown in(9)QSt,At=QSt,At+α∗Rt+1+γ∗maxaQSt+1,At−QSt,At,where α∈0,1 is the learning rate of the RL agent.At each time stept, Q-agent observes the current state St and selects the action At from a discrete set of behaviors A=1,2,…,k, where the value of k is equal to the number of the items to be packed. At the beginning, the action At is randomly initialized, that is to say, the action At corresponding to the random number between 1 and k is selected. Then, the RL-system selects the action At that can maximize the QSt,a value at each time step t:(10)At=maxaQSt,a.The agent uses a greedy learning strategy [51] to choose actions. It selects actions according to the optimal value of Q table with 1−θ probability and randomly selects with θ probability.The state is represented as the remaining space capacity of the bin after each round of packing. At each time stept, the remaining items prefer to be packed into as few bins as possible. When the bin is full, the agent is given a reward Rt. If the bin is overflowing, the agent is punished severely and it is told that state like this is not allowed.The slackϵ is defined as(11)ϵ=a+d/r,Therein,d is a constant, r is the immediate reward achieved by Q-agent, and a represents the initial value in the first iteration process. By returning the reward value Rt, the slack ϵ is adjusted in each packing round accordingly. The slack ϵ can be changed in a range with the change of the reward value Rt. Ultimately, the new round of environment is updated as the subtraction of bin capacity C and slack ϵ.Q-agent captures this intuition through performance-driven rewards Rt. At each time step t, the agent’s reward is defined as t. Therein, countn is the number of bins that are exactly filled, countC−ϵ is the number of bins that are filled in the slack space, α is the weight coefficient of positive reward, Countm is the number of overflowing bins, β is the punishment coefficient of negative reward less than 0, and ι is a constant to regulate the value of the entire reward function Rt.


## 4.4. Reinforced-MBS Algorithm

By introducing the slack learned by the RL agent into the MBS, we propose the Reinforced-MBS algorithm. Therein,slack is defined as(12)slack=minvalue∗ω,where ω is the slack parameter learned by the agent applying RL. It is calculated as ω=C−ϵ/C by minimizing the number of used bins on the validation set. Then, the coefficient of slack is passed into our reinforced-MBS algorithm. In detail, the idea of the reinforced-MBS algorithm is shown in Algorithm 2.Algorithm 2: Reinforced-MBS algorithm.
Input: training dataitemList with n items, container list BinList with capacity C; set S, σ=σ1,σ2,…,σs, for t=1,…,n, s=n(1)
Initializek=1, ω=C−ϵ/C;(2)
generate random Slack∈0,min−value∗ω;(3)
fori=1 to |itemList|do(4)
Use the improvedL dictionary search procedure to find the set of items that should be allocated to the bin of k(5)
ifσ=∅then Pack S=S1,S2,…,Sk into the bins 1,2,…,k;(6)
else(7)
k=k+1(8)
end if(9)
end for(10)
CompetitionRatio=SOL/OPTOutput: bins 1,2,…,k with item set S1,S2,…,Sk, CompetitionRatio.In Algorithm2, the improved L dictionary search procedure is utilized to find the set Sk of items that should be assigned to the bin Bk during the iterative process. The improved L dictionary search procedure is shown in Algorithm 3.Algorithm 3: Improved L dictionary search procedure.
Input:ti for i  = 1,…,s; C; k  = 1, σ=σ1,σ2,…,σj, where tσ1≥tσ2≥⋯≥tσs; α=0; π=π1,π2,…,πj=σ1,σ2,…,σj.(1)
Generate Slack∈0,min−value∗ω.(2)
Step 1:(3)
if 0 ≤ C−Pπ≤Slackthen(4)
ifSk =  π, go to Step 3.(5)
else(6)
Find the arrangement of the number of the last item in the temporary item list in the original item list, that is, to findq makes σq=πj.(7)
ifPπ<Cthen(8)
j=j+1(9)
ifPπ>αthen(10)
α=Pπ, prepare for packing Sk=π(11)
end if(12)
Step 2:(13)
ifq<sthen(14)
πj=σq+1, go to Step 1.(15)
else(16)
ifj=1then(17)
go to Step 3(18)
else(19)
j=j−1. Find q makes σq=πj, go to Step 2.(20)
end if(21)
end if(22)
else(23)
go to Step 2(24)
end if(25)
end if(26)
Step 3: Place the items in Sk into the Kth bin.Output:S=S1,S2,…,Sk.


## 5. Experimental Evaluation

In this section, experiments are carried out to verify the effectiveness and robustness of the proposed RBF. First, experimental evaluation indexes are introduced and the datasets used in the experiments are detailed. Afterwards, the experimental results are presented and analyzed. Finally, the robustness and stability of our method is discussed.


### 5.1. Evaluation Indexes and Datasets

#### 5.1.1. Competition Ratio

The competition ratio [52, 53], CRt, is defined as(13)CRt=SOLOPT,where SOL represents the number of bins used by the concrete algorithm and OPT is the number of bins in the optimal solution for the packing instance. The competition ratio equal to 1 means that the algorithm has found the optimal solution.Generally, OPT(σ) has a lower limit, as shown in formula (14), where ⌈⌉ is the ceiling function. Due to the limitation of bin packing conditions, the number of bins used in each bin packing iteration cannot be less than the ratio of the total load of the items to the capacity of a single bin:(14)OPTσ≥∑i=1ktiC.


#### 5.1.2. FSOL

For a dataset, FSOL represents the number of feasible optimal solution instances achieved by the algorithm; in other words, the number of instances whoseCRt is 1. For the specialized algorithm alg and the dataset data, FSOL is specialized as FSOLalgdata.


#### 5.1.3. Realization Rate

Realization rate (RT) is defined as formula (15), where INS is the number of instances in the packing dataset:(15)RT=FSOLINS.


#### 5.1.4. Gap

Gap is referred to the deviation between the number of used bins obtained by the algorithm and the optimal number of the packing. The relative Gap is exploited to evaluate the performance of the algorithms, which is calculated as(16)Gap=SOL−OPTOPT.TheBINDATA [54] and SCH−WAE [55] datasets are used in the experiment for evaluation. Therein, BINDATA dataset includes three subsets, such as Bin1data, Bin2data, and Bin3data. The details of datasets are shown in Table 3, such as the number of instances, weight of items, capacity of bins, and the number of items in the instances.Table 3
Information about the problem instances.
Bin1data720[1, 100]{100, 120, 150}{50, 100, 200, 500}Bin2data480[1, 700]1000{50, 100, 200, 500}Bin3data10[20000, 35000]100000200SCH−WAE200[150, 200]1000{100, 120}


### 5.2. Experimental Results and Analysis

The performance of the RBF is compared with that of the classical Fit algorithms, the MBS algorithm, and the MBS’ algorithm onBINDATA and SCH−WAE datasets shown in Table 3. For each instance of each dataset, the number of items in each category is the same. The experimental results reported in this paper are the average of ten runs under per hyperparameter settings.


#### 5.2.1. Results onBINDATA

Table4 lists the results of FSOL, RT, and CRt of the algorithms involved in comparison on BINDATA, while Table 5 lists the value of Gap. In comparison with the classical heuristic algorithms, such as NFD, FFD, WFD, AWFD, BFD, MBS, and MBS’, RBF obtains the maximum FSOL on BINDATA, while its CRt and Gap are minimum. Furthermore, the improvement of FSOLRBF, represented as IMPRBFalg and defined as formula (17), is further calculated, where alg∈MBS,MBS′ and data∈Bin1data,Bin2data. Especially, for Bin1data and Bin2data, IMPRBFMBS is 165.08% and 179.2%, respectively, while IMPRBFMBS′ is 5.53% and 41.3%, respectively. For the dataset Bin3data, RBF is the only one that can obtain 2 optimal solutions in the total 10 cases, while the others obtain zero optimal solutions:(17)IMPRBFalg=FSOLRBFdata−FSOLalgdataFSOLalgdata.Table 4
Results onBINDATA.
AlgorithmBin1data (n=720)Bin2data (n=480)Bin3data (n=10)FSOLRTCRtFSOLRTCRtFSOLRTCRtNFD [24]00.001.35025912.291.127100.001.1711FFD [23]54675.831.049723649.161.031500.001.0739WFD [25]44261.381.053721344.371.033600.001.0739AWFD [25]16322.631.066310.201.080600.001.0865BFD [23]54775.971.049723649.161.031500.001.0739MBS [14]25235.001.064512526.041.082900.001.0594MBS’ [14]63387.911.047124751.451.026400.001.0721RBF66892.781.046834972.711.0101220.001.0198Table 5
Results ofGap.
AlgorithmBin1dataBin2dataBin3dataSCH-WAENFD [24]35.03%12.71%17.12%6.22%FFD [23]4.98%3.15%7.39%6.15%WFD [25]5.38%3.37%7.39%6.15%AWFD [25]6.64%8.06%8.66%10.69%BFD [23]4.98%3.15%7.39%6.15%MBS [14]6.46%3.08%5.95%5.17%MBS’ [14]4.71%2.98%7.21%5.10%RBF4.68%1.01%1.98%1.39%


#### 5.2.2. Results onSCH−WAE

The results of the compared algorithms onSCH−WAE are listed in Table 6. And, the detail results of RBF on SCH−WAE, that is, SOL, OPT, and the time cost (Runtime) on each instance, are shown in Tables 7 and 8. In the setting of Table 7, the number of items is 100 and the container capacity is 1000. Table 8 shows the statistical results when the number of items is 120. Meanwhile, Gap of each algorithm are shown in the last column of Table 5. It is shown that, in comparison with other algorithms on SCH−WAE, RBF achieved the minimum CRt and Gap, but the maximum was FSOL and RT. Especially, for SCH−WAE, IMPRBFMBS is 472%, while IMPRBFMBS′ is 346.88%.Table 6
Results onSCH−WAEn=200.
AlgorithmFSOLRTCRtNFD [24]10.501.0622FFD [23]10.501.0614WFD [25]10.501.0614AWFD [25]00.001.1069BFD [23]10.501.0614MBS [14]2512.501.0574MBS’ [14]3216.001.0513RBF14371.501.0139Table 7
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=100,C=1000SCH_WAE1_118181.462466SCH_WAE1_218182.727113SCH_WAE1_318183.150908SCH_WAE1_418183.70839SCH_WAE1_518180.539083SCH_WAE1_618180.758503SCH_WAE1_718180.664705SCH_WAE1_818180.679174SCH_WAE1_919184.522568SCH_WAE1_1018184.374016SCH_WAE1_1118180.982381SCH_WAE1_1218181.691106SCH_WAE1_1318184.604945SCH_WAE1_14191810.755302SCH_WAE1_1518181.797069SCH_WAE1_1618181.450974SCH_WAE1_1719181.246981SCH_WAE1_1818180.722101SCH_WAE1_1918180.713857SCH_WAE1_2018180.709936SCH_WAE1_2118180.998908SCH_WAE1_2219183.028952SCH_WAE1_2318180.557798SCH_WAE1_2418180.976983SCH_WAE1_2518181.074089SCH_WAE1_2619180.31875SCH_WAE1_2718183.446602SCH_WAE1_2818186.492802SCH_WAE1_2918184.080608SCH_WAE1_3018181.483333SCH_WAE1_3118180.731631SCH_WAE1_3218181.545062SCH_WAE1_3318181.73632SCH_WAE1_3418180.730045SCH_WAE1_3518181.060398SCH_WAE1_3618180.987255SCH_WAE1_37191813.783422SCH_WAE1_3818180.861974SCH_WAE1_3918183.244424SCH_WAE1_4018182.785588SCH_WAE1_4118181.43709SCH_WAE1_4218181.009547SCH_WAE1_4318181.022882SCH_WAE1_4418180.58083SCH_WAE1_4518184.300251SCH_WAE1_4618181.063874SCH_WAE1_4718187.621793SCH_WAE1_4818180.681381SCH_WAE1_4918180.96076SCH_WAE1_5018180.520412SCH_WAE1_5118180.706839SCH_WAE1_5218181.22345SCH_WAE1_5318181.450091SCH_WAE1_5418180.876361SCH_WAE1_5518180.839967SCH_WAE1_5618180.522451SCH_WAE1_5719189.148892SCH_WAE1_5818181.304132SCH_WAE1_5918180.91717SCH_WAE1_6018180.860201SCH_WAE1_61181811.420425SCH_WAE1_6218180.818042SCH_WAE1_6318181.024627SCH_WAE1_6418180.630548SCH_WAE1_6518181.120638SCH_WAE1_6618187.398161SCH_WAE1_6718181.001821SCH_WAE1_6818180.979633SCH_WAE1_6918180.681692SCH_WAE1_7019183.835019SCH_WAE1_7118184.387344SCH_WAE1_7218181.003916SCH_WAE1_7318183.558745SCH_WAE1_7419185.927648SCH_WAE1_7518180.779189SCH_WAE1_7618181.061736SCH_WAE1_7718181.168255SCH_WAE1_7819180.446685SCH_WAE1_7918181.053857SCH_WAE1_8018181.261393SCH_WAE1_8118183.997979SCH_WAE1_8218180.953343SCH_WAE1_8318180.918264SCH_WAE1_8418180.965771SCH_WAE1_8518180.714233SCH_WAE1_8618180.950277SCH_WAE1_8718181.366335SCH_WAE1_88181812.544721SCH_WAE1_8918180.918441SCH_WAE1_9018181.302644SCH_WAE1_9118182.591703SCH_WAE1_9218181.554301SCH_WAE1_9318181.055307SCH_WAE1_9418181.010704SCH_WAE1_9518181.482197SCH_WAE1_9618181.351396SCH_WAE1_9718181.305057SCH_WAE1_9818180.872971SCH_WAE1_9918183.715139SCH_WAE1_10018181.34348Table 8
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=120,C=1000SCH_WAE2_122227.881069SCH_WAE2_222223.576123SCH_WAE2_322213.484807SCH_WAE2_422212.672799SCH_WAE2_522221.696537SCH_WAE2_622226.829253SCH_WAE2_7222210.166636SCH_WAE2_821214.537143SCH_WAE2_922224.785806SCH_WAE2_1022211.873941SCH_WAE2_1122221.246602SCH_WAE2_1222221.538963SCH_WAE2_1322226.513991SCH_WAE2_1422213.337582SCH_WAE2_15222123.913958SCH_WAE2_1622221.695519SCH_WAE2_1722212.759149SCH_WAE2_1822222.037806SCH_WAE2_1922221.961526SCH_WAE2_2023227.537802SCH_WAE2_2122211.318665SCH_WAE2_2222221.634718SCH_WAE2_2322221.795601SCH_WAE2_2422221.40357SCH_WAE2_25222219.901876SCH_WAE2_26222110.612043SCH_WAE2_2722213.323103SCH_WAE2_2822212.773831SCH_WAE2_2922212.13123SCH_WAE2_3022212.424299SCH_WAE2_3122221.590401SCH_WAE2_3222221.371827SCH_WAE2_3322221.966954SCH_WAE2_3422213.440176SCH_WAE2_3522221.483907SCH_WAE2_3622226.622695SCH_WAE2_3722221.249159SCH_WAE2_3822221.299636SCH_WAE2_39222212.406897SCH_WAE2_4022222.000733SCH_WAE2_4122215.219861SCH_WAE2_42222116.346722SCH_WAE2_4322222.031538SCH_WAE2_4422222.05005SCH_WAE2_4522222.064586SCH_WAE2_4622211.883535SCH_WAE2_4722213.715486SCH_WAE2_4822214.25449SCH_WAE2_4922228.43341SCH_WAE2_5022212.382179SCH_WAE2_5122222.021937SCH_WAE2_5222221.854207SCH_WAE2_5322225.216751SCH_WAE2_54222218.804251SCH_WAE2_5522227.729899SCH_WAE2_5622212.015478SCH_WAE2_5722212.654803SCH_WAE2_5822222.015065SCH_WAE2_59222115.788445SCH_WAE2_60222212.14978SCH_WAE2_6122226.24467SCH_WAE2_6222212.718076SCH_WAE2_63222110.584626SCH_WAE2_6422212.177987SCH_WAE2_6522224.06024SCH_WAE2_6622221.741747SCH_WAE2_6722222.653687SCH_WAE2_6822221.437786SCH_WAE2_6922213.402605SCH_WAE2_7022223.326743SCH_WAE2_7122212.248744SCH_WAE2_72222216.249829SCH_WAE2_7322221.297735SCH_WAE2_74222117.573503SCH_WAE2_7522211.374113SCH_WAE2_7622222.612285SCH_WAE2_7722213.444593SCH_WAE2_7822212.393924SCH_WAE2_7922212.894696SCH_WAE2_80232214.637149SCH_WAE2_81232211.182882SCH_WAE2_8222223.12165SCH_WAE2_8322211.875829SCH_WAE2_84222210.238209SCH_WAE2_8522218.727173SCH_WAE2_8622224.11194SCH_WAE2_8722214.925202SCH_WAE2_8822221.467682SCH_WAE2_8922221.679621SCH_WAE2_9022217.822758SCH_WAE2_9122212.573397SCH_WAE2_9222212.676046SCH_WAE2_9322213.51098SCH_WAE2_9422211.595649SCH_WAE2_9522212.751163SCH_WAE2_9622212.599518SCH_WAE2_9722221.551431SCH_WAE2_9822212.829111SCH_WAE2_9922221.861101SCH_WAE2_10022212.520166


#### 5.2.3. Cumulative Results

For all the instances inBINDATA and SCH−WAE, the cumulative packing results of the compared algorithms, such as the cumulative FSOL, the average RT, the average CRt, and the average Gap, are shown in Table 9. It is shown that RBF obtained 1162 cumulative FSOL and the RT was 82.41%, which greatly overwhelmed other compared algorithms. Especially, according to formula (17), the cumulative improvement of RBF to MBS and MBS’, correspondingly, IMPRBFMBS and IMPRBFMBS′, is 189.05% and 27.41%, respectively. Figure 2 graphically shows the statistical FSOL of the comparison algorithm on each dataset. It is noted that, from the radar in Figure 2, the quantitative curve of RBF for FSOL is at the outermost. It means that RBF achieved the largest number of optimal solutions in the test cases. Also, RBF achieved the minimum CRt and Gap. Results indicate that, in comparison with the typical heuristic algorithms, RBF has a stronger global optimal performance. Overall, the proposed RBF obtains first ranks in all metrics according to the results of all compared algorithms listed in Tables 4–6. In detail, the improvement in FSOL of uncomplicated datasets, Bin1data, is limited among all compared methods. RBF achieves best results and wins with few advantages. However, RBF works much better than other methods on difficult datasets, bin2data, bin3data, and SCH−WAE. Besides, RBF achieves huge advantages in Gap, and it wins almost all other methods on used datasets.Table 9
Average results.
AlgorithmNFD [24]FFD [23]WFD [25]AWFD [25]BFD [23]MBS [14]MBS’ [14]RBFCumulativeFSOL607836561647844029121162Average RT4.26%55.53%46.52%11.63%55.60%28.51%64.68%82.41%AverageCRt1.17761.05411.05561.08501.05411.06601.04921.0226AverageGap17.77%5.42%5.57%8.51%5.42%5.17%5.00%2.27%Figure 2
The number of instances to optimal solution by each algorithm.


### 5.3. Robustness and Stability

The construction of the validation set is a key procedure of RBF. This experiment is carried out to verify the validity of the eigenvalue mapping function on the Bin1data. Since 10 instances of the Bin1data are selected to form the validation set by the eigenvalue mapping function, here different selection policy are applied for comparison in the packing process. The first policy is that the first 10 instances of the Bin1data are selected, the second policy is that the last 10 instances of the Bin1data are selected, and the third policy is that 10 random instances of the Bin1data are selected to form the validation set. The packing results with different selection policies are depicted in Table10. It can be seen that the value of slack learned by Q-agent is different with different selection policies. Especially, with the selection policy of the eigenvalue mapping function, RBF achieved the maximum FSOL and RT, while the minimum was CRt and Gap. The results verified the validity of the eigenvalue mapping function, which helped RBF achieved better performance.Table 10
Statistical results with different composition of validation sets.
Validation setParameterωFSOLRT (%)CRtGap (%)Top 10 cases0.181718926.251.05325.32The last 10 cases0.871023232.221.06205.87Random 10 cases0.453230742.641.04924.93Mapping 10 cases0.581366892.781.04684.68


## 5.1. Evaluation Indexes and Datasets

### 5.1.1. Competition Ratio

The competition ratio [52, 53], CRt, is defined as(13)CRt=SOLOPT,where SOL represents the number of bins used by the concrete algorithm and OPT is the number of bins in the optimal solution for the packing instance. The competition ratio equal to 1 means that the algorithm has found the optimal solution.Generally, OPT(σ) has a lower limit, as shown in formula (14), where ⌈⌉ is the ceiling function. Due to the limitation of bin packing conditions, the number of bins used in each bin packing iteration cannot be less than the ratio of the total load of the items to the capacity of a single bin:(14)OPTσ≥∑i=1ktiC.


### 5.1.2. FSOL

For a dataset, FSOL represents the number of feasible optimal solution instances achieved by the algorithm; in other words, the number of instances whoseCRt is 1. For the specialized algorithm alg and the dataset data, FSOL is specialized as FSOLalgdata.


### 5.1.3. Realization Rate

Realization rate (RT) is defined as formula (15), where INS is the number of instances in the packing dataset:(15)RT=FSOLINS.


### 5.1.4. Gap

Gap is referred to the deviation between the number of used bins obtained by the algorithm and the optimal number of the packing. The relative Gap is exploited to evaluate the performance of the algorithms, which is calculated as(16)Gap=SOL−OPTOPT.TheBINDATA [54] and SCH−WAE [55] datasets are used in the experiment for evaluation. Therein, BINDATA dataset includes three subsets, such as Bin1data, Bin2data, and Bin3data. The details of datasets are shown in Table 3, such as the number of instances, weight of items, capacity of bins, and the number of items in the instances.Table 3
Information about the problem instances.
Bin1data720[1, 100]{100, 120, 150}{50, 100, 200, 500}Bin2data480[1, 700]1000{50, 100, 200, 500}Bin3data10[20000, 35000]100000200SCH−WAE200[150, 200]1000{100, 120}


## 5.1.1. Competition Ratio

The competition ratio [52, 53], CRt, is defined as(13)CRt=SOLOPT,where SOL represents the number of bins used by the concrete algorithm and OPT is the number of bins in the optimal solution for the packing instance. The competition ratio equal to 1 means that the algorithm has found the optimal solution.Generally, OPT(σ) has a lower limit, as shown in formula (14), where ⌈⌉ is the ceiling function. Due to the limitation of bin packing conditions, the number of bins used in each bin packing iteration cannot be less than the ratio of the total load of the items to the capacity of a single bin:(14)OPTσ≥∑i=1ktiC.


## 5.1.2. FSOL

For a dataset, FSOL represents the number of feasible optimal solution instances achieved by the algorithm; in other words, the number of instances whoseCRt is 1. For the specialized algorithm alg and the dataset data, FSOL is specialized as FSOLalgdata.


## 5.1.3. Realization Rate

Realization rate (RT) is defined as formula (15), where INS is the number of instances in the packing dataset:(15)RT=FSOLINS.


## 5.1.4. Gap

Gap is referred to the deviation between the number of used bins obtained by the algorithm and the optimal number of the packing. The relative Gap is exploited to evaluate the performance of the algorithms, which is calculated as(16)Gap=SOL−OPTOPT.TheBINDATA [54] and SCH−WAE [55] datasets are used in the experiment for evaluation. Therein, BINDATA dataset includes three subsets, such as Bin1data, Bin2data, and Bin3data. The details of datasets are shown in Table 3, such as the number of instances, weight of items, capacity of bins, and the number of items in the instances.Table 3
Information about the problem instances.
Bin1data720[1, 100]{100, 120, 150}{50, 100, 200, 500}Bin2data480[1, 700]1000{50, 100, 200, 500}Bin3data10[20000, 35000]100000200SCH−WAE200[150, 200]1000{100, 120}


## 5.2. Experimental Results and Analysis

The performance of the RBF is compared with that of the classical Fit algorithms, the MBS algorithm, and the MBS’ algorithm onBINDATA and SCH−WAE datasets shown in Table 3. For each instance of each dataset, the number of items in each category is the same. The experimental results reported in this paper are the average of ten runs under per hyperparameter settings.


### 5.2.1. Results onBINDATA

Table4 lists the results of FSOL, RT, and CRt of the algorithms involved in comparison on BINDATA, while Table 5 lists the value of Gap. In comparison with the classical heuristic algorithms, such as NFD, FFD, WFD, AWFD, BFD, MBS, and MBS’, RBF obtains the maximum FSOL on BINDATA, while its CRt and Gap are minimum. Furthermore, the improvement of FSOLRBF, represented as IMPRBFalg and defined as formula (17), is further calculated, where alg∈MBS,MBS′ and data∈Bin1data,Bin2data. Especially, for Bin1data and Bin2data, IMPRBFMBS is 165.08% and 179.2%, respectively, while IMPRBFMBS′ is 5.53% and 41.3%, respectively. For the dataset Bin3data, RBF is the only one that can obtain 2 optimal solutions in the total 10 cases, while the others obtain zero optimal solutions:(17)IMPRBFalg=FSOLRBFdata−FSOLalgdataFSOLalgdata.Table 4
Results onBINDATA.
AlgorithmBin1data (n=720)Bin2data (n=480)Bin3data (n=10)FSOLRTCRtFSOLRTCRtFSOLRTCRtNFD [24]00.001.35025912.291.127100.001.1711FFD [23]54675.831.049723649.161.031500.001.0739WFD [25]44261.381.053721344.371.033600.001.0739AWFD [25]16322.631.066310.201.080600.001.0865BFD [23]54775.971.049723649.161.031500.001.0739MBS [14]25235.001.064512526.041.082900.001.0594MBS’ [14]63387.911.047124751.451.026400.001.0721RBF66892.781.046834972.711.0101220.001.0198Table 5
Results ofGap.
AlgorithmBin1dataBin2dataBin3dataSCH-WAENFD [24]35.03%12.71%17.12%6.22%FFD [23]4.98%3.15%7.39%6.15%WFD [25]5.38%3.37%7.39%6.15%AWFD [25]6.64%8.06%8.66%10.69%BFD [23]4.98%3.15%7.39%6.15%MBS [14]6.46%3.08%5.95%5.17%MBS’ [14]4.71%2.98%7.21%5.10%RBF4.68%1.01%1.98%1.39%


### 5.2.2. Results onSCH−WAE

The results of the compared algorithms onSCH−WAE are listed in Table 6. And, the detail results of RBF on SCH−WAE, that is, SOL, OPT, and the time cost (Runtime) on each instance, are shown in Tables 7 and 8. In the setting of Table 7, the number of items is 100 and the container capacity is 1000. Table 8 shows the statistical results when the number of items is 120. Meanwhile, Gap of each algorithm are shown in the last column of Table 5. It is shown that, in comparison with other algorithms on SCH−WAE, RBF achieved the minimum CRt and Gap, but the maximum was FSOL and RT. Especially, for SCH−WAE, IMPRBFMBS is 472%, while IMPRBFMBS′ is 346.88%.Table 6
Results onSCH−WAEn=200.
AlgorithmFSOLRTCRtNFD [24]10.501.0622FFD [23]10.501.0614WFD [25]10.501.0614AWFD [25]00.001.1069BFD [23]10.501.0614MBS [14]2512.501.0574MBS’ [14]3216.001.0513RBF14371.501.0139Table 7
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=100,C=1000SCH_WAE1_118181.462466SCH_WAE1_218182.727113SCH_WAE1_318183.150908SCH_WAE1_418183.70839SCH_WAE1_518180.539083SCH_WAE1_618180.758503SCH_WAE1_718180.664705SCH_WAE1_818180.679174SCH_WAE1_919184.522568SCH_WAE1_1018184.374016SCH_WAE1_1118180.982381SCH_WAE1_1218181.691106SCH_WAE1_1318184.604945SCH_WAE1_14191810.755302SCH_WAE1_1518181.797069SCH_WAE1_1618181.450974SCH_WAE1_1719181.246981SCH_WAE1_1818180.722101SCH_WAE1_1918180.713857SCH_WAE1_2018180.709936SCH_WAE1_2118180.998908SCH_WAE1_2219183.028952SCH_WAE1_2318180.557798SCH_WAE1_2418180.976983SCH_WAE1_2518181.074089SCH_WAE1_2619180.31875SCH_WAE1_2718183.446602SCH_WAE1_2818186.492802SCH_WAE1_2918184.080608SCH_WAE1_3018181.483333SCH_WAE1_3118180.731631SCH_WAE1_3218181.545062SCH_WAE1_3318181.73632SCH_WAE1_3418180.730045SCH_WAE1_3518181.060398SCH_WAE1_3618180.987255SCH_WAE1_37191813.783422SCH_WAE1_3818180.861974SCH_WAE1_3918183.244424SCH_WAE1_4018182.785588SCH_WAE1_4118181.43709SCH_WAE1_4218181.009547SCH_WAE1_4318181.022882SCH_WAE1_4418180.58083SCH_WAE1_4518184.300251SCH_WAE1_4618181.063874SCH_WAE1_4718187.621793SCH_WAE1_4818180.681381SCH_WAE1_4918180.96076SCH_WAE1_5018180.520412SCH_WAE1_5118180.706839SCH_WAE1_5218181.22345SCH_WAE1_5318181.450091SCH_WAE1_5418180.876361SCH_WAE1_5518180.839967SCH_WAE1_5618180.522451SCH_WAE1_5719189.148892SCH_WAE1_5818181.304132SCH_WAE1_5918180.91717SCH_WAE1_6018180.860201SCH_WAE1_61181811.420425SCH_WAE1_6218180.818042SCH_WAE1_6318181.024627SCH_WAE1_6418180.630548SCH_WAE1_6518181.120638SCH_WAE1_6618187.398161SCH_WAE1_6718181.001821SCH_WAE1_6818180.979633SCH_WAE1_6918180.681692SCH_WAE1_7019183.835019SCH_WAE1_7118184.387344SCH_WAE1_7218181.003916SCH_WAE1_7318183.558745SCH_WAE1_7419185.927648SCH_WAE1_7518180.779189SCH_WAE1_7618181.061736SCH_WAE1_7718181.168255SCH_WAE1_7819180.446685SCH_WAE1_7918181.053857SCH_WAE1_8018181.261393SCH_WAE1_8118183.997979SCH_WAE1_8218180.953343SCH_WAE1_8318180.918264SCH_WAE1_8418180.965771SCH_WAE1_8518180.714233SCH_WAE1_8618180.950277SCH_WAE1_8718181.366335SCH_WAE1_88181812.544721SCH_WAE1_8918180.918441SCH_WAE1_9018181.302644SCH_WAE1_9118182.591703SCH_WAE1_9218181.554301SCH_WAE1_9318181.055307SCH_WAE1_9418181.010704SCH_WAE1_9518181.482197SCH_WAE1_9618181.351396SCH_WAE1_9718181.305057SCH_WAE1_9818180.872971SCH_WAE1_9918183.715139SCH_WAE1_10018181.34348Table 8
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=120,C=1000SCH_WAE2_122227.881069SCH_WAE2_222223.576123SCH_WAE2_322213.484807SCH_WAE2_422212.672799SCH_WAE2_522221.696537SCH_WAE2_622226.829253SCH_WAE2_7222210.166636SCH_WAE2_821214.537143SCH_WAE2_922224.785806SCH_WAE2_1022211.873941SCH_WAE2_1122221.246602SCH_WAE2_1222221.538963SCH_WAE2_1322226.513991SCH_WAE2_1422213.337582SCH_WAE2_15222123.913958SCH_WAE2_1622221.695519SCH_WAE2_1722212.759149SCH_WAE2_1822222.037806SCH_WAE2_1922221.961526SCH_WAE2_2023227.537802SCH_WAE2_2122211.318665SCH_WAE2_2222221.634718SCH_WAE2_2322221.795601SCH_WAE2_2422221.40357SCH_WAE2_25222219.901876SCH_WAE2_26222110.612043SCH_WAE2_2722213.323103SCH_WAE2_2822212.773831SCH_WAE2_2922212.13123SCH_WAE2_3022212.424299SCH_WAE2_3122221.590401SCH_WAE2_3222221.371827SCH_WAE2_3322221.966954SCH_WAE2_3422213.440176SCH_WAE2_3522221.483907SCH_WAE2_3622226.622695SCH_WAE2_3722221.249159SCH_WAE2_3822221.299636SCH_WAE2_39222212.406897SCH_WAE2_4022222.000733SCH_WAE2_4122215.219861SCH_WAE2_42222116.346722SCH_WAE2_4322222.031538SCH_WAE2_4422222.05005SCH_WAE2_4522222.064586SCH_WAE2_4622211.883535SCH_WAE2_4722213.715486SCH_WAE2_4822214.25449SCH_WAE2_4922228.43341SCH_WAE2_5022212.382179SCH_WAE2_5122222.021937SCH_WAE2_5222221.854207SCH_WAE2_5322225.216751SCH_WAE2_54222218.804251SCH_WAE2_5522227.729899SCH_WAE2_5622212.015478SCH_WAE2_5722212.654803SCH_WAE2_5822222.015065SCH_WAE2_59222115.788445SCH_WAE2_60222212.14978SCH_WAE2_6122226.24467SCH_WAE2_6222212.718076SCH_WAE2_63222110.584626SCH_WAE2_6422212.177987SCH_WAE2_6522224.06024SCH_WAE2_6622221.741747SCH_WAE2_6722222.653687SCH_WAE2_6822221.437786SCH_WAE2_6922213.402605SCH_WAE2_7022223.326743SCH_WAE2_7122212.248744SCH_WAE2_72222216.249829SCH_WAE2_7322221.297735SCH_WAE2_74222117.573503SCH_WAE2_7522211.374113SCH_WAE2_7622222.612285SCH_WAE2_7722213.444593SCH_WAE2_7822212.393924SCH_WAE2_7922212.894696SCH_WAE2_80232214.637149SCH_WAE2_81232211.182882SCH_WAE2_8222223.12165SCH_WAE2_8322211.875829SCH_WAE2_84222210.238209SCH_WAE2_8522218.727173SCH_WAE2_8622224.11194SCH_WAE2_8722214.925202SCH_WAE2_8822221.467682SCH_WAE2_8922221.679621SCH_WAE2_9022217.822758SCH_WAE2_9122212.573397SCH_WAE2_9222212.676046SCH_WAE2_9322213.51098SCH_WAE2_9422211.595649SCH_WAE2_9522212.751163SCH_WAE2_9622212.599518SCH_WAE2_9722221.551431SCH_WAE2_9822212.829111SCH_WAE2_9922221.861101SCH_WAE2_10022212.520166


### 5.2.3. Cumulative Results

For all the instances inBINDATA and SCH−WAE, the cumulative packing results of the compared algorithms, such as the cumulative FSOL, the average RT, the average CRt, and the average Gap, are shown in Table 9. It is shown that RBF obtained 1162 cumulative FSOL and the RT was 82.41%, which greatly overwhelmed other compared algorithms. Especially, according to formula (17), the cumulative improvement of RBF to MBS and MBS’, correspondingly, IMPRBFMBS and IMPRBFMBS′, is 189.05% and 27.41%, respectively. Figure 2 graphically shows the statistical FSOL of the comparison algorithm on each dataset. It is noted that, from the radar in Figure 2, the quantitative curve of RBF for FSOL is at the outermost. It means that RBF achieved the largest number of optimal solutions in the test cases. Also, RBF achieved the minimum CRt and Gap. Results indicate that, in comparison with the typical heuristic algorithms, RBF has a stronger global optimal performance. Overall, the proposed RBF obtains first ranks in all metrics according to the results of all compared algorithms listed in Tables 4–6. In detail, the improvement in FSOL of uncomplicated datasets, Bin1data, is limited among all compared methods. RBF achieves best results and wins with few advantages. However, RBF works much better than other methods on difficult datasets, bin2data, bin3data, and SCH−WAE. Besides, RBF achieves huge advantages in Gap, and it wins almost all other methods on used datasets.Table 9
Average results.
AlgorithmNFD [24]FFD [23]WFD [25]AWFD [25]BFD [23]MBS [14]MBS’ [14]RBFCumulativeFSOL607836561647844029121162Average RT4.26%55.53%46.52%11.63%55.60%28.51%64.68%82.41%AverageCRt1.17761.05411.05561.08501.05411.06601.04921.0226AverageGap17.77%5.42%5.57%8.51%5.42%5.17%5.00%2.27%Figure 2
The number of instances to optimal solution by each algorithm.


## 5.2.1. Results onBINDATA

Table4 lists the results of FSOL, RT, and CRt of the algorithms involved in comparison on BINDATA, while Table 5 lists the value of Gap. In comparison with the classical heuristic algorithms, such as NFD, FFD, WFD, AWFD, BFD, MBS, and MBS’, RBF obtains the maximum FSOL on BINDATA, while its CRt and Gap are minimum. Furthermore, the improvement of FSOLRBF, represented as IMPRBFalg and defined as formula (17), is further calculated, where alg∈MBS,MBS′ and data∈Bin1data,Bin2data. Especially, for Bin1data and Bin2data, IMPRBFMBS is 165.08% and 179.2%, respectively, while IMPRBFMBS′ is 5.53% and 41.3%, respectively. For the dataset Bin3data, RBF is the only one that can obtain 2 optimal solutions in the total 10 cases, while the others obtain zero optimal solutions:(17)IMPRBFalg=FSOLRBFdata−FSOLalgdataFSOLalgdata.Table 4
Results onBINDATA.
AlgorithmBin1data (n=720)Bin2data (n=480)Bin3data (n=10)FSOLRTCRtFSOLRTCRtFSOLRTCRtNFD [24]00.001.35025912.291.127100.001.1711FFD [23]54675.831.049723649.161.031500.001.0739WFD [25]44261.381.053721344.371.033600.001.0739AWFD [25]16322.631.066310.201.080600.001.0865BFD [23]54775.971.049723649.161.031500.001.0739MBS [14]25235.001.064512526.041.082900.001.0594MBS’ [14]63387.911.047124751.451.026400.001.0721RBF66892.781.046834972.711.0101220.001.0198Table 5
Results ofGap.
AlgorithmBin1dataBin2dataBin3dataSCH-WAENFD [24]35.03%12.71%17.12%6.22%FFD [23]4.98%3.15%7.39%6.15%WFD [25]5.38%3.37%7.39%6.15%AWFD [25]6.64%8.06%8.66%10.69%BFD [23]4.98%3.15%7.39%6.15%MBS [14]6.46%3.08%5.95%5.17%MBS’ [14]4.71%2.98%7.21%5.10%RBF4.68%1.01%1.98%1.39%


## 5.2.2. Results onSCH−WAE

The results of the compared algorithms onSCH−WAE are listed in Table 6. And, the detail results of RBF on SCH−WAE, that is, SOL, OPT, and the time cost (Runtime) on each instance, are shown in Tables 7 and 8. In the setting of Table 7, the number of items is 100 and the container capacity is 1000. Table 8 shows the statistical results when the number of items is 120. Meanwhile, Gap of each algorithm are shown in the last column of Table 5. It is shown that, in comparison with other algorithms on SCH−WAE, RBF achieved the minimum CRt and Gap, but the maximum was FSOL and RT. Especially, for SCH−WAE, IMPRBFMBS is 472%, while IMPRBFMBS′ is 346.88%.Table 6
Results onSCH−WAEn=200.
AlgorithmFSOLRTCRtNFD [24]10.501.0622FFD [23]10.501.0614WFD [25]10.501.0614AWFD [25]00.001.1069BFD [23]10.501.0614MBS [14]2512.501.0574MBS’ [14]3216.001.0513RBF14371.501.0139Table 7
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=100,C=1000SCH_WAE1_118181.462466SCH_WAE1_218182.727113SCH_WAE1_318183.150908SCH_WAE1_418183.70839SCH_WAE1_518180.539083SCH_WAE1_618180.758503SCH_WAE1_718180.664705SCH_WAE1_818180.679174SCH_WAE1_919184.522568SCH_WAE1_1018184.374016SCH_WAE1_1118180.982381SCH_WAE1_1218181.691106SCH_WAE1_1318184.604945SCH_WAE1_14191810.755302SCH_WAE1_1518181.797069SCH_WAE1_1618181.450974SCH_WAE1_1719181.246981SCH_WAE1_1818180.722101SCH_WAE1_1918180.713857SCH_WAE1_2018180.709936SCH_WAE1_2118180.998908SCH_WAE1_2219183.028952SCH_WAE1_2318180.557798SCH_WAE1_2418180.976983SCH_WAE1_2518181.074089SCH_WAE1_2619180.31875SCH_WAE1_2718183.446602SCH_WAE1_2818186.492802SCH_WAE1_2918184.080608SCH_WAE1_3018181.483333SCH_WAE1_3118180.731631SCH_WAE1_3218181.545062SCH_WAE1_3318181.73632SCH_WAE1_3418180.730045SCH_WAE1_3518181.060398SCH_WAE1_3618180.987255SCH_WAE1_37191813.783422SCH_WAE1_3818180.861974SCH_WAE1_3918183.244424SCH_WAE1_4018182.785588SCH_WAE1_4118181.43709SCH_WAE1_4218181.009547SCH_WAE1_4318181.022882SCH_WAE1_4418180.58083SCH_WAE1_4518184.300251SCH_WAE1_4618181.063874SCH_WAE1_4718187.621793SCH_WAE1_4818180.681381SCH_WAE1_4918180.96076SCH_WAE1_5018180.520412SCH_WAE1_5118180.706839SCH_WAE1_5218181.22345SCH_WAE1_5318181.450091SCH_WAE1_5418180.876361SCH_WAE1_5518180.839967SCH_WAE1_5618180.522451SCH_WAE1_5719189.148892SCH_WAE1_5818181.304132SCH_WAE1_5918180.91717SCH_WAE1_6018180.860201SCH_WAE1_61181811.420425SCH_WAE1_6218180.818042SCH_WAE1_6318181.024627SCH_WAE1_6418180.630548SCH_WAE1_6518181.120638SCH_WAE1_6618187.398161SCH_WAE1_6718181.001821SCH_WAE1_6818180.979633SCH_WAE1_6918180.681692SCH_WAE1_7019183.835019SCH_WAE1_7118184.387344SCH_WAE1_7218181.003916SCH_WAE1_7318183.558745SCH_WAE1_7419185.927648SCH_WAE1_7518180.779189SCH_WAE1_7618181.061736SCH_WAE1_7718181.168255SCH_WAE1_7819180.446685SCH_WAE1_7918181.053857SCH_WAE1_8018181.261393SCH_WAE1_8118183.997979SCH_WAE1_8218180.953343SCH_WAE1_8318180.918264SCH_WAE1_8418180.965771SCH_WAE1_8518180.714233SCH_WAE1_8618180.950277SCH_WAE1_8718181.366335SCH_WAE1_88181812.544721SCH_WAE1_8918180.918441SCH_WAE1_9018181.302644SCH_WAE1_9118182.591703SCH_WAE1_9218181.554301SCH_WAE1_9318181.055307SCH_WAE1_9418181.010704SCH_WAE1_9518181.482197SCH_WAE1_9618181.351396SCH_WAE1_9718181.305057SCH_WAE1_9818180.872971SCH_WAE1_9918183.715139SCH_WAE1_10018181.34348Table 8
Information of packing result for 200 instances ofSCH−WAE.
SetSOLOPTRuntime (s)Number of itemsn=120,C=1000SCH_WAE2_122227.881069SCH_WAE2_222223.576123SCH_WAE2_322213.484807SCH_WAE2_422212.672799SCH_WAE2_522221.696537SCH_WAE2_622226.829253SCH_WAE2_7222210.166636SCH_WAE2_821214.537143SCH_WAE2_922224.785806SCH_WAE2_1022211.873941SCH_WAE2_1122221.246602SCH_WAE2_1222221.538963SCH_WAE2_1322226.513991SCH_WAE2_1422213.337582SCH_WAE2_15222123.913958SCH_WAE2_1622221.695519SCH_WAE2_1722212.759149SCH_WAE2_1822222.037806SCH_WAE2_1922221.961526SCH_WAE2_2023227.537802SCH_WAE2_2122211.318665SCH_WAE2_2222221.634718SCH_WAE2_2322221.795601SCH_WAE2_2422221.40357SCH_WAE2_25222219.901876SCH_WAE2_26222110.612043SCH_WAE2_2722213.323103SCH_WAE2_2822212.773831SCH_WAE2_2922212.13123SCH_WAE2_3022212.424299SCH_WAE2_3122221.590401SCH_WAE2_3222221.371827SCH_WAE2_3322221.966954SCH_WAE2_3422213.440176SCH_WAE2_3522221.483907SCH_WAE2_3622226.622695SCH_WAE2_3722221.249159SCH_WAE2_3822221.299636SCH_WAE2_39222212.406897SCH_WAE2_4022222.000733SCH_WAE2_4122215.219861SCH_WAE2_42222116.346722SCH_WAE2_4322222.031538SCH_WAE2_4422222.05005SCH_WAE2_4522222.064586SCH_WAE2_4622211.883535SCH_WAE2_4722213.715486SCH_WAE2_4822214.25449SCH_WAE2_4922228.43341SCH_WAE2_5022212.382179SCH_WAE2_5122222.021937SCH_WAE2_5222221.854207SCH_WAE2_5322225.216751SCH_WAE2_54222218.804251SCH_WAE2_5522227.729899SCH_WAE2_5622212.015478SCH_WAE2_5722212.654803SCH_WAE2_5822222.015065SCH_WAE2_59222115.788445SCH_WAE2_60222212.14978SCH_WAE2_6122226.24467SCH_WAE2_6222212.718076SCH_WAE2_63222110.584626SCH_WAE2_6422212.177987SCH_WAE2_6522224.06024SCH_WAE2_6622221.741747SCH_WAE2_6722222.653687SCH_WAE2_6822221.437786SCH_WAE2_6922213.402605SCH_WAE2_7022223.326743SCH_WAE2_7122212.248744SCH_WAE2_72222216.249829SCH_WAE2_7322221.297735SCH_WAE2_74222117.573503SCH_WAE2_7522211.374113SCH_WAE2_7622222.612285SCH_WAE2_7722213.444593SCH_WAE2_7822212.393924SCH_WAE2_7922212.894696SCH_WAE2_80232214.637149SCH_WAE2_81232211.182882SCH_WAE2_8222223.12165SCH_WAE2_8322211.875829SCH_WAE2_84222210.238209SCH_WAE2_8522218.727173SCH_WAE2_8622224.11194SCH_WAE2_8722214.925202SCH_WAE2_8822221.467682SCH_WAE2_8922221.679621SCH_WAE2_9022217.822758SCH_WAE2_9122212.573397SCH_WAE2_9222212.676046SCH_WAE2_9322213.51098SCH_WAE2_9422211.595649SCH_WAE2_9522212.751163SCH_WAE2_9622212.599518SCH_WAE2_9722221.551431SCH_WAE2_9822212.829111SCH_WAE2_9922221.861101SCH_WAE2_10022212.520166


## 5.2.3. Cumulative Results

For all the instances inBINDATA and SCH−WAE, the cumulative packing results of the compared algorithms, such as the cumulative FSOL, the average RT, the average CRt, and the average Gap, are shown in Table 9. It is shown that RBF obtained 1162 cumulative FSOL and the RT was 82.41%, which greatly overwhelmed other compared algorithms. Especially, according to formula (17), the cumulative improvement of RBF to MBS and MBS’, correspondingly, IMPRBFMBS and IMPRBFMBS′, is 189.05% and 27.41%, respectively. Figure 2 graphically shows the statistical FSOL of the comparison algorithm on each dataset. It is noted that, from the radar in Figure 2, the quantitative curve of RBF for FSOL is at the outermost. It means that RBF achieved the largest number of optimal solutions in the test cases. Also, RBF achieved the minimum CRt and Gap. Results indicate that, in comparison with the typical heuristic algorithms, RBF has a stronger global optimal performance. Overall, the proposed RBF obtains first ranks in all metrics according to the results of all compared algorithms listed in Tables 4–6. In detail, the improvement in FSOL of uncomplicated datasets, Bin1data, is limited among all compared methods. RBF achieves best results and wins with few advantages. However, RBF works much better than other methods on difficult datasets, bin2data, bin3data, and SCH−WAE. Besides, RBF achieves huge advantages in Gap, and it wins almost all other methods on used datasets.Table 9
Average results.
AlgorithmNFD [24]FFD [23]WFD [25]AWFD [25]BFD [23]MBS [14]MBS’ [14]RBFCumulativeFSOL607836561647844029121162Average RT4.26%55.53%46.52%11.63%55.60%28.51%64.68%82.41%AverageCRt1.17761.05411.05561.08501.05411.06601.04921.0226AverageGap17.77%5.42%5.57%8.51%5.42%5.17%5.00%2.27%Figure 2
The number of instances to optimal solution by each algorithm.


## 5.3. Robustness and Stability

The construction of the validation set is a key procedure of RBF. This experiment is carried out to verify the validity of the eigenvalue mapping function on the Bin1data. Since 10 instances of the Bin1data are selected to form the validation set by the eigenvalue mapping function, here different selection policy are applied for comparison in the packing process. The first policy is that the first 10 instances of the Bin1data are selected, the second policy is that the last 10 instances of the Bin1data are selected, and the third policy is that 10 random instances of the Bin1data are selected to form the validation set. The packing results with different selection policies are depicted in Table10. It can be seen that the value of slack learned by Q-agent is different with different selection policies. Especially, with the selection policy of the eigenvalue mapping function, RBF achieved the maximum FSOL and RT, while the minimum was CRt and Gap. The results verified the validity of the eigenvalue mapping function, which helped RBF achieved better performance.Table 10
Statistical results with different composition of validation sets.
Validation setParameterωFSOLRT (%)CRtGap (%)Top 10 cases0.181718926.251.05325.32The last 10 cases0.871023232.221.06205.87Random 10 cases0.453230742.641.04924.93Mapping 10 cases0.581366892.781.04684.68


## 6. Conclusion and Future Work

In this paper we propose reinforced bin packing framework (RBF) to tackle the one-dimensional BPP. The proposed RBF consists of three main components: the RL-system, the instance-eigenvalue mapping process, and the reinforced-MBS strategy. The RL-system is designed to construct a slack selection policy automatically byQ-agent to select high-quality slack for the heuristic algorithm integrated in RBF. The instance-eigenvalue mapping process is utilized to generate the representative and classified the validate set based on the similarity of the input instances, which greatly eliminates the computational overhead and improves the generalization performance of the model. Finally, with the provision of the slack coefficient from the RL-system, the reinforced-MBS strategy is exploited to resolve the packing process. We evaluate our models on BPP tasks, where RBF exhibits excellent packing ability and experimental results validate its superior performance compared to state-of-the-art proposals on BINDATA and SCH−WAE datasets. Compared to its baseline methods, MBS and MBS’, the average number of optimal solutions achieved by RBF increases by 189.05% and 27.41%, respectively.For future work, we plan to investigate slack selection policies and new mechanisms to learn them automatically. We also foresee the extension of our method to more complex multiagent reinforcement learning frameworks, where the use of new aspects of the multiagent communication environment is crucial to boost the packing performance.



---

*Source: 6653586-2021-05-19.xml*