矩形件排樣最優(yōu)化問題求解

張青　劉芳

摘 要： 為了解決大型婚紗沖印公司人工排版效率低，排版利用率差的問題，提出一種矩形件排樣最優(yōu)化的解決思路，即基于專家模板的照片自動排版方法。經(jīng)過某公司半年測試，其方法排版利用率高于人工排版4.3個(gè)百分點(diǎn)，工作效率則實(shí)現(xiàn)數(shù)量級的提升。

關(guān)鍵詞： 矩形件排樣； 自動排版； 婚紗沖?。?排版利用率

中圖分類號： TN081?34 文獻(xiàn)標(biāo)識碼： 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 引 言

矩形件優(yōu)化排樣問題廣泛地出現(xiàn)于輕工、家具、造紙及玻璃切割等行業(yè)，它將許多小矩形件盡可能多地、無重疊地排放到一個(gè)定寬、定長的矩形板材上，使其利用率達(dá)到最大[1]。矩形件優(yōu)化排樣是一個(gè)經(jīng)典的NP（Nondeterministic Problem）完全問題，以目前的計(jì)算理論和算法；要么根本無法求解，要么求解的過程需要的時(shí)間和費(fèi)用無法接受；因此，目前的研究都在求其有效近似最優(yōu)解。隨著對排樣問題的深入研究，這些算法可大致分為兩類：一類是啟發(fā)式算法[2?3]，例如背包算法、基于占穴思想的啟發(fā)式算法；另一類算法主要是利用現(xiàn)代智能算法，例如遺傳算法、模擬退火算法[4]、蟻群算法等。

以上這些算法在矩形件的排樣上都取得了較好的效果，但是也都存在效果不佳的實(shí)例，尤其是應(yīng)用于照片排版時(shí)，更是有不足之處。為此本文提出基于專家模板的矩形件排樣最優(yōu)化的解決算法。

1 照片自動排版問題分析

對照片版面進(jìn)行排版屬于矩形件優(yōu)化排樣問題，傳統(tǒng)算法用于照片排版時(shí)，更是有不足之處。和多數(shù)其他行業(yè)的矩形件優(yōu)化排樣問題不同，照片排版問題有很多特殊的難題。其中，多數(shù)其他行業(yè)的矩形件優(yōu)化排樣問題中，大尺寸矩形件很少，絕大部分矩形件都很小，如果出現(xiàn)大的縫隙，則可以隨意用小矩形件填充，因此，排版利用率比較容易得到保證。但照片排版問題中，存在大量的用少數(shù)幾張就能排滿母版的大尺寸照片，而且小尺寸照片數(shù)量通常不足，利用經(jīng)典的矩形件排樣算法，很容易出現(xiàn)小尺寸照片很快用盡，后面排入的版面缺乏足夠多小尺寸照片填充縫隙，而導(dǎo)致總體利用率大幅度降低。因此，使用傳統(tǒng)算法進(jìn)行照片自動排版的排版利用率都很難達(dá)到專家排版的水平。

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

本算法提供一種利用專家經(jīng)驗(yàn)進(jìn)行照片自動排版的方法，可以有效改善排版利用率，達(dá)到或者超過專家排版的水平。

在排版之前，通過機(jī)器學(xué)習(xí)方法[5]，把專家常用的一些排版結(jié)果自動轉(zhuǎn)化為系統(tǒng)模板。

2.1 主算法

自動排版過程如下：

步驟1：將所有待排版的照片添加至系統(tǒng)。

步驟2：選擇一個(gè)未標(biāo)記為完成的模板，如果所有模板都被標(biāo)記為完成，則結(jié)束整個(gè)排版過程。

步驟3：用同尺寸的未排照片替換模板上的所有照片，如果成功，則輸出一個(gè)排版結(jié)果，并且回到步驟3，直到缺乏某個(gè)尺寸照片而無法成功全部替換模板照片為止。

步驟4：用同尺寸的未排照片替換模板上的所有可替換的照片，如果無法替換任何照片，則把模板標(biāo)記為完成，返回步驟2，如果能得到一個(gè)部分成功的排版結(jié)果a，這個(gè)排版結(jié)果上有若干未替換照片，針對這些未替換照片使用子方法A，獲得所有的包絡(luò)矩形集合q，然后選擇一個(gè)包絡(luò)矩形使用子方法B，執(zhí)行方法B之前先把包絡(luò)矩形內(nèi)已經(jīng)替換的照片從部分排版結(jié)果a中移除，如果方法B失敗（返回不包含任何照片的空的排版結(jié)果）則把模板標(biāo)記為完成并返回步驟2，如果方法B得到一個(gè)填充滿包絡(luò)矩形的照片子排版結(jié)果b，把這個(gè)子排版結(jié)果b和部分排版結(jié)果a合并，得到一個(gè)排版結(jié)果并輸出。回到步驟4。算法流程圖如圖1所示。

2.2 子方法A

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

