摘要
研究了广泛存在于生产制造中的二维矩形件下料问题,提出一种边缘匹配度算法和变邻域搜索算法相结合的混合算法进行求解。首先,分析了一般最低水平线相关算法的缺陷,提出了一种边缘匹配度评价函数。下料时其可以对所有剩余的矩形件进行评价,从中选出与当前布局边缘重合最大的矩形件进行排放。其次,由于下料问题存在上位效应,提出一种与其相匹配的邻域结构,得到了一种适应下料问题的变邻域搜索算法,边缘匹配度算法通过与变邻域搜索算法结合来加强其搜索能力。最后,通过对已有文献的多个案例进行试验。实例证明提出的算法可以得到较好的排样结果,相较于其它算法提高了板材利用率1.16%~12.03%,具有较高的实用性。
A hybrid algorithm combining edge matching degree algorithm and variable neigh-borhood 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 neighbor-hood 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,experi-menting 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.
作者
王巍
马威
曹颖
WANG Wei;MA Wei;CAO Ying(College of Engineering and Technology,Northeast Forestry University,Harbin 150040,China)
出处
《青岛科技大学学报（自然科学版）》
CAS
2023年第2期108-115,共8页
Journal of Qingdao University of Science and Technology:Natural Science Edition
基金
中央高校基本科研业务费专项资助基金项目(2572019BL04)
黑龙江省留学归国人员科学基金项目(LC201407)。
关键词
二维矩形下料
布局优化
变邻域搜索算法
边缘匹配度算法
two-dimensional rectangle packing
layout optimization
variable neighborhood search algorithm
edge matching degree algorithm
