Abstract: Rectangle strip packing problem is a combinational optimization problem with NP complete hard,an improved surplus rectangle algorithm based on weighted matching function was presented to solve rectangle strip packing problem.A weighted matching function based on multiple factors was designed,which used bidirectional selection strategy to select the most suitable rectangle item and the surplus rectangle for the best fit from the surplus rectangle set and the rectangle item set.A dynamic placement policy was employed to place the item at a certain position based on the fitness value of the weighted matching function.The post process for the highest position consisting of the rotation process and the shift process was implemented to reduce the height of packing.As to different benchmark test instances,dynamic weight values were employed and the particle swarm optimization algorithm was used to search the optimal weight values.The computational results for the benchmark test instances showed that the proposed approach based on the weighted matching function and the dynamic placement policy could much effectively decrease the packing height comparing with the traditional surplus rectangle algorithm.From the average errors of packing height for the test instances,the proposed algorithm well outperformed the Best Fit (BF) algorithm and its improved algorithms,which was nest only to the heuristic algorithms based on the scoring rule.

Key words: rectangle strip packing problem, surplus rectangle algorithm, weighted matching, dynamic placement, post process, particle swarm optimization algorithm

摘要： 矩形条带装箱问题是一类具有NP-Complete求解复杂性的组合优化问题,提出一种基于加权匹配函数的改进剩余矩形法用于求解矩形条带装箱问题。设计一种多因素加权匹配函数,采用双向选择策略,在剩余矩形集合和待排放矩形件集合中,选择最合适的剩余矩形和矩形件实现最优匹配。基于加权匹配函数值,采用动态放置策略用于确定矩形件在剩余矩形中的放置位置。为了降低装箱高度,采用了旋转和平移后处理工艺对位于最高位置的矩形件进行调整。不同算例采用动态权重模式,利用粒子群算法用于搜索和确定最优权重值。针对典型算例的实验结果表明,相比传统剩余矩形法,改进剩余矩形法能够有效降低装箱高度。从测试算例装箱高度的平均误差看,计算结果也明显好于BF(Best Fit)算法及其改进算法,仅次于基于评分规则的启发式算法。

关键词: 矩形条带装箱问题, 剩余矩形法, 加权匹配, 动态放置, 后处理, 粒子群算法