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

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

關(guān)鍵詞：布局問題；性能約束；啟發(fā)式方法；智能算法

引言

布局問題是工業(yè)生產(chǎn)中經(jīng)常出現(xiàn)的問題，如在玻璃切割、服裝裁減以及金屬加工等行業(yè)，需要在標(biāo)準(zhǔn)的材料上，切割出所需要的多個(gè)小型件，要求材料浪費(fèi)最少；又如在貨物運(yùn)輸、機(jī)械設(shè)計(jì)等領(lǐng)域，需要將一些小型的對(duì)象，如貨品、零件、集成塊等，裝入一個(gè)大的容器，要求裝載的對(duì)象數(shù)目最多（或者某種價(jià)值最大）。

布局問題的研究不僅具有重要的經(jīng)濟(jì)意義，也具有很強(qiáng)的理論意義。鑒于布局問題的多樣性、復(fù)雜性，文章對(duì)布局問題的分類以及求解方法的做了一個(gè)研究綜述。

1 布局問題的分類

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

1.1 空間維數(shù)

布局問題按照空間維數(shù)可分為：一維布局問題、二維布局問題和三維布局問題。一般來說，問題維數(shù)越高，求解越困難。其中一維布局問題較為簡(jiǎn)單。二維布局問題由于其廣泛的應(yīng)用，是現(xiàn)階段布局問題研究的一個(gè)主要分支。三維布局問題，由于圖形和約束條件的復(fù)雜性，難于求解，因此研究相對(duì)較少，它將會(huì)成為今后布局問題研究的重點(diǎn)。

1.2 布局物的形狀

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

1.3 約束條件

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

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

由于布局問題在工業(yè)產(chǎn)品中的廣泛應(yīng)用，引起了許多學(xué)者的關(guān)注，對(duì)布局問題進(jìn)行了大量的研究，求解布局問題的方法很多，總的說來，可以分為以下幾類。

2.1 精確的數(shù)學(xué)方法

早期的布局問題一般采用傳統(tǒng)的數(shù)學(xué)規(guī)劃方法求解（如線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、網(wǎng)絡(luò)流和分枝定界法等）。精確的數(shù)學(xué)方法能得到問題的最優(yōu)解，但對(duì)于較大規(guī)模布局問題，其耗時(shí)是難以承受的。

2.2 啟發(fā)式方法

啟發(fā)式算法在布局問題求解中占據(jù)了重要的地位，其通常根據(jù)問題的特點(diǎn)，設(shè)計(jì)啟發(fā)式規(guī)則在布局空間中進(jìn)行搜索，能較快的求得問題的解，是一種近似方法。但由于啟發(fā)式方法縮小了搜索的空間，故得到的解一般不是問題的最優(yōu)解，只是問題的較優(yōu)解。

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

2.3 智能算法

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

2.4 混合算法

將智能算法與啟發(fā)式算法相結(jié)合形成混合算法，能有效彌補(bǔ)各自的不足，正日益成為解決布局問題的重要途徑。Dagli等[4]采用人工神經(jīng)網(wǎng)絡(luò)方法、數(shù)學(xué)規(guī)劃和遺傳算法來求解定寬無限長(zhǎng)板材的矩形布局問題，給出了SA、GA等與不同啟發(fā)式算法結(jié)合對(duì)不同問題實(shí)例的綜合性能評(píng)價(jià)的結(jié)果，有兩點(diǎn)主要結(jié)論：（1）混合算法的結(jié)果優(yōu)于單純啟發(fā)式算法的結(jié)果；（2）單純啟發(fā)式算法效果越好，則混合算法在同等條件下的效果也越好。

3 結(jié)束語

總的說來，從研究問題上看，一維布局問題相對(duì)簡(jiǎn)單，二維布局問題是當(dāng)今布局問題研究的主流，而三維布局為今后研究發(fā)展的方向?；趶?fù)雜性的考慮，從布局物圖形上看，主要集中在圓形（或球體）、矩形（或長(zhǎng)方體）等規(guī)則圖形布局上，現(xiàn)在逐漸開始對(duì)不規(guī)則的圖形布局進(jìn)行研究；從是否在性能約束上看，大多數(shù)研究主要為無性能約束的布局問題，對(duì)帶性能約束的布局問題研究相對(duì)較少，但已引起研究者的關(guān)注。

在求解方法上，鑒于實(shí)際布局優(yōu)化問題的復(fù)雜性，現(xiàn)階段的主要求解方法還是啟發(fā)式方法、智能算法或者兩者相結(jié)合的混合算法。這類研究包括兩個(gè)方面：（1）針對(duì)某一類具體問題，設(shè)計(jì)高效的啟發(fā)式算法；（2）開發(fā)具有較強(qiáng)全局搜索能力的智能算法。而三維布局的有些啟發(fā)式方法是通過擴(kuò)展二維布局問題某些啟發(fā)式方法的來的，規(guī)則圖形的布局問題某些啟發(fā)式方法進(jìn)行適當(dāng)?shù)匦薷囊部梢詰?yīng)用到一些不規(guī)則圖形布局問題上。

參考文獻(xiàn)

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

[2]黃文奇，付樟華，許如初.不等圓 Packing 問題的擬物型鄰域搜索算法[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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.

作者簡(jiǎn)介：黃振東（1980-），男，漢族，湖北武漢人，博士，湖北經(jīng)濟(jì)學(xué)院講師，主要研究方向：布局優(yōu)化、計(jì)算智能，涌現(xiàn)計(jì)算。