To explain our proposed methodology, we present the representation of the interior packing state at each placement step, along with the algorithm designed to optimize the sequence and orientation of items, incorporating the BLF heuristic and the Q-learning algorithm.
A common constructive algorithm for 2D cutting or packing problems is the BL heuristic, which places pieces in the lowest possible position and then as far left as possible without overlapping, aiming to minimize height, as illustrated by
The constructive rectangular packing algorithm takes the sheet width W, the number of items n, and the dimensions of the items {(w1, h1), (w2, h2), (w3, h3) … (wn, hn)} as inputs, executes the packing process, and returns the layout along with the packing length L.
Examples of application of the Bottom-Left (BL) and Bottom-Left-Fill (BLF) placement strategies.
This figure is shown in the PDF version of the article.
Bottom-Left-Fill algorithm.
This table is shown in the PDF version of the article.
RL is a category of machine learning problems that involve an autonomous agent interacting with an environment. The agent perceives information about its current state and takes actions accordingly. In return, the environment responds with a reward signal, which may be positive or negative. The agent's goal is to maximize the expected cumulative reward signal throughout its interactions Ernst and Louette
s0, a1, s1, r1, a2, s2, r2. . . , an, sn, rn. (1)
At the i-th stage, ai and si refer to the action and state, respectively, where i ∊ [1, n], and ri indicates the immediate reward obtained by the piece in state si. The evaluation strategy, denoted as ( | ), can adopt methods like the greedy algorithm. The action a_i denotes the piece the agent selects in state s _ {i-1}. Upon completing ai, the environment transitions from state si-1 to si, where si = ai, representing the current piece number. In this study, the state is the set of items already placed, while the action is the item to be placed along with its orientation. The reward is represented as the reciprocal of the total layout length.
The state s_t is defined as the partial packing history, represented by the ordered sequence of dimensions of the rectangles that have already been placed. Formally, s_t = [(h_1, w_1 ), (h_2, w_2 ), … , (h_t, w_t )], where (h_k,w_k ) denotes the width and height of the k-th placed rectangle in its placed orientation. At each decision step, the action is defined as a_t=(j_t,o_t ), where〖 j〗_t denotes the selected item (rectangle) to be placed, and o_t∈ {0,1} is the rotation indicator. Specifically, o_t=0 represents the original orientation (no rotation), while o_t=1 denotes a 90° rotation before placement .
Choice of items and Markov decision process.
This figure is shown in the PDF version of the article.
In this paper, the reward r is assigned after completing a packing process, where rn = C/H ≠ 0. Here, C is a constant, and H represents the packing height achieved after placing all items. The immediate rewards for intermediate steps are set as r1 = r2 = r3 = . . . = rn − 1 = 0. Consequently, a lower packing height results in a higher packing utilization rate and a greater reward value. Within each episode, the agent traverses all items to be packed once, ensuring the packing process completes in a single run. Thus, each episode consists of n iterations to sequentially select and pack these n items .
In general classification, Fang, Rao, Zhao, et al.
Q(s, a) = Q(s, a) + α [r(s, a) + γ ∗ Max Q(s^′, a^′ ) − Q (s, a)].
where α is the learning rate, γ is the discount factor, and s' and a' correspond to the state and action of the subsequent stage, respectively.
Based on Formula (1), we enhance the traditional Q-learning algorithm. Instead of updating the Q (s, a) values at each stage during the episode, the updates are deferred to the end of the episode, where all state-action pairs are updated collectively. This process is carried out in reverse order, following the sequence Q (sn-1, an), Q (sn-2, an-1), Q (sn-3, an-2) … Q (s0, a1). By adopting this approach, the Q(s, a) values for all state-action pairs are effectively updated, ensuring that each episode's exploration experience is fully leveraged to improve decision-making in subsequent episodes.
Q-Learning algorithm
This table is shown in the PDF version of the article.