基于NSGA-Ⅱ與A*算法的原竹初加工生產(chǎn)線設(shè)施布局研究

廖政洲 刁 燕 李政豪 段必成

（四川大學(xué)機(jī)械工程學(xué)院，四川 成都 610065）

我國(guó)是世界上最主要的產(chǎn)竹國(guó)，竹類資源和竹類產(chǎn)品的對(duì)外貿(mào)易量均位于世界首位。預(yù)計(jì)到2030 年，我國(guó)竹產(chǎn)業(yè)總產(chǎn)值將達(dá)到一萬(wàn)億，竹產(chǎn)業(yè)發(fā)展前景巨大[1]。竹材在經(jīng)過(guò)一定處理后可代替木材[2]，能減少碳排放穩(wěn)定氣候，降低森林火災(zāi)發(fā)生風(fēng)險(xiǎn)[3]。竹類產(chǎn)品品種豐富，有工業(yè)產(chǎn)品以及各種家具[4]藝術(shù)品，其加工設(shè)備也層出不窮[5-6]，如智能化的分選剖竹設(shè)備[7]。在生產(chǎn)線設(shè)計(jì)方面，宋菲菲[8]以產(chǎn)能匹配為核心理念，設(shè)計(jì)了重組竹生產(chǎn)線。龔正等[9]設(shè)計(jì)了重組竹竹方冷壓裝料自動(dòng)化生產(chǎn)裝置[10]。周涵譽(yù)[11]建立了小型竹砧板柔性自動(dòng)生產(chǎn)線。然而，針對(duì)原竹生產(chǎn)線布局的研究文獻(xiàn)很少，現(xiàn)有的布局方法主要是在U型、直線型和混合型基礎(chǔ)上進(jìn)行修改或使用SPL（系統(tǒng)布局規(guī)劃）。對(duì)加工制造企業(yè)來(lái)說(shuō)，整個(gè)生產(chǎn)環(huán)境運(yùn)營(yíng)費(fèi)用的20%～50%為物流費(fèi)用，而精細(xì)布局能減少物流費(fèi)用，并提高生產(chǎn)效率。在實(shí)際工廠中，往往根據(jù)經(jīng)驗(yàn)來(lái)進(jìn)行布局，沒(méi)有經(jīng)過(guò)詳細(xì)的計(jì)算，其物流路線長(zhǎng)、運(yùn)輸路徑干涉多、效率低。因此，對(duì)原竹初加工生產(chǎn)線進(jìn)行布局優(yōu)化很有必要。

SPL是專門(mén)應(yīng)用于平面規(guī)劃的一種傳統(tǒng)方法，在布局優(yōu)化問(wèn)題中應(yīng)用廣泛[12-13]。該方法需要人工分析物流和非物流因素，從而排布設(shè)備位置，過(guò)程繁瑣，多受主觀因素影響。隨著計(jì)算模型的復(fù)雜化，SPL的效果不佳。目前，研究多采用智能算法來(lái)解決布局優(yōu)化問(wèn)題。汪和平等[14]利用人工蜂群算法對(duì)預(yù)制件廠生產(chǎn)布局進(jìn)行了優(yōu)化。譚健[15]使用遺傳算法對(duì)凸輪軸生產(chǎn)線進(jìn)行了布局優(yōu)化。葛曉梅等[16]使用改進(jìn)的遺傳算法，對(duì)鋼構(gòu)件車(chē)間進(jìn)行了布局優(yōu)化。張一飛[17]針對(duì)翅片式蒸發(fā)器生產(chǎn)線的布局問(wèn)題，將遺傳退火算法結(jié)合SPL進(jìn)行了優(yōu)化。Pourhassan等[18]研究了動(dòng)態(tài)布局優(yōu)化問(wèn)題，運(yùn)用NSGA-Ⅱ算法進(jìn)行優(yōu)化。曾強(qiáng)等[19]也利用NSGA-Ⅱ算法對(duì)車(chē)間布局進(jìn)行了優(yōu)化。Guan等[20]建立了車(chē)間內(nèi)部和外部車(chē)間布局的綜合優(yōu)化模型，并采用多目標(biāo)粒子群優(yōu)化算法進(jìn)行整體布局優(yōu)化。

