黃 河，許 超

（東南大學(xué) 機(jī)械工程學(xué)院，江蘇 南京211100）

0 引言

矩形件排樣的優(yōu)化問(wèn)題，是將一定數(shù)量的矩形件盡可能多地、無(wú)重疊地排放到—個(gè)定寬、定長(zhǎng)（或無(wú)限長(zhǎng)）的矩形板材上，使其利用率達(dá)到最大。矩形件排樣問(wèn)題，廣泛存在于鈑金下料、玻璃切割、電路布局、報(bào)刊排版等工業(yè)生產(chǎn)中。隨著社會(huì)生產(chǎn)力的不斷提高，生產(chǎn)規(guī)模不斷擴(kuò)大，原材料的消耗量也越來(lái)越大，提高原材料利用率在實(shí)際生產(chǎn)中顯得越來(lái)越重要[1-2]。為此，國(guó)內(nèi)外眾多學(xué)者在排樣領(lǐng)域提出了許多有效的算法。其中啟發(fā)式算法主要有BL 算法、最低水平線(xiàn)算法、Best-Fit 算法等；由于單一的啟發(fā)式定位規(guī)則難以實(shí)現(xiàn)全局優(yōu)化，許多學(xué)者將啟發(fā)式算法與智能算法（遺傳算法、螞蟻算法等）相結(jié)合尋求全局最優(yōu)解并取得了一些成果，如文獻(xiàn)[2]中將最低水平線(xiàn)搜索加上遺傳算法等。然而，當(dāng)排樣規(guī)模較大時(shí)這些算法十分耗時(shí)，影響實(shí)際生產(chǎn)效率。因此，尋求一種簡(jiǎn)單快速并在一定程度上可優(yōu)化排樣結(jié)果的啟發(fā)式算法具有重要應(yīng)用價(jià)值。研究表明，最低水平線(xiàn)算法是一種頗具潛力的啟發(fā)式算法，至今已有許多派生算法，如最低輪廓線(xiàn)搜索算法、旋轉(zhuǎn)最低水平線(xiàn)算法等。本文在分析上述算法的不足的基礎(chǔ)上提出基于優(yōu)先度的改進(jìn)最低水平線(xiàn)算法，可以有效改善最低水平線(xiàn)算法的排樣結(jié)果。

1 當(dāng)前最低水平線(xiàn)算法及其分析

1.1 最低水平線(xiàn)算法基本思想

原始最低水平線(xiàn)算法的基本排樣步驟如下[2]：

（1）設(shè)初始最高輪廓線(xiàn)為板材最下面的邊。

（2）每當(dāng)排入一個(gè)零件就在最高輪廓線(xiàn)集中選取最低的一段水平線(xiàn)。如有數(shù)段，則選取最左邊的一段，測(cè)試該段線(xiàn)的寬度是否大于或者等于要排零件的寬度：①如果該段線(xiàn)的寬度大于要排零件的寬度，則將該零件在此位置排放，同時(shí)更新零件的最高輪廓線(xiàn)；②否則，查詢(xún)最低水平線(xiàn)段相鄰的左、右兩段水平線(xiàn)，將最低水平線(xiàn)提升至與之相鄰且高度較低的一段平齊，更新零件最高輪廓線(xiàn)。

（3）重復(fù)第（2）步，直至能排入該零件。

（4）重復(fù)上述過(guò)程，直至所有零件排放完畢。

從排樣過(guò)程不難看出，原始的最低水平線(xiàn)算法沒(méi)有定義零件的排入順序。由于對(duì)零件的搜索極具盲目性，即使給定了零件順序（如寬度遞減排入），其排樣結(jié)果依然欠佳。

圖1 是按寬度遞減順序應(yīng)用最低水平線(xiàn)算法的模擬排樣過(guò)程，容易看出由于2 號(hào)零件寬度大于最低水平線(xiàn)寬度，使得最低水平線(xiàn)更新至1 號(hào)零件上輪廓。而實(shí)際更優(yōu)的排樣方案應(yīng)該是將3 號(hào)零件排入當(dāng)前最低水平線(xiàn)以避免板材右側(cè)區(qū)域浪費(fèi)。

圖1 最低水平線(xiàn)算法的排樣實(shí)例

