更新时间

（1）2022-10-6,13:00 更新内容：二维举行下料求解算法的相关参考文献

（2）2022-10-6,17:55 更新内容：问题一B题建立的数学模型和求解方案

（3）2022-10-7，11：00 更新内容：问题二B题建立的数学模型和求解方案

（4）2022-10-8,23:00 更新内容：MATLAB实现代码、提交文件，图片，补充的重要模型参考文献

1 题目

一、背景介绍

智能制造被“中国制造2025”列为主攻方向, 而个性化定制、更短的产品及系统生命周期、互联互通的服务模式等成为目前企业在智能制造转型中的主要竞争点。以离散行业中的产品为例，如电子器件、汽车、航空航天零部件等，这些产品均是依赖于机械设计、可分散加工、可灵活组装且同类产品款式极多。对于此类产品，客户可能提出的产品需求难以穷举、订单规模难以预测且产品质量要求极高。此时“个性化定制”的服务需求则要求企业具有高效快速的需求分析及产品设计能力、具有柔性且精益的生产流程、具有完整且精细的全流程生产管控能力。

方形件产品（也称板式类产品）是以板材为主要原片、通过平面加工后的几种板式配件装配而形成的一类产品。常见方形件产品制造企业，如3C(计算、通讯、消费电子)、板式家具、玻璃、钣金件等行业，多采用“多品种小批量”的个性化定制生产，由于企业订单数量庞大，生产组织通常采用“订单组批+批量生产+订单分拣”的模式，通过使用订单组批来实现批量切割，提高原材料的利用率，加工完成后再按不同客户订单进行分拣。

上述个性化定制生产模式中的订单组批与排样优化至关重要，订单组批是将不同订单组成若干批次,实现订单的批量化生产。在对小批量、多品种、大规模的订单进行组批生产时，如果组批批次太小，材料利用率低，生产效率低；如果组批批次太大，材料利用率会提高，但订单交货期得不到保证，订单分拣难度提高，生产效率降低，缓冲区容量不足而造成堵塞等，需要解决个性化与生产高效性之间的矛盾。

排样优化本质上一个下料问题（也称切割填充问题），优化的目的是合理规划方形件在板材上的布局，以减少下料过程中存在板材浪费，简化切割过程。此问题是一种计算复杂度很高的组合优化问题，也是运筹学中的一个重要分支。下料作为众多制造企业生产链中产品及零部件生产的第一道工序，消耗的材料和资源不容小视，如何提高材料利用率，降低原材料消耗，是企业减少资源和能源浪费，承担环境责任所要解决的关键问题。

二、问题描述

订单组批问题:在考虑订单交货期、设备产能负荷、仓储容量、材料利用率、生产效率、生产工艺约束等因素下,对生产订单进行组批优化。使具有相同材质、交货期相近、工艺相似的订单安排在同一个生产批次, 通过订单组批优化来保证交货期, 提高原材料的利用率，提高设备生产效率等。为便于统一处理数据和体现问题本质，本次赛题所有订单的交货期均相同，不做区分。批次的定义为完成若干订单全部任务且不含任何不完整订单任务的订单集合。

下料优化问题（也称排样优化问题）:根据同一生产批次内方形件的尺寸与数量,选择原片的规格和数量,进行下料排样优化,最大化板材原片利用率。依据切割工序的工艺要求,排样方案必须满足“一刀切”（也称齐头切，Guillotine cut)约束(任何一次直线切割都要保证板材可分离，换言之，每次直线切割使得板材分成两块)。下料优化问题属于具有“一刀切”约束的板型材方形件排样优化问题。

考虑切割工艺的方式不同，分齐头切（guillotine cut）和非齐头切（如图1），齐头切又可以细分精确方式和非精确方式（涉及到切割的阶段数，如图2）.图2中的三阶段排样方式主要有三种不同的类型：三阶段非精确(3NE)排样方式、三阶段匀质排样方式(3E)、三阶段同质排样方式(3H)。其中 3E 和 3H 排样方式可在三个阶段内切割出准确尺寸的方形件，因此都属于精确排样方式。3NE 排样方式中，部分方形件还需要额外的第四阶段切割才能得到满足规格尺寸要求。