目前研究都是根據(jù)不同生產(chǎn)線的特點(diǎn)，建立具體的數(shù)學(xué)模型，設(shè)計(jì)智能算法來(lái)進(jìn)行布局優(yōu)化。原竹初加工生產(chǎn)線具有以下特點(diǎn)：1）每個(gè)工序機(jī)器大小不同，是不等面積的布局優(yōu)化問(wèn)題；2）原竹加工生產(chǎn)線將趨于智能化，運(yùn)輸路徑干涉對(duì)生產(chǎn)線搭建和運(yùn)營(yíng)有嚴(yán)重影響，減少干涉勢(shì)在必行。針對(duì)不等面積問(wèn)題，可以建立獨(dú)特的數(shù)學(xué)模型。針對(duì)運(yùn)輸路徑干涉的問(wèn)題，則可以采用A*算法規(guī)劃運(yùn)輸路徑，判斷路徑干涉。在之前的研究中，計(jì)算設(shè)備之間運(yùn)輸距離多采用曼哈頓距離[21]。相比而言，A*算法可以避免其計(jì)算路徑過(guò)長(zhǎng)和無(wú)法考慮障礙的缺陷。同時(shí)，NSGA-Ⅱ在求解多目標(biāo)問(wèn)題時(shí)表現(xiàn)出色。綜上，本文采用A*算法計(jì)算物料運(yùn)輸成本和運(yùn)輸路徑之間的交叉干涉，并結(jié)合NSGA-Ⅱ算法進(jìn)行優(yōu)化，進(jìn)而輸出PO前沿和布局方案。

1 生產(chǎn)線模型構(gòu)建

1.1 生產(chǎn)工藝分析

如圖1所示，原竹初加工工藝流程主要為原竹、截?cái)?、分選、開(kāi)條[22]。截?cái)嗖糠钟射徶駲C(jī)完成，分選部分由自動(dòng)化的傳送帶和視覺(jué)識(shí)別模塊完成，開(kāi)條工藝由自動(dòng)換刀的剖竹機(jī)完成。為了保證整個(gè)生產(chǎn)過(guò)程中的物料流通順暢，在截?cái)嗪烷_(kāi)條中間增加半成品儲(chǔ)料區(qū)進(jìn)行緩沖，并根據(jù)生產(chǎn)情況來(lái)確定設(shè)備數(shù)量。

圖1 加工工藝流程圖Fig.1 Primary processing process of bamboo

1.2 數(shù)學(xué)模型建立

根據(jù)原竹初加工生產(chǎn)線和A*算法特點(diǎn)建立設(shè)備布局的數(shù)學(xué)模型。做出如下假設(shè)：1）每個(gè)設(shè)備和車(chē)間均為長(zhǎng)方形且兩邊已知；2）每個(gè)設(shè)備擺放好后，其邊與車(chē)間墻壁平行；3）運(yùn)輸起止點(diǎn)為設(shè)備質(zhì)心，運(yùn)輸路徑不能與其他設(shè)備干涉；4）將整個(gè)車(chē)間劃分為單位長(zhǎng)度為e的網(wǎng)格，設(shè)備的質(zhì)心和邊長(zhǎng)需落在網(wǎng)格上。

原竹初加工的場(chǎng)地和設(shè)備都近似于長(zhǎng)方形，且設(shè)備一般與墻壁平行放置，滿足1）和2）兩條假設(shè)。為了方便路徑規(guī)劃，避免運(yùn)輸時(shí)與設(shè)備碰撞，做出假設(shè)3）。A*算法是用離散節(jié)點(diǎn)來(lái)搜索物料運(yùn)輸路徑的，需將空間網(wǎng)格化且設(shè)備落在節(jié)點(diǎn)上，即為假設(shè)4）。

布局示意圖如圖2 所示。車(chē)間長(zhǎng)為L(zhǎng)，寬為H。設(shè)備位置由質(zhì)心坐標(biāo)確定。設(shè)備i的質(zhì)心坐標(biāo)為（xi，yi），x軸方向長(zhǎng)為L(zhǎng)i，y軸方向長(zhǎng)為Hi。

圖2 布局示意圖Fig.2 Representation of the layout

由于原竹初加工生產(chǎn)線設(shè)備多為長(zhǎng)方形，因此設(shè)備有兩種擺放方式，分別橫放和豎放，如圖3所示。擺放方式也會(huì)影響優(yōu)化結(jié)果。引入一個(gè)0、1變量z來(lái)記錄擺放方式。設(shè)備b較長(zhǎng)邊為Xb，較短邊為Yb。擺放后設(shè)備b的Lb，Hb按式(1)計(jì)算：

圖3 同一設(shè)備兩種擺放方式Fig.3 Tow placement methods of the same equipment

