基于启发式的二维不规则多规格板材排样问题研究.pdfVIP

2024年01月机电工程技术Jan.2024

第53卷第01期MECHANICALELECTRICALENGINEERINGTECHNOLOGYVol.53No.01

DOI:10.3969/j.issn.1009-9492.2024.01.029

吴松桓，唐超，魏丽军.基于启发式的二维不规则多规格板材排样问题研究［J］.机电工程技术，2024，53（01）：130-135.

基于启发式的二维不规则多规格板材排样问题研究*

吴松桓，唐超，魏丽军※

（广东工业大学机电工程学院，广州510006）

摘要：二维不规则板材排样在工业生产中的应用十分广泛，属于空间布局优化问题。目前该方向的研究主要考虑单规格板材，缺

乏在多规格板材上排样不规则零件的研究。提出了一种启发式算法求解二维不规则多规格板材排样问题，该问题需要把不规则零

件打包到不同尺寸的板材中，使得所选板材的面积总和最小。为了解决该问题，采用回溯算法和剪枝策略生成板材组合，通过二

分有哪些信誉好的足球投注网站策略选定并切换板材组合。对于给定板材组合，提出了基于重叠移除的排样算法，首先通过首次适应下降策略和左下算法

尝试把每个零件放置在板材里面，假若还有零件未能放置在板材里面，则运用插入算法把这些零件插入到板材中重叠最小的位置，

再通过邻域有哪些信誉好的足球投注网站和重叠移除算法最小化重叠值，从而求得可行解。对多规格板材的算例进行测试，实验结果表明，该启发式算法

可有效解决二维不规则多规格板材排样问题。

关键词：切割；下料；不规则板材排样；启发式

中图分类号：TP27文献标志码：A文章编号：1009-9492（2024）01-0130-06

AHeuristicfortheTwo-dimensionalMultipleBinSizeIrregularBin

PackingProblem

WuSonghuan，TangChao，WeiLijun

（SchoolofElectromechanicalEngineering,GuangdongUniversityofTechnology,Guangzhou510006,China）

Abstract:Two-dimensionalirregularbinpackingiswidelyusedinindustrialproduction,whichbelongstospatiallayoutoptimizationproblem.

Atpresent,theresearchinthedirectionmainlyconsidersthesingle-sizebins,andthereisalackofresearchonpackingirregularpieceson

multiple-sizebins.Aheuristicisproposedtosolvethetwo-dimensionalmultiplebinsizeirregularbinpackingproblem.Theproblemrequires

packingirregularpiecesintobinsofdifferentsizessothatthetotalareaoftheselectedbinsisminimized.Inordertosolvetheproblem,the

heuristicusesbacktrackingalgorithmandpruningstrategytogeneratebincombinations,andthenselectsandswitchesbincombinationsby

binarysearchstrategy.Foragivenbincombination,apackingalgorithmbasedonoverlapremovalisproposed.First,trytoplaceeachpiecein

thebinthroughthefirstfitdec