编辑切换为居中

添加图片注释，不超过 140 字（可选）

(a)齐头切（guillotine cutting） （b）非齐头切（non-guillotine cutting）

图1 切割示意：(a)齐头切（guillotine cutting）和（b）非齐头切（non-guillotine cutting）

编辑切换为居中

添加图片注释，不超过 140 字（可选）

图2 三阶段排样方式

由于涉及到阶段数不同，不同文献对于切割每个阶段的称呼不一样，为了便于理解和统一表述形式，采用英文的方式形容关键阶段模块的描述，具体可参见图3（实际切割过程中，第一刀可能垂直于长边，也可能垂直于短边，图3以垂直于其中一条边为例）。

编辑切换为居中

添加图片注释，不超过 140 字（可选）

图3 不同切割阶段的形式定义

因为常见的阶段最多为3-4个，因此以3阶段的切割方式为例（如图3），第1阶段的横向切割生成模块称之为stripe（条带），如Stripe1和Strip2；第2阶段纵向切割生成模块称之为stack（栈），如Strip1继续被切割分成Stack1、Stack2和Stack3；第三阶段横向切割生成模块称之为item（产品项），如Stack1继续被切割分成Item1、Item2和Item3。

三、问题

本赛题由两个子问题组成，第二个子问题的约束都基于第一个子问题并与之相容，但两个子问题所提供的数据不相关。如果概念定义和过程描述与业界有所出入，皆以本赛题为准。本题假定：

1. 只考虑齐头切的切割方式（直线切割、切割方向垂直于板材一条边，并保证每次直线切割板材可分离成两块）；
2. 切割阶段数不超过3，同一个阶段切割方向相同；
3. 排样方式为精确排样；
4. 假定板材原片仅有一种规格且数量充足；
5. 排样方案不用考虑锯缝宽度（即切割的缝隙宽度）影响。

子问题1：排样优化问题。要求建立混合整数规划模型，在满足生产订单需求和相关约束条件下，尽可能减少板材用量。

约束：

1. 在相同栈（stack）里的产品项（item）的宽度（或长度）应该相同；
2. 最终切割生成的产品项是完整的，非拼接而成。

本子问题要求编程，以数据集A为输入，输出结果要求见第五部分。

子问题2：订单组批问题。要求建立混合整数规划模型，对数据集B中全部的订单进行组批，然后对每个批次进行独立排样，在满足订单需求和相关约束条件下，使得板材原片的用量尽可能少。

在满足子问题1约束的基础上进一步要求：

1. 每份订单当且仅当出现在一个批次中；

2. 每个批次中的相同材质的产品项（item）才能使用同一块板材原片进行排样；

3. 为保证加工环节快速流转，每个批次产品项（item）总数不能超过限定值；

4. 因工厂产能限制，每个批次产品项（item）的面积总和不能超过限定值；

本子题要求编程，以数据集B为输入，输出结果要求见第五部分。

四、输入数据说明

每套输入数据由两部分组成，一部分是输入参数（参见后文），另一部分是产品项（item）数据（需要另外下载），这里仅给出格式描述。

输入参数：

1. 单个批次产品项（item）总数上限 max_item_num = 1000

2. 单个批次产品项（item）的面积总和上限max_item_area = 250（m2）

3. 原片长度plate_length = 2440（mm）

4. 原片宽度plate_width = 1220 (mm)

产品项数据格式

数据集：

1. 数据集A；

2. 数据集B。

五、提交结果要求

参赛选手必须按比赛规则提交规定格式的论文报告。此外，本赛题还有如下要求：

建立完整的数学模型

1. 模型所用变量和参数都需要解释清楚。变量一般用单个小写英文字母表示；参数可以是希腊字母，也可以是第一个字母大写的英文字符串，但需要尽可能简洁；下标尽可能只用单个小写的英文字母表示。为简洁易读易懂起见，变量可以有上撇，上横等辅助记号；

2. 所有变量、参数和记号都必须通篇前后一致。