式中：當(dāng)z=1時(shí)為橫放，當(dāng)z=0時(shí)為豎放。

1.3 優(yōu)化目標(biāo)確定

原竹初加工生產(chǎn)中，物料運(yùn)輸成本占生產(chǎn)運(yùn)營(yíng)成本的20%～50%。同時(shí)，運(yùn)輸路徑干涉也會(huì)使得生產(chǎn)線建設(shè)和維護(hù)成本上升。因此，優(yōu)化目標(biāo)如式（2～3）：

式中：MHC為物料運(yùn)輸成本；i和j為設(shè)備編號(hào)；N為設(shè)備總數(shù)；pij是一個(gè)0、1變量，表示是否有i到j(luò)的物料運(yùn)輸操作；cij表示由i運(yùn)輸?shù)絡(luò)單位距離的運(yùn)輸成本；A*ij表示由A*算法計(jì)算出的i和j之間的物料運(yùn)輸距離。OL為運(yùn)輸路徑干涉交叉點(diǎn)總和，表示運(yùn)輸路徑干涉；a、b表示路徑編號(hào)；M為路徑總數(shù)；olab為路徑a和b之間的交叉點(diǎn)個(gè)數(shù)。因此，本研究的優(yōu)化目標(biāo)位減小MHC和OL。

A*算法所規(guī)劃的路徑存在3 種交叉方式，如圖4所示。節(jié)點(diǎn)和中點(diǎn)重合記為交叉點(diǎn)，起點(diǎn)終點(diǎn)不計(jì)算。1 和2 有1 個(gè)，3 有3 個(gè)。

圖4 不同交叉形式Fig.4 Three crossing modes

Horta等[23]研究了在同一條件下對(duì)于MHC和物流干涉兩個(gè)目標(biāo)分別優(yōu)化的問(wèn)題，證明了兩者是相互沖突和矛盾的，是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。

1.4 約束條件

為了模型接近現(xiàn)實(shí)，考慮實(shí)際情況，結(jié)合算法特點(diǎn)總結(jié)出以下約束條件。

1）設(shè)備與車(chē)間墻面約束

式中：s為與墻面的最小間距，m。Li和Hi由式（1）計(jì)算出。不緊靠墻壁方便原竹加工設(shè)備維護(hù)。

2）設(shè)備間距離約束

式中：Δx、Δy表示在橫縱坐標(biāo)方向上的設(shè)備間距要求。設(shè)備間的距離保證原竹加工過(guò)程中的人員物料流動(dòng)順暢。

3）設(shè)備位于網(wǎng)格上約束

式中：e為網(wǎng)格單元長(zhǎng)度，m，n為正整數(shù)。當(dāng)設(shè)備所有邊長(zhǎng)都為e的偶數(shù)倍時(shí)，質(zhì)心才有可能在網(wǎng)格點(diǎn)上。確保模型滿足假設(shè)4的要求。

2 基于NSGA-Ⅱ和A*的帶運(yùn)輸路徑規(guī)劃的多目標(biāo)布局優(yōu)化算法

2.1 NSGA-Ⅱ和A*算法原理分析

NSGA-II算法結(jié)構(gòu)簡(jiǎn)單且在大部分的測(cè)試問(wèn)題上表現(xiàn)出色。算法核心在于它的環(huán)境選擇和交配選擇。環(huán)境選擇部分，采用分層策略搜尋PO最優(yōu)解，同時(shí)定義了個(gè)體擁擠度，保留那些稀疏個(gè)體，使得求得的PO解集更加均勻和全面。交配選擇方面使用錦標(biāo)賽法[24-25]。

A*算法是一種全局路徑算法，能在障礙物已知的情況下，在平面上找到一條能避開(kāi)障礙物的較短路徑。它將整個(gè)平面離散化為網(wǎng)格節(jié)點(diǎn)，從起始點(diǎn)出發(fā)，通過(guò)代價(jià)函數(shù)判斷最優(yōu)的下一個(gè)路徑節(jié)點(diǎn)，不斷延伸通往終點(diǎn)，找到一條能躲避障礙的最佳路徑[26-27]。

2.2 算法過(guò)程

算法以NSGA-II算法為理論基礎(chǔ)，根據(jù)數(shù)學(xué)模型進(jìn)行修改。利用罰函數(shù)來(lái)去掉不滿足約束的解。使用A*算法規(guī)劃運(yùn)輸路徑從而得到目標(biāo)值，具體的優(yōu)化過(guò)程如圖5所示。

圖5 優(yōu)化算法流程圖Fig.5 Optimization algorithm flowchart

