矩形件排样最优化问题求解

张青　刘芳

摘 要： 为了解决大型婚纱冲印公司人工排版效率低，排版利用率差的问题，提出一种矩形件排样最优化的解决思路，即基于专家模板的照片自动排版方法。经过某公司半年测试，其方法排版利用率高于人工排版4.3个百分点，工作效率则实现数量级的提升。

关键词： 矩形件排样； 自动排版； 婚纱冲印； 排版利用率

中图分类号： TN081?34 文献标识码： A 文章编号： 1004?373X（2017）22?0072?03

Abstract： 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 typesetting 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 efficiency has been increased by some orders of magnitude.

Keywords： rectangular piece layout； automatic typesetting； wedding dress developing； typesetting utilization rate

0 引 言

矩形件优化排样问题广泛地出现于轻工、家具、造纸及玻璃切割等行业，它将许多小矩形件尽可能多地、无重叠地排放到一个定宽、定长的矩形板材上，使其利用率达到最大[1]。矩形件优化排样是一个经典的NP（Nondeterministic Problem）完全问题，以目前的计算理论和算法；要么根本无法求解，要么求解的过程需要的时间和费用无法接受；因此，目前的研究都在求其有效近似最优解。随着对排样问题的深入研究，这些算法可大致分为两类：一类是启发式算法[2?3]，例如背包算法、基于占穴思想的启发式算法；另一类算法主要是利用现代智能算法，例如遗传算法、模拟退火算法[4]、蚁群算法等。

以上这些算法在矩形件的排样上都取得了较好的效果，但是也都存在效果不佳的实例，尤其是应用于照片排版时，更是有不足之处。为此本文提出基于专家模板的矩形件排样最优化的解决算法。

1 照片自动排版问题分析

对照片版面进行排版属于矩形件优化排样问题，传统算法用于照片排版时，更是有不足之处。和多数其他行业的矩形件优化排样问题不同，照片排版问题有很多特殊的难题。其中，多数其他行业的矩形件优化排样问题中，大尺寸矩形件很少，绝大部分矩形件都很小，如果出现大的缝隙，则可以随意用小矩形件填充，因此，排版利用率比较容易得到保证。但照片排版问题中，存在大量的用少数几张就能排满母版的大尺寸照片，而且小尺寸照片数量通常不足，利用经典的矩形件排样算法，很容易出现小尺寸照片很快用尽，后面排入的版面缺乏足够多小尺寸照片填充缝隙，而导致总体利用率大幅度降低。因此，使用传统算法进行照片自动排版的排版利用率都很难达到专家排版的水平。

2 基于专家模板的排版算法

本算法提供一种利用专家经验进行照片自动排版的方法，可以有效改善排版利用率，达到或者超过专家排版的水平。

在排版之前，通过机器学习方法[5]，把专家常用的一些排版结果自动转化为系统模板。

2.1 主算法

自动排版过程如下：

步骤1：将所有待排版的照片添加至系统。

步骤2：选择一个未标记为完成的模板，如果所有模板都被标记为完成，则结束整个排版过程。

步骤3：用同尺寸的未排照片替换模板上的所有照片，如果成功，则输出一个排版结果，并且回到步骤3，直到缺乏某个尺寸照片而无法成功全部替换模板照片为止。

步骤4：用同尺寸的未排照片替换模板上的所有可替换的照片，如果无法替换任何照片，则把模板标记为完成，返回步骤2，如果能得到一个部分成功的排版结果a，这个排版结果上有若干未替换照片，针对这些未替换照片使用子方法A，获得所有的包络矩形集合q，然后选择一个包络矩形使用子方法B，执行方法B之前先把包络矩形内已经替换的照片从部分排版结果a中移除，如果方法B失败（返回不包含任何照片的空的排版结果）则把模板标记为完成并返回步骤2，如果方法B得到一个填充满包络矩形的照片子排版结果b，把这个子排版结果b和部分排版结果a合并，得到一个排版结果并输出。回到步骤4。算法流程图如图1所示。

2.2 子方法A

（1） 把所有未替换照片的左边界所在直线和右边界所在直线放入垂直直线集合c，把所有未替换照片的上边界所在直线和下边界所在直线放入水平直线集合d。

（2） 计算二元组集合e=c*c，其中“*”为集合的笛卡儿乘积运算。计算二元组集合f=d*d，其中“*”为集合的笛卡儿乘积运算。