根据模型设计求解算法

1. 模型和算法是两个独立的概念。提交的论文必须对数学模型的特点进行分析，包括模型的规模和结构，求解的难易，等等；

2. 算法必须针对数学模型的特点设计。论文需要解释算法的合理性，包括算法实现的难易，复杂度估计和运行时间分析。如果采用实用性算法，必须解释算法的思路；

3. 模型算法描述必须逻辑严谨，条理清晰，同时简单易懂。

编写程序算法，并使用给定数据进行求解

1. 程序编写可以按自己的专长选用高级语言或脚本语言，或多种方法的组合，求解器可以是商用、开源、自主开发，由参赛者根据自己的情况选择。

2. 程序必须模块化，结构要面向目标，注释清晰；

3. 参赛选手需要在报告附录中介绍程序和数据结构。

论文报告必须明确包括如下数据以及排样方案效果图（如果两个排样方案相同，只需增加一个数量说明即可），同时欢迎作者采用其它图表形式对实验结果进行描述，但要求设计简单易懂，线条清晰，色彩分明，重点突出，标注恰到好处。

【注】：板材利用率 = 产品项面积之和 / 使用原片面积之和

本赛题还需提交程序实现的计算结果，及如下两个文本文件：。

1. 排版方案：以原片左底点位坐标原点，以坐标系形式描述产品项的位置分布，还原排版方案，用文件名“cut_program.csv”提交，输出结果数据格式如下：

2. 组批方案：输出组批结果（包含每个批次的排版方案），在产品项数据的基础上增加一列批次号属性，用文件名“sum_order.csv”提交，输出结果数据格式如下：

参考文献

1. Silva E, Alvelos F, Valério de Carvalho J M. An integer programming model for two-and three-stage two-dimensional cutting stock problems [J]. European Journal of Operational Research, 2010, 205(3): 699-708.

2. Cui Y D, Huang B X. Reducing the number of cuts in generating three-staged cutting patterns [J]. European Journal of Operational Research, 2012, 218: 358-365.

3. Puchinger J, Raidl G R. Models and algorithms for three-stage two-dimensional bin packing [J]. European Journal of Operational Research, 2007, 183(3): 1304-1327.

2 分析

（1）分析角度一：二维装箱问题
二维装箱问题。将若干个矩形物品装进矩形箱子中，并且在装箱的过程中不允许将矩形物品斜着放，即平行于横坐标。一般来说求解的目标是最小化箱子的箱子数目或者是箱子空间占用率。

当该算法适用于矩阵存储时，求解的最优目标是箱子的最大化空间占用率。以下即是求解的过程

装箱算法参考【A Thousand Ways to Pack the Bin – A Practical Approach to Two-Dimensional Rectangle Bin Packing】

以下我将会介绍其中一种叫Bottom-Left装箱算法。算法过程就是，矩形从箱子的右上角开始进入，先尽可能向下移动，再向左移动，一直循环，直至不再移动。在以下算法过程中，以0-1背包问题的思路去实现，即某个矩形装进箱子，则flag相应为1，未装进的flag为0。输出单个箱子占用率。

完整算法及实现介绍参考文章
【实现二维装箱Bottom-Left算法及用人工蜂群算法改进-Left算法及可视化】
https://zhuanlan.zhihu.com/p/494294824

（2）分析角度二：三阶段二维剪切问题
参考《考虑余料价值的三阶段二维剪切下料算法-陈秋莲》

相关参考文献
1、《同尺寸矩形毛坯排样的连分数分支定界算法_崔耀东》
2、《矩形三阶段带排样问题的遗传算法的研究_严玄》
3、《矩形件三阶段带排样问题的遗传算法_刘睿》
4、《A Heuristic for the 3-staged 2D Cutting Stock Problem with Usable Leftover》
5、《Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation 》

3 方案设计

（1）建立一个二维装箱问题的整数最优化模型

（2）问题二：在问题一的基础上增加约束条件，求解最优化模型

4 完整文档和代码实现

从知乎下单，转到知乎文章的最下方
2022年华为杯B题代码实现