1.2 已有的改進(jìn)算法及其分析

許多學(xué)者針對(duì)最低水平線(xiàn)算法的不足做出了不同程度地改進(jìn)，這里選取比較有代表性的一種改進(jìn)算法進(jìn)行分析。

文獻(xiàn)[3]中提到了最低水平線(xiàn)旋轉(zhuǎn)搜索法。該算法對(duì)原始算法做出了兩點(diǎn)關(guān)鍵改動(dòng)：引入了搜索和旋轉(zhuǎn)。其具體做法是：若當(dāng)前零件寬度大于最低水平線(xiàn)寬度，并不立即提升最低水平線(xiàn)，而是將零件旋轉(zhuǎn)90°后再次判斷其寬度是否小于最低水平線(xiàn)，若此時(shí)零件寬度仍大于最低水平線(xiàn)寬度則向后搜索其他零件；重復(fù)上述步驟，直至有合適的零件排入；只有當(dāng)按上述步驟遍歷所有零件仍無(wú)法排入時(shí)才提升最低水平線(xiàn)。從圖2 可以看出該算法的排樣效果較原始算法有一定的提升。

圖2 改進(jìn)前后排樣結(jié)果對(duì)比

最低水平線(xiàn)旋轉(zhuǎn)搜索算法雖然擴(kuò)大了每次排樣的零件搜索范圍，一定程度上避免了因盲目提升最低水平線(xiàn)造成的板材區(qū)域浪費(fèi)。但是這種搜索方法過(guò)于單一，僅僅只是為了找到待排零件隊(duì)列中首個(gè)能夠排入當(dāng)前最低水平線(xiàn)的零件，而不是尋找一個(gè)排入后能對(duì)全局優(yōu)化目標(biāo)貢獻(xiàn)最大的零件。換句話(huà)說(shuō)，該搜索算法難以找到“最適合”排入當(dāng)前最低水平線(xiàn)的零件。通過(guò)圖3 的例子可以清楚地說(shuō)明這一問(wèn)題。

上述例子中，在第二次排入時(shí)，最低水平線(xiàn)旋轉(zhuǎn)搜索算法首先發(fā)現(xiàn)2 號(hào)零件旋轉(zhuǎn)后可以排入最低水平線(xiàn)，因此忽略了更適合排入當(dāng)前最低水平線(xiàn)的3 號(hào)零件，導(dǎo)致排樣圖出現(xiàn)圖示的“高塔”，不僅浪費(fèi)了右側(cè)板材區(qū)域，而且不利于板材的后續(xù)利用。

圖3 最低水平線(xiàn)旋轉(zhuǎn)搜索算法缺陷示例

經(jīng)過(guò)以上分析，為了使排樣結(jié)果更趨近全局最優(yōu)解，必須尋找一種更加有效的搜索規(guī)則，使得基于該規(guī)則的每一次排入都能達(dá)到局部最優(yōu)，并且盡可能地使后續(xù)排樣過(guò)程朝著最優(yōu)方向發(fā)展。

2 基于優(yōu)先度的最低水平線(xiàn)改進(jìn)算法設(shè)計(jì)

2.1 優(yōu)先度函數(shù)的設(shè)計(jì)

基于優(yōu)先度的搜索規(guī)則實(shí)際上與現(xiàn)實(shí)生活中高考錄取規(guī)則十分相似。高校以考生的各科總成績(jī)這個(gè)綜合量化指標(biāo)來(lái)?yè)駜?yōu)錄??；同樣的，每一次的排樣過(guò)程也是一個(gè)“擇優(yōu)”過(guò)程，當(dāng)前最低水平線(xiàn)（好比高校），通過(guò)優(yōu)先度（好比總成績(jī)）這一量化指標(biāo)來(lái)尋找零件隊(duì)列中最適合排入的對(duì)象?？偝煽?jī)包含一些所占比重不同的科目，同理，優(yōu)先度也由一些權(quán)重不同的影響因子構(gòu)成。

（1）主影響因子f1

考慮到排樣的核心目標(biāo)是提高板材利用率，減少材料浪費(fèi)，結(jié)合最低水平線(xiàn)算法的特點(diǎn)，將零件的排入寬度（零件排入時(shí)的水平尺寸）與當(dāng)前最低水平線(xiàn)的匹配程度作為主要影響因子f1，其表達(dá)式如下：