整個(gè)算法的關(guān)鍵在于將A*算法和NSGA-II算法完美融合，利用A*算法來(lái)對(duì)優(yōu)化過(guò)程中的每一個(gè)個(gè)體來(lái)進(jìn)行物流路徑的規(guī)劃從而得到目標(biāo)值，又不影響原算法計(jì)算。同時(shí)，算法是多目標(biāo)優(yōu)化算法，相較于加權(quán)方法有著更多的解、更好的結(jié)果。關(guān)鍵點(diǎn)如下：

1）使用A*算法與罰函數(shù)相結(jié)合的方式計(jì)算目標(biāo)值。先用罰函數(shù)f1(A)、f2(A)來(lái)計(jì)算約束1）、約束2）的罰函數(shù)值，A為個(gè)體矩陣。當(dāng)兩者都為0，則用A*算法規(guī)劃運(yùn)輸路徑并計(jì)算兩目標(biāo)值。否則為不滿足約束，使用式（8）和式（9）計(jì)算兩目標(biāo)值，其遠(yuǎn)大于正常值從而在后續(xù)迭代中被淘汰。α、β為懲罰因子。

2）解決A*算法嵌入后對(duì)算法影響。網(wǎng)格化操作導(dǎo)致目標(biāo)值重復(fù)的個(gè)體增加。為了避免重復(fù)，計(jì)算目標(biāo)值后去除部分重復(fù)目標(biāo)值個(gè)體，個(gè)體數(shù)不足時(shí)則生成新個(gè)體補(bǔ)足。為了提高搜索效率，初始生成的是可行個(gè)體。

2.3 編碼規(guī)則

采用3×N的矩陣來(lái)存?zhèn)€體數(shù)據(jù)。如式（10）所示，一二兩行存放質(zhì)心橫縱坐標(biāo)，第三行存放z變量。

2.4 雜交變異操作

1）雜交方法

隨機(jī)生成一個(gè)1到N-1的自然數(shù)r。將父本1前r列和父本2的前r列交換得到兩個(gè)子代。如圖6所示。

圖6 交叉示意圖Fig.6 Cross operation

2）變異方法

移動(dòng)：隨機(jī)生成1到N的兩個(gè)不同自然數(shù)r1、r2，e整數(shù)倍的d1、d2、d3、d4，大小在正負(fù)30倍之間。將父代r1列一、二行依次加上d1，d2，r2列一、二行依次加上d3、d4得到新的子代。如圖7所示。

圖7 移動(dòng)示意圖Fig.7 Move operation

改變擺放方式：隨機(jī)生成一個(gè)1到N的自然數(shù)r，將父代的r列的第三行的數(shù)zr替換為,其中按式（11）計(jì)算，變異得到新的子代。如圖8所示。

圖8 變向示意圖Fig.8 Change the placement method

交換：隨機(jī)生成1到N的四個(gè)不同自然數(shù)r1、r2、r3、r4，將父代的r1、r3列和r2、r4互換變異得到新的子代。如圖9所示。

圖9 交換示意圖Fig.9 Exchange operation

3 實(shí)例演算

3.1 輸入數(shù)據(jù)

以某原竹初加工生產(chǎn)線車(chē)間的設(shè)備來(lái)進(jìn)行實(shí)例演算。該車(chē)間L為30 m，H為30 m，單位網(wǎng)格長(zhǎng)度e為0.1 m。根據(jù)產(chǎn)能平衡原理及節(jié)拍要求，需要2臺(tái)鋸竹機(jī)、4臺(tái)剖竹機(jī)和3個(gè)儲(chǔ)料倉(cāng)庫(kù)。具體的長(zhǎng)寬數(shù)據(jù)如表1所示，原始布局個(gè)體如式（12）所示。設(shè)備間距離約束和設(shè)備與墻面距離約束的參數(shù)分別為s=1 m，Δx=Δy=1 m。物流關(guān)系如圖1所示，單位距離物料運(yùn)輸成本記為1。

