Research On Hybrid Heuristic Algorithm For Two-dimensional Strip Packing Problem

The two-dimensional strip packing problem is a classic NP-hard combinatorial optimization problem,which has been widely used in practical life and industrial production.Studying this problem is of great significance for enterprises to save costs,save resources and improve production efficiency.The main work of this paper is to study the two-dimensional strip packing problem and propose two algorithms:the hybrid heuristic algorithm(HHA)and the enhanced hybrid heuristic algorithm(RLHHA).The hybrid heuristic algorithm proposed in this paper consists of three key parts.Firstly,this paper improves the corner increment strategy and proposes a δ scoring rule.This rule is used to evaluate candidate rectangles when selecting rectangles,and can effectively filter out rectangles that best match the available space.Secondly,we use two red-black trees with special ordering rules to store the sequence of rectangles.It can quickly find candidate rectangles and improve the efficiency of the algorithm.In addition,in order to find a better solution,we combine an accurate algorithm with a heuristic algorithm and propose a hierarchical search method combined with the idea of random local search to optimize the solution.Experimental results on 737 standard problem instances show that the proposed hybrid heuristic algorithm performs better than our known algorithm on most examples.This paper proposes an enhanced hybrid heuristic algorithm combined with reinforcement learning.Our novel use of reinforcement learning provides an initial boxing sequence for the heuristic algorithm to effectively improve the heuristic cold start problem.The reinforcement learning model can perform self-driven learning,using only the value of the heuristically calculated solution as a reward signal to optimize the network,so that the network can learn a better packing sequence.We use a simplified version of the pointer network to decode the output boxing sequence.The model consists of an embedding layer,a decoder,and an attention mechanism.ActorCritic algorithm is used to train the model,which improves the efficiency of the model.We test the enhanced hybrid heuristic algorithm on 714 standard problem instances and 400 generated problem instances.Experimental results show that the reinforcement learning model can effectively improve the heuristic cold start problem and help the hybrid heuristic algorithm to get better solution.