边缘匹配度算法与变邻域搜索结合的矩形件下料算法

全文下载： 202302015.pdf

文章编号： 1672-6987（2023）02-0108-08； DOI： 10.16351/j.1672-6987.2023.02.015

王巍， 马威， 曹颖(东北林业大学 工程技术学院，黑龙江 哈尔滨 150040)

摘要： 研究了广泛存在于生产制造中的二维矩形件下料问题，提出一种边缘匹配度算法和变邻域搜索算法相结合的混合算法进行求解。首先，分析了一般最低水平线相关算法的缺陷，提出了一种边缘匹配度评价函数。下料时其可以对所有剩余的矩形件进行评价，从中选出与当前布局边缘重合最大的矩形件进行排放。其次，由于下料问题存在上位效应，提出一种与其相匹配的邻域结构，得到了一种适应下料问题的变邻域搜索算法，边缘匹配度算法通过与变邻域搜索算法结合来加强其搜索能力。最后，通过对已有文献的多个案例进行试验。实例证明提出的算法可以得到较好的排样结果，相较于其它算法提高了板材利用率116%~1203%，具有较高的实用性。

关键词： 二维矩形下料； 布局优化； 变邻域搜索算法； 边缘匹配度算法

中图分类号： TP 391文献标志码： A

引用格式： 王巍， 马威， 曹颖. 边缘匹配度算法与变邻域搜索结合的矩形件下料算法［J］. 青岛科技大学学报(自然科学版), 2023, 44(2): 108-115.

WANG Wei， MA Wei， CAO Ying. Optimal algorithm on rectangular pieces layout combining edge matching degree algorithm and variable neighborhood search［J］. Journal of Qingdao University of Science and Technology（Natural Science Edition), 2023， 44（2）： 108-115.

Optimal Algorithm on Rectangular Pieces Layout Combining Edge Matching

Degree Algorithm and Variable Neighborhood Search

WANG Wei， MA Wei， CAO Ying

(College of Engineering and Technology, Northeast Forestry University, Harbin 150040, China)

Abstract: A hybrid algorithm combining edge matching degree algorithm and variable neighborhood search algorithm is proposed for solving the two-dimensional rectangular part layout problem, which widely exists in manufacturing. Firstly, an edge matching degree evaluation function is proposed based on the defects of the general minimum horizontal line correlation algorithm. Secondly, due to the epistatic effect of the layout problem, a matching neighborhood structure is proposed. Then a variable neighborhood search algorithm adapted to the layout problem is obtained. The search capability of the edge matching degree algorithm is enhanced by combining it with the variable neighborhood search algorithm. Finally, experimenting with several cases in the existing literature show that the proposed algorithm can get better results. Compared with other algorithms, the algorithm improves plate utilization by 116% to 1203%, which has high practicality.

Key words: two-dimensional rectangle packing; layout optimization; variable neighborhood search algorithm; edge matching degree algorithm

收稿日期： 2022-07-14

基金项目： 中央高校基本科研业务费专项资助基金项目（2572019BL04）；黑龙江省留学归国人员科学基金项目（LC201407）.

作者简介： 王巍(1975—), 女, 教授.