（3） 计算四元组集合k=e*f，其中“*”为集合的笛卡儿乘积运算。

（4） 对k集合中的每一个四元组（v1，v2，h1，h2），v1，v2是两条来自集合c的垂直直线，h1，h2是来自集合d的水平直线，如果v1，v2，h1，h2能够组成一个面积大于0的矩形，并且这个矩形不和排版结果a中的任何照片部分相交（要么完全包含照片，要么不和照片相交），则把这个矩形放入集合q中。endprint

（5） 集合q就是子方法A的结果包络矩形集合。

2.3 子方法B（剩余矩形递归排版方法）

输入目标矩形rt：

（1） 选择一个能够完全包含在矩形rt中的尺寸最大的未排照片pm，放置到矩形rt的左上角。如果没有未排照片能放入rt，则结束本次子方法B，把空的排版方案（不包含任何照片）返回给调用者。

（2） 计算利用率：

s=[pm面积rt面积]

如果s>smin，则成功结束子方法B的本次递归，把照片pm作为排版方案返回给调用者。其中smin为最小可接受的利用率阈值。

（3） 用pm的下边界所在直线把矩形rt除去pm的部分切割为上下两个剩余矩形，分别为矩形lr1和矩形lr2，分别针对lr1和lr2使用子方法B进行排版，分别得到子排版方案rlr1和子排版方案rlr2（rlr1和rlr2都有可能为空的排版方案），把rlr1，rlr2和pm合并，得到本次排版方案r，计算利用率为：

s=[排入r的照片面积总和rt面积]

如果s>smin，则成功结束子方法B的本次递归，把照片pm作为排版方案返回给调用者。

（4） 用pm的右边界所在直线把矩形rt除去pm的部分切割为左右两个剩余矩形，分别为矩形lr3和矩形lr4，分别针对lr3和lr4使用子方法B进行排版，分别得到子排版方案rlr3和子排版方案rlr4，把rlr3，rlr4和pm合并，得到本次排版方案r，计算利用率为：

s=[排入r的照片面积总和rt面积]

如果s>smin，则成功结束子方法B的本次递归，把照片pm作为排版方案返回给调用者。如果s

3 结 语

由于优化排样是一个经典的NP完全问题，照片组合空间巨大，不论是启发式还是智能搜索算法，均只能在合理时间内搜索可能的排版结果中的很小一部分。實践证明，在照片自动排版直接使用这些方法会漏掉很多排版专家发现的优秀的排版方案，导致排版利用率显著低于人工排版，且排版利用率不稳定，常常会得到排版利用率非常低的结果。

本算法使用专家模板进行自动排版，并且能够自动地灵活修改专家模板的局部，使得模板可以被充分利用，从而实现排版利用率稳定地达到或者高于专家排版。采用本算法的照片自动排版软件已研发出来，已在国内大型连锁婚纱公司进行为期半年试用，从试用的结果来看，采用基于专家模板的自动排版算法的相纸的利用率高于人工4.3个百分点（人工排版平均相纸利用率为94.2，本算法为98.5%），同时提高了排版的效率，自动排版软件的30 min的产能，大于人工一个工作日的产能，实证了本算法可靠、高效。通过调整一些约束条件[6]，基于专家模板的自动排版算法还可在板材加工、服装制版、玻璃切割、工程图纸打印广泛应用，具有较好的应用前景。

参考文献

[1] 李治江，崔广勋，王嵩.基于矩形Packing问题求解的页面自动排版方法[J].山东农业大学学报（自然科学版），2016，47（2）：264?268.

[2] HOPPER E， TURTON B C H. An empirical investigation of meta?heuristic and heuristic algorithms for a 2D packing problem [J]. European journal of operational research， 2001， 128（1）： 34?57.

[3] 张雪芬，王栋，罗笑南.一种改进的启发式自动排版算法及其应用[J].中山大学学报（自然科学版），2003（2）：256?258.

[4] 唐立山.非数值并行算法第一部：模拟退火算法[M].北京：科学出版社，2000.

[5] 刘弘，曾广周，林宗楷.具有类比学习机制的优化排料系统[J].计算机辅助设计与图形学学报，1997，9（5）：21?27.

[6] 王金敏，马丰鸣，陈东祥，等.一种基于约束的布局求解算法[J].计算机辅助设计与图形学学报，1998，10（2）：150?160.