式中：Wline——最低水平線(xiàn)寬度；

Wpart）——零件排入寬度。

f1的值越小說(shuō)明當(dāng)前最低水平線(xiàn)的利用率越高，本次排樣造成板材浪費(fèi)的可能性越小。搜索過(guò)程會(huì)自動(dòng)篩選排入寬度小于最低水平線(xiàn)寬度的零件，因此f1的取值范圍是[0，1]。

（2）次影響因子f2

每次排樣時(shí)，除了追求局部利用率的最大化，還應(yīng)顧全后續(xù)的排樣過(guò)程以及余料的利用，盡可能地使現(xiàn)有的排樣圖邊界整齊，避免出現(xiàn)高度差過(guò)大的“臺(tái)階”。本文采取控制零件寬長(zhǎng)比的方法確保形狀接近方形的零件優(yōu)先排入，為此設(shè)計(jì)f2的表達(dá)式如下：

式中：ratio——零件寬長(zhǎng)比，即零件的較大尺寸/零件較小尺寸。

f2的取值越小說(shuō)明零件寬長(zhǎng)比越小，形狀越接近方形。由于ratio 不小于1，故f2的取值范圍是[0.5，1]。

（3）次影響因子的權(quán)重系數(shù)

若直接取f1與f2的和作為優(yōu)先度函數(shù)，則當(dāng)f1取值接近于0 時(shí)，f2的值將顯著影響優(yōu)先度函數(shù)的取值，這會(huì)造成一些不好的排樣結(jié)果。如圖4 中的例子，當(dāng)前最低水平線(xiàn)寬度為20，現(xiàn)有待排零件3、4，它們的尺寸分別為20×100 和15×15，若取f1+f2的值作為優(yōu)先度函數(shù)值，則經(jīng)過(guò)計(jì)算后發(fā)現(xiàn)4 號(hào)零件的計(jì)算值要小于3 號(hào)，即4 號(hào)零件優(yōu)先于3 號(hào)零件排入，這顯然是不合理的。

圖4 特定情況下的缺陷示例

為此，需要為次影響因子添加一個(gè)系數(shù)，使得當(dāng)主影響因子f1取值較小時(shí)，次影響因子f2的影響力得到控制。經(jīng)過(guò)反復(fù)試驗(yàn)推導(dǎo)，采用如下表達(dá)式作為次影響因子權(quán)重系數(shù)，記為ε。

不難看出ε 的取值范圍是[0.2，1.1]，且單調(diào)遞增，當(dāng)f1取值接近0 時(shí)，次影響因子受到了有效的約束。總結(jié)上述分析可最終確定優(yōu)先度函數(shù)F 的表達(dá)式如下：

利用公式（4）重新計(jì)算圖4 中兩個(gè)待排零件的優(yōu)先度值，發(fā)現(xiàn)此時(shí)3 號(hào)零件的計(jì)算值小于4 號(hào)零件，使排樣結(jié)果得到了優(yōu)化。

需要說(shuō)明的一點(diǎn)是，此處優(yōu)先度函數(shù)F 的取值越小代表零件在隊(duì)列中優(yōu)先度越高，并不是F 取值越大優(yōu)先度越高。

2.2 算法的基本思路

排樣之前，首先將所有待排零件調(diào)整至橫放狀態(tài)（即水平尺寸大于等于豎直尺寸），并按照水平尺寸（寬度）遞減的順序組成待排零件隊(duì)列。對(duì)于寬度為L(zhǎng) 的當(dāng)前最低水平線(xiàn)，首先剔除零件隊(duì)列中寬度與高度均大于L 的零件，若剩余零件個(gè)數(shù)為0，則更新最低水平線(xiàn)至與其相鄰的較低水平線(xiàn)，重復(fù)上述操作；若剩余零件個(gè)數(shù)不為0，則在剩下的零件中，令Wi為第i（i=0，1，2…n）個(gè)零件的排入寬度，mark為已計(jì)算零件中最優(yōu)零件標(biāo)記，F(xiàn)min為已計(jì)算零件中F 最小值，rotate 為旋轉(zhuǎn)標(biāo)志，單次排樣流程如圖5所示。一個(gè)完整的排樣過(guò)程就是重復(fù)執(zhí)行單次排樣操作，直至所有零件均已排入，或板材已耗盡，最終輸出排樣圖。

