布局問題的分類及求解方法

摘 要：鑒于布局問題的多樣性和復雜性，有必要對布局問題的分類以及常見的求解方法做一個研究總結。首先對布局問題分別按照空間維數，布局物的形狀和約束條件分別進行分類，接著對各類布局問題常用的求解方法作了介紹，最后對布局問題的研究現狀和發展趨勢做了總結和展望。

關鍵詞：布局問題；性能約束；啟發式方法；智能算法

引言

布局問題是工業生產中經常出現的問題，如在玻璃切割、服裝裁減以及金屬加工等行業，需要在標準的材料上，切割出所需要的多個小型件，要求材料浪費最少；又如在貨物運輸、機械設計等領域，需要將一些小型的對象，如貨品、零件、集成塊等，裝入一個大的容器，要求裝載的對象數目最多（或者某種價值最大）。

布局問題的研究不僅具有重要的經濟意義，也具有很強的理論意義。鑒于布局問題的多樣性、復雜性，文章對布局問題的分類以及求解方法的做了一個研究綜述。

1 布局問題的分類

工業生產中的布局問題各種各樣，根據布局物維數、布局物和布局空間形狀以及是否帶性能約束，布局問題可分為如下幾類[1]：

1.1 空間維數

布局問題按照空間維數可分為：一維布局問題、二維布局問題和三維布局問題。一般來說，問題維數越高，求解越困難。其中一維布局問題較為簡單。二維布局問題由于其廣泛的應用，是現階段布局問題研究的一個主要分支。三維布局問題，由于圖形和約束條件的復雜性，難于求解，因此研究相對較少，它將會成為今后布局問題研究的重點。

1.2 布局物的形狀

布局問題按照布局物的形狀，可分為規則圖形的布局和不規則圖形的布局。相對于規則圖樣的布局問題，不規則圖樣的布局問題的求解要困難很多，是由于不規則圖樣在不同的角度可以形成不同的布局方案，使得其解空間比規則圖樣的解空間大得多。因此，現實優化中，往往通過將不規則布局物簡化處理為規則圖形進行布局，但是這種近似處理會影響求解質量，從而很難得到較高質量的解。

1.3 約束條件

布局問題按照是否帶性能約束分為：無性能約束問題和帶性能約束問題。無性能約束的問題只需滿足基本的不干涉要求，并盡量提高空間利用率。帶性能約束布局問題除了要滿足以上基本要求外，還帶有其它的性能約束。相比而言，帶性能約束的布局問題由于存在多約束條件，使得解空間呈現出多峰態、非線性、不連續的特點，求解更加困難。

2 布局問題求解方法的分類

由于布局問題在工業產品中的廣泛應用，引起了許多學者的關注，對布局問題進行了大量的研究，求解布局問題的方法很多，總的說來，可以分為以下幾類。

2.1 精確的數學方法

早期的布局問題一般采用傳統的數學規劃方法求解（如線性規劃、整數規劃、非線性規劃、動態規劃、網絡流和分枝定界法等）。精確的數學方法能得到問題的最優解，但對于較大規模布局問題，其耗時是難以承受的。

2.2 啟發式方法

啟發式算法在布局問題求解中占據了重要的地位，其通常根據問題的特點，設計啟發式規則在布局空間中進行搜索，能較快的求得問題的解，是一種近似方法。但由于啟發式方法縮小了搜索的空間，故得到的解一般不是問題的最優解，只是問題的較優解。

根據啟發式策略的不同，啟發式方法又分為定位定序的構造方法和全裝填式的局部搜索方法。定位定序的構造方法根據一定的放置規則依次放置布局物，每一次放置均滿足不干涉要求和某些其他要求，直至最后一個布局物，最后得到一個完整的解。如基于一維裝箱的FFD算法、基于最左最下原則的BL算法等。這類啟發式方法解的質量和布局順序有關。與定位定序啟發式方法不同，全裝填式的局部搜索方法一次將全部的布局物放置到布局空間中，形成一個初始解，然后根據啟發式策略對某個或某些布局物進行移動，逐步改進解的質量，最后得到滿足要求的較優解。黃文奇等提出的求解圓形布局問題的“擬物法”，即是一種全裝填式的局部搜索方法[2]。啟發式算法的特點是針對某類或某些布局問題的結果較好，求解速度快，但其缺乏全局搜索能力，容易陷入局部最優，在對其他布局問題的普遍適用性上不強。

2.3 智能算法

20世紀70，80年代至今，隨著智能優化算法如遺傳算法（GA）、禁忌搜索（TS）、蟻群優化算法（ACO）、粒子群優化（PSO）算法、模擬退火算法（SA）、散射搜索（SS）算法和人工蜂群算法（ABC）等的不斷出現，給解決布局問題提供了新的思路[1-4]。由于智能算法具有全局搜索能力，在求解NP-難的布局問題上顯示出其優越性。但智能算法沒有啟發式方法針對性強，當布局問題的解空間呈現出多峰、不連續的特征時，單純的智能算法會導致搜索空間大、搜索時間長、早熟等問題，并且不同的智能算法對于不同的布局問題，解的效果也有差異。

2.4 混合算法

將智能算法與啟發式算法相結合形成混合算法，能有效彌補各自的不足，正日益成為解決布局問題的重要途徑。Dagli等[4]采用人工神經網絡方法、數學規劃和遺傳算法來求解定寬無限長板材的矩形布局問題，給出了SA、GA等與不同啟發式算法結合對不同問題實例的綜合性能評價的結果，有兩點主要結論：（1）混合算法的結果優于單純啟發式算法的結果；（2）單純啟發式算法效果越好，則混合算法在同等條件下的效果也越好。

3 結束語

總的說來，從研究問題上看，一維布局問題相對簡單，二維布局問題是當今布局問題研究的主流，而三維布局為今后研究發展的方向。基于復雜性的考慮，從布局物圖形上看，主要集中在圓形（或球體）、矩形（或長方體）等規則圖形布局上，現在逐漸開始對不規則的圖形布局進行研究；從是否在性能約束上看，大多數研究主要為無性能約束的布局問題，對帶性能約束的布局問題研究相對較少，但已引起研究者的關注。

在求解方法上，鑒于實際布局優化問題的復雜性，現階段的主要求解方法還是啟發式方法、智能算法或者兩者相結合的混合算法。這類研究包括兩個方面：（1）針對某一類具體問題，設計高效的啟發式算法；（2）開發具有較強全局搜索能力的智能算法。而三維布局的有些啟發式方法是通過擴展二維布局問題某些啟發式方法的來的，規則圖形的布局問題某些啟發式方法進行適當地修改也可以應用到一些不規則圖形布局問題上。

參考文獻

[1]徐義春.衛星艙布局問題的智能求解方法研究[D].華中科技大學，2008.

[2]黃文奇，付樟華，許如初.不等圓 Packing 問題的擬物型鄰域搜索算法[J].華中科技大學學報：自然科學版，2012，40（4）：1-4.

[3]徐榮武，封漢潁，郝飛龍，等.求解不等圓布局問題的一類遺傳算法[J].信息與控制，2004，33（6）：656-659.

[4]Dagli CH， Poshyanond N. New approaches to nesting rectangular patterns， Journal of Intelligent manufacturing[J].1997，8：177-190.

作者簡介：黃振東（1980-），男，漢族，湖北武漢人，博士，湖北經濟學院講師，主要研究方向：布局優化、計算智能，涌現計算。