基于優(yōu)先度的改進(jìn)最低水平線排樣算法

黃 河，許 超

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

0 引言

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

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

1.1 最低水平線算法基本思想

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

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

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

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

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

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

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

圖1 最低水平線算法的排樣實例

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

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

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

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

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

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

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

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

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

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

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

（1）主影響因子f1

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

式中：Wline——最低水平線寬度；

Wpart）——零件排入寬度。

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

（2）次影響因子f2

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

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

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

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

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

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

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

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

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

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

2.2 算法的基本思路

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

圖5 單次排樣流程圖

3 實例計算

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

表1 所用的實驗數(shù)據(jù)

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

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

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

4 結(jié)論

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

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

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

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

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

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

[4]楊傳華，吳錦文，等.定序列矩形件優(yōu)化排樣的二維搜索算法[J].佳木斯 大 學(xué) 學(xué) 報，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)的最低水平線搜索算法求解矩形排樣問題[J].工程設(shè)計學(xué)報，2009，16（2）：98?102.

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

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