優(yōu)化算法的相關(guān)參數(shù)如下：種群大小N=26，最大 循 環(huán) 次 數(shù)T=600。懲 罰 因 子α1=β1=1 000 000、α2=β2=1 000。在優(yōu)化初期，需要較高的全局搜索能力。較高的雜交概率可以實(shí)現(xiàn)這個(gè)目的。優(yōu)化的末期，需要較高的局部搜索能力來(lái)使得個(gè)體能更快收斂，并且這時(shí)過(guò)高的雜交概率會(huì)產(chǎn)生大量重復(fù)個(gè)體。在優(yōu)化末期提高變異概率。當(dāng)循環(huán)代數(shù)t＜300 時(shí)，雜交概率pSwap=0.75、移動(dòng)概率pMove=0.1、改變擺放方式概率pT=0.05、交換概率pR=0.1。當(dāng)循環(huán)代數(shù)t＞=300 時(shí)，雜交概率pSwap=0.25、移動(dòng)概率pMove=0.4、改變擺放方式概率pT=0.15、交換概率pR=0.2。

3.2 優(yōu)化結(jié)果分析

優(yōu)化后的PO前沿如圖10 所示。圖中星形紅點(diǎn)表示個(gè)體，算法計(jì)算出PO前沿分布較為均勻，個(gè)體之間的間距相似。個(gè)體不集中于一個(gè)小型區(qū)域有著較好的多樣性。

圖10 PO前沿Fig.10 PO front

原布局方案如圖11 所示，優(yōu)化后個(gè)體的位置及運(yùn)輸路徑如圖12 所示。個(gè)體1、2、3、4、5 分別對(duì)應(yīng)：圖12a、12b、12c、12d、12e。圖名為兩優(yōu)化目標(biāo)值，MHC單位為m，OL單位為個(gè)。圖中坐標(biāo)單位長(zhǎng)e，設(shè)備之間的線為規(guī)劃的物料運(yùn)輸路徑。優(yōu)化后與優(yōu)化前相比，所得到的60%的PO前沿解在兩個(gè)目標(biāo)值上都優(yōu)于原方案，所有解都有比原方案更優(yōu)的目標(biāo)值。優(yōu)化結(jié)果中，MHC最小的個(gè)體比原方案的減少了10.5%，OL最小的個(gè)體僅有原方案的2.5%。由此可以看出，優(yōu)化結(jié)果遠(yuǎn)勝于原方案，說(shuō)明優(yōu)化算法是有效的。在實(shí)際生產(chǎn)設(shè)計(jì)時(shí)，可根據(jù)實(shí)際情況在PO前沿中優(yōu)選個(gè)體。

圖11 原布局方案圖(MHC 113.94 m OL 200)Fig.11 Original layout plan(MHC 113.94 m OL 200)

圖12 PO前沿個(gè)體布局圖Fig.12 PO frontier individual layout

由圖12e中設(shè)備4 和設(shè)備5 之間的運(yùn)輸路徑可以看出，使用A*算法求解出的路徑可以解決曼哈頓距離中路徑長(zhǎng)度無(wú)法跨越障礙的問(wèn)題。由表2 可以看出，在PO前沿個(gè)體中，A*算法計(jì)算出的MHC都比曼哈頓距離計(jì)算的MHC低，平均低18.1%。使用A*算法對(duì)運(yùn)輸路徑進(jìn)行規(guī)劃，更能模擬實(shí)際情況，計(jì)算的MHC更加的精確且更低。由此可見(jiàn)，運(yùn)用A*算法來(lái)計(jì)算優(yōu)化目標(biāo)比傳統(tǒng)的曼哈頓距離更好。

表2 兩種距離算法對(duì)比表Tab.2 Comparison of two different calculation methods

4 結(jié)論

本文通過(guò)將A*算法和NSGA-Ⅱ算法相結(jié)合，設(shè)計(jì)出一種新型算法來(lái)對(duì)原竹初加工生產(chǎn)線設(shè)施布局進(jìn)行多目標(biāo)優(yōu)化。優(yōu)化后，60%的PO前沿個(gè)體其兩個(gè)目標(biāo)值都比原方案好，所有個(gè)體都有比原方案更好的目標(biāo)值。MHC最小的個(gè)體比原方案的減少了10.5%，OL最小的個(gè)體僅有原方案的2.5%，進(jìn)一步證明了該優(yōu)化算法切實(shí)可行。算法生成的PO前沿可以供實(shí)際原竹初加工生產(chǎn)線選擇。

采用A*算法計(jì)算的物料運(yùn)輸成本會(huì)比曼哈頓距離計(jì)算出的平均低18.1%，可進(jìn)一步降低原竹初加工生產(chǎn)線的物料運(yùn)輸成本。同時(shí)，還解決了曼哈頓距離中路徑長(zhǎng)度無(wú)法跨越障礙和運(yùn)輸干涉無(wú)法判斷的問(wèn)題，能夠更好地模擬原竹初加工生產(chǎn)線的實(shí)際情況。