下载文档原格式
矩形排样算法python矩形排样算法Python介绍矩形排样算法是一种优化材料利用率的算法，它可以将多个不同尺寸的矩形按照一定规则排列在一个大矩形中，以最大限度地减少材料浪费。
Python是一种流行的编程语言，其简单易学、灵活性强、可读性好等特点使得它成为了很多人选择的编程语言。
本文将介绍如何使用Python实现矩形排样算法。
算法思路1. 将所有待排放的矩形按面积从大到小排序。
2. 选择一个初始点作为第一个矩形的左下角点。
3. 依次将每个矩形放置在已有布局中，找到一个最佳位置，使得当前布局下剩余空间最小。
4. 如果无法找到合适位置，则向上移动当前位置，直至找到合适位置或者无法再移动。
5. 如果所有位置都无法放置当前矩形，则回溯到上一个已经放置好的矩形，并向上移动该矩形，直至找到合适位置或者无法再移动。
6. 如果所有已经放置好的矩形都无法再向上移动，则回溯到上一个已经放置好的但是还有可能向上移动的矩形，并向上移动该矩形。
7. 重复步骤3-6，直至所有矩形都被放置。
实现下面是一个简单的Python实现：```pythonclass Rectangle:def __init__(self, width, height):self.width = widthself.height = heightself.x = 0self.y = 0class Layout:def __init__(self, width, height):self.width = widthself.height = heightself.rectangles = []def add_rectangle(self, rectangle):self.rectangles.append(rectangle)def get_remain_space(self):remain_width = self.widthremain_height = self.heightfor rectangle in self.rectangles:remain_width -= rectangle.widthif rectangle.height > remain_height:remain_height = rectangle.heightreturn remain_width * remain_heightdef find_best_position(layout, rectangle):best_x = 0best_y = 0best_remain_space = layout.get_remain_space()for y in range(layout.height - rectangle.height + 1):for x in range(layout.width - rectangle.width + 1):can_place_here = Truefor placed_rectangle in layout.rectangles:if (x < placed_rectangle.x + placed_rectangle.width and x + rectangle.width > placed_rectangle.x and y < placed_rectangle.y + placed_rectangle.height and y + rectangle.height > placed_rectangle.y):can_place_here = Falsebreakif can_place_here:layout.add_rectangle(rectangle)rectangle.x = xrectangle.y = yremain_space = layout.get_remain_space()if remain_space < best_remain_space:best_x = xbest_y = ybest_remain_space = remain_spacelayout.rectangles.pop()rectangle.x = best_xrectangle.y = best_ylayout.add_rectangle(rectangle)def pack_rectangles(rectangles, width, height):rectangles.sort(key=lambda r: r.width * r.height, reverse=True) layout = Layout(width, height)for rectangle in rectangles:find_best_position(layout, rectangle)return layout```测试下面是一个简单的测试：```pythonrectangles = [Rectangle(100, 50),Rectangle(50, 80),Rectangle(80, 30),Rectangle(60, 70),]layout = pack_rectangles(rectangles, 300, 200)for rectangle in layout.rectangles:print(f"({rectangle.x}, {rectangle.y}) - ({rectangle.x + rectangle.width}, {rectangle.y + rectangle.height})")print(f"Remain space: {layout.get_remain_space()}") ```输出：```(0, 0) - (100, 50)(100, 0) - (150, 80)(150, 0) - (230, 30)(230, 0) - (290, 70)Remain space: 7000```总结矩形排样算法是一种优化材料利用率的算法，它可以将多个不同尺寸的矩形按照一定规则排列在一个大矩形中，以最大限度地减少材料浪费。
结合批量问题的多目标矩形件优化排样郑明月;刘林;阚方;方昶【摘要】This paper studies the multi-objective rectangle packing problem combined with lot-sizing problem by multi-objec-tive heuristic evolutionary algorithm. Establish a multi-objective optimization model containing the raw materials cost minimization and parts inventory cost minimization. Initialize the patterns by heuristic algorithm and then use improved fast non-dominated sorting algorithm getting the cutting program. Through the results and comparison with other algorithms, this algorithm can solve small rectangle packing problem with high utilization and low total cost in a fast time.%设计多目标启发式进化算法，研究了一种考虑批量问题的二维矩形件排样问题，建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。
先用启发式算法初始化下料方式，再用改进的快速非支配排序算法进行优化求解，确定下料方案。
通过实验结果以及与其他算法的对比表明，在中等规模的矩形件排样问题中，该算法能够在较快的时间内既保证较高的原料利用率，又能降低该问题的总成本，证明了该算法的有效性。
目录1. 矩形件排样的问题描述： (2)2. 算法分类 (2)2.1. 启发式算法 (2)2.1.1.基于最低水平线算法[2] (2)2.1.1.1. 基于最低水平线的二维搜索算法[3] (2)2.1.1.2. 文献[8] (4)2.1.1.3.基于二维装箱问题的矩形件排样算法[9] (6)2.1.2. Best-fit算法 (9)2.1.2.1.A squeaky wheel optimisation packing methodology（SWP）[4] (9)2.1.3. 分层排布算法 (11)2.1.3.1. Modified size-alternating stack algorithm(SASm)[5] (11)2.1.3.2.Best fit with stacking algorithm (BFS) [5] (12)2.1.4. 其他启发式算法 (13)2.1.4.1. 文献[10] (13)2.1.4.2. 文献[11] (16)2.2. 智能算法 (19)2.2.1. PSO算法 (19)2.2.1.1. 文献[12] (19)3. 上述算法在矩形排样件中的应用分类 (21)4. 参考文献 (22)部分2010年矩形件优化排样算法的研究进展1.矩形件排样的问题描述：参见文献[1]:矩形件排样题指在给的矩形板材上将一系列矩形零件按最优方式进行排布。
即给定n个零件R=（R1，R2，，…，Rn)，将零件置于宽度为W，高度为L的板材P上，使得板材的利用率最高，并要求满足下列约束条件:(1)Ri、Rj互不重叠, i≠j, i, j=1,2,…,n;(2)Ri能够且必须放在P内, i= 1,2,…,n;(3)满足一定工艺要求。
2.算法分类2.1.启发式算法2.1.1.基于最低水平线算法[2]2.1.1.1.基于最低水平线的二维搜索算法[3]为了提高矩形件排样时材料的利用率,针对定序列矩形件优化排样问题,本文在＂基于最低水平线的搜索算法＂的基础上,提出了一种改进的矩形件优化排样算法——基于最低水平线的二维搜索算法.此改进算法在＂基于最低水平线的搜索算法＂基础上,进行了排样宽度的二维搜索,即有如下改进：基于最低水平线的搜索算法只进行入排宽度的搜索(即矩形宽度的搜索)，而本文提出的排样算法不仅优先进行入排宽度的搜索，而且在入排宽度均不符合排样要求时，还进行了待排宽度的搜索(即矩形高度的搜索)。
二维矩形排样问题是在给定的矩形板材上排放一系列矩形零件，且所有零件采用正交排放的方式，被排放的零件之间不能有重叠，且零件必须全部排放在板材内部。
以下是一种可能的算法：
1. 初始化水平线集，初始状态下水平线集中只有一条水平线，为坐标系中板材最底部的边。
2. 选择要排入的零件。
3. 从水平线集中的选取最低的那条水平线，如果最低水平线不止一条则选取最靠左边的那条。
4. 如果被选中的水平线的宽度大于要排入的矩形零件的长度，执行步骤(4)，否则执行步骤(5)。
5. 将该零件排放在最低水平线的最左端，更新水平线集。
6. 选择与最低水平线相邻且高度较低的一段水平线，将最低水平线提升与该水平线平齐，更新水平线集。
7. 判断所有零件是否排样完毕，若排放完毕则排样结束，否则转向执行步骤(2)。
这个算法的基本思想是尽可能地将零件放入更少的层数中，以提高板材的利用率。
矩形件排样算法探讨作者：苏厚仁钟相强来源：《科技视界》2015年第33期【摘要】针对二维矩形件优化排样问题，提出一种新型的算法——矩形动态匹配算法。
通过对零件的矩形化预处理，并自动正交排布使零件紧密靠接和定位，从而实现复杂不规则船体零件的矩形化排样，该算法亦可扩展用于三维空间零件的排样求解，实例证明其有效性。
【关键词】排样；矩形零件；优化；算法【Abstract】For optimal nesting of rectangular parts of a two dimensional problem， a new kind of algorithm is put forward. The rectangular pretreatment and automatically orthogonal configuration make the location of parts more close， the rectangular optimization nesting of complex irregular ship parts is realized， the algorithm can be extended to 3d space parts. Examples show its effectiveness.【Key words】Parking； Rectangular parts； Optimization； Algorithm0 引言排样优化技术是工业产品设计、制造中如何节约原材料、优化利用资源的重要手段。
现实零件形状复杂，多为不规则零件，且制造特征和方法各异，如何采用有效的算法实现最优布局、提高原材料的利用率尤为重要[1-3]。
文中基于对排样零件矩形化预处理提出了矩形动态匹配算法来实现零件的定位，具有较高的材料利用率。
1 算法简介1.1 实现算法的前提条件将一个矩形零件排放在矩形板材中，需要解决的问题有：（1）多个矩形零件排放时的排放次序。
浅谈如何优化下料方法摘要：本文通过对车间下料调查研究后，分析了其生产现状，发现了诸多问题，故提出优化下料工序的生产管理，使数控下料能更加科学合理,从而提高生产效率和质量。
关键词：数控；切割；变形；设备1.课题研究背景现今，钢结构制造行业市场竞争格外激烈，而生产成本、生产效率则是企业是否具有市场竞争力的先决条件。
通常而言，材料成本为整个生产体系的关键成本，能高达总体成本的60%-80%。
现实中钢构件排料大多为人工排料，此法过于依赖员工的生产经验，工作量大，效率和材料利用率都不高，嵌套过程不仅消耗了企业技术人员的大量劳动，而且耗时较长，大大降低了原料的利用率以及生产效率，无形中加重了在建项目的成本负担。
本文所提出的优化布局是指将不同数量和形状的零件布置在多张钢板上，巧妙利用计算机合理布局，不仅可以提高排料速度，还能进一步节省材料。
相较于人工排料的方案来说，即便实际的利用率数据提升1%，最终效益也非常可观。
良好的开端是成功的一半，从原材料到最终钢结构产品，数控下料作为项目开工的首道工序，走好这第一步尤为重要。
目前，钢结构制造项目中普遍存在的问题是材料种类多、构件数量多，现场工件的管理较为混乱，缺件多件情况时有发生，不仅浪费了原材料，而且耗费了大量人力，严重制约了生产。
2.优化下料方法简述2.1有效利用排料APP精细布局排版现国内钢结构制造行业广泛使用的钢材下料模式有如下两种:（1）人工排料。
对特定项目而言，依据设计图开展细节的结构拆分，捕捉相应的下料信息，依托人工方法开展排料，再结合排料方案进行板材切割的处理。
若构件数量很少时，此法简单快捷。
但若某一类型的构件数量较多，外形较为复杂时，单靠员工凭经验完成下料工作，原材料利用率和工作效率都很低。
需求的材料以及工时，都很难精准把控，有碍材料的管理以及生产计划的调整。
（2）发展软件辅助排料。
将最优化理论应用于实践场景，配合计算机的辅助方案，进而取代人工排料。
板材下料问题 Prepared on 22 November 2020板材玻璃的下料问题摘要“下料问题（cutting stock problem）”就是指在给定板材宽度和长度的情况下，如何将具有一定种类和数量的矩形件排放到板材上，使所需的板材数量最少的问题，该问题广泛存在于工业生产中。
本文运用优化理论，建立了矩形件优化排样数学模型，并提出了基于启发式算法的一刀切约束条件下二维板材下料算法。
关键词下料二维下料问题优化启发式算法矩形件排样一刀切一、问题的重述在大型建筑工程中，需要大量使用玻璃材料，如门窗等。
在作材料预算时，需要求出原材料的张数。
已知板材玻璃原材料和下料后的成品均为矩形。
由于玻璃材料的特点，切割玻璃时，刀具只能走直线，且中间不能拐弯或者停顿，即每切一刀均将玻璃板一分为二。
切割次序和方法的不同、各种规格搭配（即下料策略）不同，材料的消耗将不同。
工程实际需要解决如下问题，在给定一组材料规格尺寸后：（1）在原材料只有一种规格的情况下（例如长为2100cm，宽为1650㎝），给出最优下料策略，此时所需要材料张数最小。
（2）在原材料为两种规格的情况下（例如2100cm*1650cm和2000cm×1500cm），给出最优下料策略，使所需材料的张数最小，且利用率（实际使用总面积与原材料总面积之比）尽量高。
（3）下表是一些成品料及所需块数（长×宽×块数）分别以一种原材料2100cm×1650cm及两种原材料规格2100cm×1650cm,2000cm×1500cm为例，分别给出（1）和（2）的算法及数字结果，并给出两种情况下的利用率。
二、问题的分析本问题属于二维下料问题，该问题已被证明为是NP完全问题。
由于任何NP完全问题都不能用任何已知的多项式算法求解，所以我们建立一个排样的算法模型。
由题目要求该算法首先要满足生产工艺，即要满足“一刀切”，即从板材的一端，沿直线方向切割到另一端。
矩形件排样最优化问题求解张青;刘芳【摘要】In order to resolve the problems of low manual typesetting efficiency and poor typesetting utilization rate of large-scale wedding dress developing companies,a layout optimization solution of rectangular pieces,that is,automatic photo typeset-ting method based on the expert template,is proposed. After a certain company′s testing for half a year,the test results show that the typesetting utilization rate of the proposed method is 4.3% higher than that of the manual typesetting,and the work effi-ciency has been increased by some orders of magnitude.%为了解决大型婚纱冲印公司人工排版效率低,排版利用率差的问题,提出一种矩形件排样最优化的解决思路,即基于专家模板的照片自动排版方法.经过某公司半年测试,其方法排版利用率高于人工排版4.3个百分点,工作效率则实现数量级的提升.【期刊名称】《现代电子技术》【年(卷),期】2017(040)022【总页数】3页(P72-74)【关键词】矩形件排样;自动排版;婚纱冲印;排版利用率【作者】张青;刘芳【作者单位】南宁职业技术学院信息工程学院,广西南宁530000;广西大学计算机与电子信息学院,广西南宁530004【正文语种】中文【中图分类】TN081-34矩形件优化排样问题广泛地出现于轻工、家具、造纸及玻璃切割等行业，它将许多小矩形件尽可能多地、无重叠地排放到一个定宽、定长的矩形板材上，使其利用率达到最大[1]。
矩形件排样程序实现（要求：只能由一个学生独立完成，不得抄袭）工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。
例如在一块宽40、高15的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。
图1 一种排样方案
表1 小矩形的尺寸
序号宽高
1 1
2 6
2 4 7
3 6 7
4 10 2
5 2 5
6 6 4
7 4 2
8 4 6
9 7 9
10 4 5
11 6 4
12 4 6
13 6 3
14 4 5
15 2 4
16 8 4
17 8 6
18 8 3
19 6 3
20 2 6
21 8 2
22 3 5
23 2 5
24 3 4
25 2 4
如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形
按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。
通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，p i 为矩形件的序号，r i 为排样方式，r i =1表示将矩形件旋转90°, r i =0表示矩形件不旋转。
将第i 个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL 条件（bottom-left-condition ，BL-condition ）。
基于BL 条件，有一种下台阶算法，具体步骤如下：
(1) 将零件1p 排放在板材的左下角，若11=r 则将其旋转90°后再排放，求出排放后所占板材的最大高度；
(2) 将i p ),,3,2(n i =根据其排样方式置于板材右边最大高度处，向下向左移动i p ，且向下移动优先（即原本已无法再向下移动，故开始向左移动，而在向左移动的过程中若发现又能继续向下移动，则先向下移动），直至i p 无法向下向左移动为止（即接触到其他零件或板材边界），并求出此时的最大高度；
(3) 重复上述过程，直至所有零件排放完毕，最后所得最大高度即为所需板材高度。
其排样过程如图2所示，就好象下台阶一样，于是形象地称之为下台阶算法。
图2 下台阶算法的排样过程
剩余矩形排样法是目前所提出的一种有效的排样算法，该方法记录了所有可利用的空间，更能合理地分配给待排样的矩形件，提高了每个排样方案的板材利用率，更接近最优排样方案。
例如对于同一个矩形件序列)4,3,2,1(进行排样，
图3(a)中下方的空洞以往的排样算法都无法利用，矩形4只能被排到上方。
而利用剩余矩形排样法可以很好的解决这个问题，它可以使矩形4充分利用下方的空间，如图3(b)。
图3 剩余矩形排样法的优越性
剩余矩形排样算法用一个矩形数据集合来表示板材目前的剩余位置情况，任何未被排样的空间（包括孤立的缝隙），都在剩余矩形集合中表示，不会遗漏任何一个。
而在每一个矩形件被排入前，都需根据这个剩余矩形集合中的数据来选择最为合理的位置进行排放。
下面给出剩余矩形的具体形成方法（这里用矩形的左下角坐标和右上角坐标来确定这个矩形的位置）：
(1) 板材的左下角和右上角坐标分别为),()0,0(H W 和，于是开始时剩余矩形数据集中只有一个矩形为)],(),0,0[(1H W R =。
(2) 当排入一个矩形件i （宽i w 高i h ）后，需将剩余矩形数据集合中的每一个矩形都减掉此矩形件所占的位置。
若此矩形件的左下角坐标为),(11i i y x ，且为横排（即矩形件不旋转90°），则每个剩余矩形都减掉与矩形件
)],(),,[(11111i i i i i i h y w x y x ++相交的部分。
例如矩形)],(),0,0[(1H W R =减掉与矩形件i 相交的部分后，形成了四个新的剩余矩形为：
)]
,(),,[()],(),0,0[(1111i i i i i i h y w x y x H W ++- )]},(),0,[()],,(),,0[()],,(),0,0[()],,(),0,0{[(1111H W w x H W h y H x y W i i i i i i ++= 按顺时针方向记录矩形。
如图4所示。
若为竖排（即矩形件旋转90°），计算方法类似。
图4 剩余矩形表示法
依此类推，将矩形数据集中的所有剩余矩形都作如此操作，减去所排入矩形件i 所占位置，形成新的剩余矩形。
(3) 由于新的剩余矩形的产生，又将引起原矩形数据集的改变，因此对其进行整理：去掉面积为零的或已无法排下所剩的任何一个矩形件的剩余矩形；把具有完全包含关系的剩余矩形中面积小的矩形去除、有相交关系的矩形全部保留。
得到新的剩余矩形集，为下一次排放使用。
用剩余矩形表示法可记录每个可形成最大矩形的空间，用于排样。
将这种表示法与BL 排样算法结合，就形成了剩余矩形排样算法，对于给定的一个排样方案},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，具体排样过程如下：
(1) 开始时剩余矩形集S 中仅有一个矩形，即板材本身)],(),0,0[(1H W R =。
(2) 从排列P 中取出第一个需排的矩形件1p （宽1p w ，高1p h ），将1p 根据相应排放方式 1r 排放在板材的左下角，用上面所述的剩余矩形表示法计算新的板材剩余矩形集},{21R R S =：
若01=r （横排），则)],(),0,[(11H W w R p =，)],(),,0[(12H W h R p =，如图5； 若11=r （竖排），则)],(),0,[(11H W h R p =，)],(),,0[(12H W w R p =。
图5 剩余矩形排样过程
(3) 依此类推，按顺序逐一排放),,2(n i p i ，直至所有矩形排放完毕。
每放入一矩形件，都需根据剩余矩形集确定其排放位置，即在剩余矩形集中选择宽高均大于等于此矩形件的底部最低的最靠左的剩余矩形（先靠下后靠左），让矩形件与剩余矩形的左下角重叠。
同时放入矩形后要对剩余矩形集进行整理更新。
同样，剩余矩形排样算法也满足BL 条件。
我们的问题叙述如下：
现在有宽为15、高为充分大的板材(即板材的高度没有限制)，将表1中的25块矩形安排到板材上有下列3种排样方案：
(1)P=(4,2,1,3,6,5,7,9,8,10,11,12,14,13,19,15,18,17,20,16,21,22,24,23,25); R=(1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1); 具体排样图见图6.
(2)P=(10,5,1,13,23,24,22,8,14,4,7,25,11,19,6,2,16,20,18,9,17,3,12,15,21); R=( 0,1,1, 1, 0, 1, 1,0, 1,1,1, 0, 0, 1,1,1, 0, 1, 0,0, 0,1, 1, 0, 0); 具体排样图见图7.
(3) P=(23,21,20,16,17,2,24,25,9,3,5,8,22,14,15,18,7,6,10,19,4,12,11,13,1); R=( 0, 0, 1, 0, 1,1, 0, 0,0,1,0,1, 0, 0, 0, 1,0,1, 1, 0,1, 0, 1, 0,0); 具体排样图未给出，由参赛同学编制相应程序绘制。
现在的问题是，请学生根据剩余矩形排样算法编制一个通用的程序仿照图6、图7绘制上述3种排样方案的图形（由程序自动绘制，不是手工绘制）。
使用语言不限，最后成果需提交程序清单、可执行程序、程序使用说明以及由程序绘制
的三张排样图。
图6 问题(1)的排样图图7 问题(2)的排样图。