圖5 單次排樣流程圖

3 實(shí)例計(jì)算

作者在VisualStudio2003 開(kāi)發(fā)環(huán)境中用C++語(yǔ)言編寫(xiě)了基于優(yōu)先度的改進(jìn)最低水平線(xiàn)算法以及最低水平線(xiàn)旋轉(zhuǎn)搜索算法的程序，將文獻(xiàn)[5]中的部分實(shí)驗(yàn)用例在PC 機(jī)進(jìn)行了仿真，并對(duì)比了實(shí)驗(yàn)結(jié)果。每組實(shí)驗(yàn)采用的是寬度一定高度不限的板材，用排樣高度來(lái)表征板材利用率。表1 列出了實(shí)驗(yàn)所用數(shù)據(jù)，表2、表3 是實(shí)驗(yàn)結(jié)果對(duì)比。

表1 所用的實(shí)驗(yàn)數(shù)據(jù)

表2 兩最低水平線(xiàn)改進(jìn)算法的排樣高度比較

表3 兩種最低水平線(xiàn)改進(jìn)算法的排樣時(shí)間比較

對(duì)比表2 中的數(shù)據(jù)發(fā)現(xiàn)，對(duì)于所選實(shí)驗(yàn)用例，本文改進(jìn)算法的排樣利用率要優(yōu)于最低水平線(xiàn)旋轉(zhuǎn)搜索算法，排樣時(shí)間雖然略有加長(zhǎng)，但在可接受范圍內(nèi)。部分排樣結(jié)果如圖6 所示。

4 結(jié)論

本文在分析原始最低水平線(xiàn)算法及其派生算法不足的基礎(chǔ)上引入優(yōu)先度的概念，利用優(yōu)先度函數(shù)來(lái)提高零件搜索的精確性，一定程度上克服了現(xiàn)有最低水平線(xiàn)算法搜索過(guò)程的盲目性，優(yōu)化了排樣結(jié)果。實(shí)驗(yàn)結(jié)果表明，本文的改進(jìn)算法在利用率方面相比現(xiàn)有最低水平線(xiàn)算法有了一定提高；與當(dāng)前主流的啟發(fā)式加智能算法的綜合排樣算法相比，利用率雖并無(wú)優(yōu)勢(shì)，但計(jì)算時(shí)間大大減少。

綜合來(lái)看，本文算法能不依賴(lài)智能算法而取得較接近最優(yōu)解的排樣結(jié)果，具有較強(qiáng)的實(shí)用性。

圖6 排樣結(jié)果實(shí)例

[1]陳仕軍，曹 炬.矩形件優(yōu)化排樣的一種啟發(fā)式算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（12）：230-232.

[2]趙曉東.矩形件優(yōu)化排樣算法的研究與實(shí)現(xiàn)[D].大連：大連交通大學(xué)，2008.

[3]李 捷.一種矩形件布局問(wèn)題的求解方法[J].科技廣場(chǎng)，2008，（1）：22-24.

[4]楊傳華，吳錦文，等.定序列矩形件優(yōu)化排樣的二維搜索算法[J].佳木斯 大 學(xué) 學(xué) 報(bào)，2010，28（3）：354?356.

[5]Hopper E，Turton B.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.

[6]Ender O¨zcan, Zhang Kai,John H.Drake Bidirectional best -fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing [J].Expert Systems with Applica tions ,2013 (40):4035-4043.

[7]王竹婷，劉 林，等.改進(jìn)的最低水平線(xiàn)搜索算法求解矩形排樣問(wèn)題[J].工程設(shè)計(jì)學(xué)報(bào)，2009，16（2）：98?102.

[8]賈志欣，李紅林，等.異形件排樣的綜合優(yōu)化算法[J].鍛壓裝備與制造技術(shù)，2004，39（1）：59-61.

[9]李 勇，曹 矩，等.矩形件排樣優(yōu)化的十字線(xiàn)法[J].鍛壓裝備與制造技術(shù)，2004，39（6）：98-99.