（2） 計(jì)算二元組集合e=c*c，其中“*”為集合的笛卡兒乘積運(yùn)算。計(jì)算二元組集合f=d*d，其中“*”為集合的笛卡兒乘積運(yùn)算。

（3） 計(jì)算四元組集合k=e*f，其中“*”為集合的笛卡兒乘積運(yùn)算。

（4） 對k集合中的每一個(gè)四元組（v1，v2，h1，h2），v1，v2是兩條來自集合c的垂直直線，h1，h2是來自集合d的水平直線，如果v1，v2，h1，h2能夠組成一個(gè)面積大于0的矩形，并且這個(gè)矩形不和排版結(jié)果a中的任何照片部分相交（要么完全包含照片，要么不和照片相交），則把這個(gè)矩形放入集合q中。endprint

（5） 集合q就是子方法A的結(jié)果包絡(luò)矩形集合。

2.3 子方法B（剩余矩形遞歸排版方法）

輸入目標(biāo)矩形rt：

（1） 選擇一個(gè)能夠完全包含在矩形rt中的尺寸最大的未排照片pm，放置到矩形rt的左上角。如果沒有未排照片能放入rt，則結(jié)束本次子方法B，把空的排版方案（不包含任何照片）返回給調(diào)用者。

（2） 計(jì)算利用率：

s=[pm面積rt面積]

如果s>smin，則成功結(jié)束子方法B的本次遞歸，把照片pm作為排版方案返回給調(diào)用者。其中smin為最小可接受的利用率閾值。

（3） 用pm的下邊界所在直線把矩形rt除去pm的部分切割為上下兩個(gè)剩余矩形，分別為矩形lr1和矩形lr2，分別針對lr1和lr2使用子方法B進(jìn)行排版，分別得到子排版方案rlr1和子排版方案rlr2（rlr1和rlr2都有可能為空的排版方案），把rlr1，rlr2和pm合并，得到本次排版方案r，計(jì)算利用率為：

s=[排入r的照片面積總和rt面積]

如果s>smin，則成功結(jié)束子方法B的本次遞歸，把照片pm作為排版方案返回給調(diào)用者。

（4） 用pm的右邊界所在直線把矩形rt除去pm的部分切割為左右兩個(gè)剩余矩形，分別為矩形lr3和矩形lr4，分別針對lr3和lr4使用子方法B進(jìn)行排版，分別得到子排版方案rlr3和子排版方案rlr4，把rlr3，rlr4和pm合并，得到本次排版方案r，計(jì)算利用率為：

s=[排入r的照片面積總和rt面積]

如果s>smin，則成功結(jié)束子方法B的本次遞歸，把照片pm作為排版方案返回給調(diào)用者。如果s

3 結(jié) 語

由于優(yōu)化排樣是一個(gè)經(jīng)典的NP完全問題，照片組合空間巨大，不論是啟發(fā)式還是智能搜索算法，均只能在合理時(shí)間內(nèi)搜索可能的排版結(jié)果中的很小一部分。實(shí)踐證明，在照片自動排版直接使用這些方法會漏掉很多排版專家發(fā)現(xiàn)的優(yōu)秀的排版方案，導(dǎo)致排版利用率顯著低于人工排版，且排版利用率不穩(wěn)定，常常會得到排版利用率非常低的結(jié)果。

本算法使用專家模板進(jìn)行自動排版，并且能夠自動地靈活修改專家模板的局部，使得模板可以被充分利用，從而實(shí)現(xiàn)排版利用率穩(wěn)定地達(dá)到或者高于專家排版。采用本算法的照片自動排版軟件已研發(fā)出來，已在國內(nèi)大型連鎖婚紗公司進(jìn)行為期半年試用，從試用的結(jié)果來看，采用基于專家模板的自動排版算法的相紙的利用率高于人工4.3個(gè)百分點(diǎn)（人工排版平均相紙利用率為94.2，本算法為98.5%），同時(shí)提高了排版的效率，自動排版軟件的30 min的產(chǎn)能，大于人工一個(gè)工作日的產(chǎn)能，實(shí)證了本算法可靠、高效。通過調(diào)整一些約束條件[6]，基于專家模板的自動排版算法還可在板材加工、服裝制版、玻璃切割、工程圖紙打印廣泛應(yīng)用，具有較好的應(yīng)用前景。

參考文獻(xiàn)

[1] 李治江，崔廣勛，王嵩.基于矩形Packing問題求解的頁面自動排版方法[J].山東農(nóng)業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），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ìn)的啟發(fā)式自動排版算法及其應(yīng)用[J].中山大學(xué)學(xué)報(bào)（自然科學(xué)版），2003（2）：256?258.

[4] 唐立山.非數(shù)值并行算法第一部：模擬退火算法[M].北京：科學(xué)出版社，2000.

[5] 劉弘，曾廣周，林宗楷.具有類比學(xué)習(xí)機(jī)制的優(yōu)化排料系統(tǒng)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1997，9（5）：21?27.

[6] 王金敏，馬豐鳴，陳東祥，等.一種基于約束的布局求解算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，1998，10（2）：150?160.