基于優先度的改進最低水平線排樣算法

黃 河，許 超

（東南大學 機械工程學院，江蘇 南京211100）

0 引言

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

1 當前最低水平線算法及其分析

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

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

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

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

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

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

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

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

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

1.2 已有的改進算法及其分析

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

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

圖2 改進前后排樣結果對比

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

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

圖3 最低水平線旋轉搜索算法缺陷示例

經過以上分析，為了使排樣結果更趨近全局最優解，必須尋找一種更加有效的搜索規則，使得基于該規則的每一次排入都能達到局部最優，并且盡可能地使后續排樣過程朝著最優方向發展。

2 基于優先度的最低水平線改進算法設計

2.1 優先度函數的設計

基于優先度的搜索規則實際上與現實生活中高考錄取規則十分相似。高校以考生的各科總成績這個綜合量化指標來擇優錄取；同樣的，每一次的排樣過程也是一個“擇優”過程，當前最低水平線（好比高校），通過優先度（好比總成績）這一量化指標來尋找零件隊列中最適合排入的對象。總成績包含一些所占比重不同的科目，同理，優先度也由一些權重不同的影響因子構成。

（1）主影響因子f1

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

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

Wpart）——零件排入寬度。

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

（2）次影響因子f2

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

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

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

（3）次影響因子的權重系數

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

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

為此，需要為次影響因子添加一個系數，使得當主影響因子f1取值較小時，次影響因子f2的影響力得到控制。經過反復試驗推導，采用如下表達式作為次影響因子權重系數，記為ε。

不難看出ε 的取值范圍是[0.2，1.1]，且單調遞增，當f1取值接近0 時，次影響因子受到了有效的約束。總結上述分析可最終確定優先度函數F 的表達式如下：

利用公式（4）重新計算圖4 中兩個待排零件的優先度值，發現此時3 號零件的計算值小于4 號零件，使排樣結果得到了優化。

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

2.2 算法的基本思路

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

圖5 單次排樣流程圖

3 實例計算

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

表1 所用的實驗數據

表2 兩最低水平線改進算法的排樣高度比較

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

對比表2 中的數據發現，對于所選實驗用例，本文改進算法的排樣利用率要優于最低水平線旋轉搜索算法，排樣時間雖然略有加長，但在可接受范圍內。部分排樣結果如圖6 所示。

4 結論

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

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

圖6 排樣結果實例

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

[2]趙曉東.矩形件優化排樣算法的研究與實現[D].大連：大連交通大學，2008.

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

[4]楊傳華，吳錦文，等.定序列矩形件優化排樣的二維搜索算法[J].佳木斯 大 學 學 報，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].工程設計學報，2009，16（2）：98?102.

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

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