具有安全間隙及物料裝卸點(diǎn)的多行布局問題建模與優(yōu)化

計(jì) 丹,張則強(qiáng)+,劉俊琦,方瀟悅

(1.西南交通大學(xué) 機(jī)械工程學(xué)院,四川 成都 610031;2.軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室,四川 成都 610031)

0 引言

“工業(yè)5.0”的提出進(jìn)一步激化了全球競(jìng)爭,在該情況下,制造業(yè)將面臨前所未有的挑戰(zhàn)。為了在激烈的競(jìng)爭中穩(wěn)定發(fā)展,制造業(yè)必須加快生產(chǎn)效率、降低生產(chǎn)成本以提升效益。設(shè)施布局是制造業(yè)生產(chǎn)過程中極為重要的因素,研究發(fā)現(xiàn),經(jīng)布局所產(chǎn)生的物流成本最多能占到企業(yè)整體運(yùn)營成本的50%,而合理的規(guī)劃布局能使其降低10%～30%[1],并且能夠有效縮短運(yùn)輸時(shí)長、減少材料堆積、提升生產(chǎn)效率[2]。因此,設(shè)施布局在制造業(yè)的降本增效過程中具有極大潛力。

多行設(shè)施布局問題[3-5](Multi-Row Facility Layout Problem,MRFLP)是設(shè)施布局中較為重要的一類。MRFLP因其良好的布局構(gòu)形得到廣泛應(yīng)用,如車間布局[6]、數(shù)值分析[7]、半導(dǎo)體制造[8]等。多行布局能夠提高設(shè)備利用率,促使生產(chǎn)活動(dòng)有序進(jìn)行,尤其適用于柔性車間,對(duì)當(dāng)前制造業(yè)升級(jí)轉(zhuǎn)型有著助推器的作用,因此MRFLP是工業(yè)界及學(xué)術(shù)界都較為關(guān)注的話題。

MRFLP中間隙是常被討論的因素,加強(qiáng)對(duì)間隙的研究,可以有效防止設(shè)備搬運(yùn)過程中的碰撞,便于設(shè)備散熱與維修。HUNGERLANDER等[9]建立了離散優(yōu)化模型,能夠有效控制部門間空間的數(shù)量和大小,通過構(gòu)造半正定規(guī)劃方法進(jìn)行求解,取得了良好的效果。SAFARZADEH等[10]建立了帶模糊約束的絕對(duì)線性化模型,最后提出一種用最小代價(jià)函數(shù)求解最優(yōu)解的遺傳算法。而本文所提安全間隙是指在滿足避免任何潛在安全隱患條件下設(shè)備與其他物品的安全距離。在布局活動(dòng)中考慮安全間隙,可以同時(shí)滿足同行、鄰行及設(shè)備與墻壁之間的間隔約束,能夠有效提高企業(yè)運(yùn)營的安全系數(shù)。

制造系統(tǒng)中生產(chǎn)單元間進(jìn)行物流交互的起始點(diǎn)與終點(diǎn)統(tǒng)一稱為物料裝卸點(diǎn)(Material Handling Points,MHP)[11-12],該點(diǎn)的位置規(guī)劃直接影響物料的運(yùn)輸距離,進(jìn)而引起物流成本的極大波動(dòng)。然而,當(dāng)前大部分研究均將其簡化為一點(diǎn),并設(shè)定在設(shè)施的中心位置。KMI等[13]打破這一局限,討論了MHP分離的情況,使其更貼近實(shí)際生產(chǎn)。董舒豪等[14]根據(jù)設(shè)備的擺放形式,設(shè)計(jì)了MHP在坐標(biāo)系中的表示方法,并將MHP從中心釋放至設(shè)備邊線上。MHP的位置分離,能夠有效避免運(yùn)輸路線交叉及在制品與原材料的混雜堆積,使得裝卸過程有序且高效[15]。因此,設(shè)施布局中對(duì)MHP位置的優(yōu)化也是一個(gè)重要的研究內(nèi)容。

綜上所述,設(shè)施安全間隙的考慮進(jìn)一步貼合實(shí)際,能夠降低企業(yè)運(yùn)營中不必要的損失,MHP的分離布置也使得產(chǎn)品加工更有序,物流更順暢。因此,綜合考慮以上因素的影響,本文首次提出具有安全間隙及物料裝卸點(diǎn)的擴(kuò)展多行布局問題(extended Multi-Row Layout Problem,eMRLP)。在布局行數(shù)不確定的情況下,以物流成本與布局面積最小化為目標(biāo),建立混合整數(shù)規(guī)劃模型,并運(yùn)用Gurobi對(duì)小規(guī)模問題進(jìn)行精確求解,證明了模型的準(zhǔn)確性。由于MRFLP需要明確設(shè)施的相互順序及精確位置,兼具組合優(yōu)化及連續(xù)優(yōu)化的特性[4],而兩階段的求解方法能夠有效融合離散性與連續(xù)性兩方面的求解需求,與其匹配度最高。因此,本文開發(fā)了一種兩階段算法—融合線性規(guī)劃的改進(jìn)生物地理學(xué)算法(Improved Biogeography-Based Optimizer with Linear Programming,IBBO_LP)求解該問題,通過對(duì)標(biāo)準(zhǔn)算例的求解結(jié)果比對(duì),證明了所提算法的有效性。最后將該算法運(yùn)用到實(shí)際車間布局中,進(jìn)一步驗(yàn)證了算法的優(yōu)越性。

1 具有安全間隙及物料裝卸點(diǎn)的MRFLP

1.1 問題描述

本文所提eMRLP可描述為：如圖1所示,在已知的L×W區(qū)域內(nèi),若干長寬不等的設(shè)施有序分布在平行行上,設(shè)施間物料搬運(yùn)距離非對(duì)稱,如由a運(yùn)往m的搬運(yùn)距離為dam,而由m運(yùn)往a的搬運(yùn)距離為dma。此外,設(shè)施的位置滿足一定規(guī)則,如Row1中enk代表相鄰設(shè)施n與k之間的間隙,兩者的中心距離不能低于該值;同時(shí)行間距d1、d2也在滿足間隙要求下自適應(yīng)變化。對(duì)于鄰近布局邊界的設(shè)施,為保證設(shè)施正常工作也應(yīng)留有一定間隔,以k為例,兩者間距不能低于sk。在滿足以上間隙約束后,通過優(yōu)化設(shè)施序列、確定設(shè)施精確位置,最終達(dá)到物流成本及布局面積最小化的目的。

圖1 eMRLP示意圖

1.2 基本假設(shè)條件

結(jié)合實(shí)際布局特點(diǎn),為簡化模型求解難度,作出如下假設(shè)：

(1)設(shè)施均為矩形,且設(shè)施的長和寬已知,工廠布置區(qū)域長和寬已知;

(2)設(shè)施間物流量已知,且單個(gè)設(shè)施內(nèi)部不進(jìn)行物流交互;

(3)設(shè)施間的物料搬運(yùn)距離為裝卸點(diǎn)間的曼哈頓距離;

(4)同行相鄰設(shè)施、鄰行設(shè)施、設(shè)施與布置邊界間均滿足安全間隙約束;

(5)設(shè)施安全間隙繞其四周且距離相等;

(6)設(shè)施初始物料裝卸點(diǎn)位于其下邊線且相對(duì)位置已知;

(7)設(shè)施擺放位置可旋轉(zhuǎn),旋轉(zhuǎn)角度為180°。

1.3 eMRLP的數(shù)學(xué)模型

(1)參數(shù)名稱及含義

n為設(shè)施數(shù)量;

Q為設(shè)施集合,Q={1,2,…,n};

T為分布行集合,T={1,2,…,n};

p,d為設(shè)施的物料裝、卸點(diǎn);

i,j為設(shè)施編號(hào)i,j∈Q;

t為分布行編號(hào),t∈T;

fij為設(shè)施i到設(shè)施j的單向物流量;

dxij為在x方向上,設(shè)施i的裝料點(diǎn)至j的卸料點(diǎn)之間的距離;

dyij為在y方向上,設(shè)施i的裝料點(diǎn)至j的卸料點(diǎn)之間的距離;

xi為設(shè)施i的中心橫坐標(biāo);

yt為第t行的縱坐標(biāo);

L為工廠布置區(qū)域的總長度;

W為工廠布置區(qū)域的總寬度;

length為n個(gè)設(shè)施的包絡(luò)面長度;

width為n個(gè)設(shè)施的包絡(luò)面寬度;

li為設(shè)施i的長度;

wi為設(shè)施i的寬度;

si為設(shè)施i的安全間隙。

(2)0-1變量

1.3.1 優(yōu)化目標(biāo)

物流成本由設(shè)施間的單位交互物流量與搬運(yùn)距離乘積的總和來確定,是評(píng)估布局優(yōu)劣的關(guān)鍵指標(biāo),該目標(biāo)函數(shù)的表達(dá)式為：

(1)

設(shè)施布局占地面積是指布置方案確定后,能夠包絡(luò)所有設(shè)施及其安全間隙的最小矩形的面積。面積越小則表示該設(shè)施方案的土地資源利用率越高,該目標(biāo)函數(shù)的表達(dá)式為：

F2=length×width。

(2)

權(quán)衡兩優(yōu)化目標(biāo)間的相對(duì)重要程度,利用加權(quán)法構(gòu)造新的目標(biāo)函數(shù),使得多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,該目標(biāo)函數(shù)的表達(dá)式為：

F=α1β1F1+α2β2F2。

(3)

式中：α1、α2為權(quán)重因子,且α1+α2=1;β1、β2為歸一化因子。

1.3.2 模型約束條件

(4)

(5)

xip=γi(xi-0.25li(2(pi+ci-2pici)-1))+
(1-γi)xi,?i∈Q;

(6)

xid=γi(xi+0.25li(2(pi+ci-2pici)-1))+
(1-γi)xi,?i∈Q。

(7)

式(4)和式(5)用于限制設(shè)施i的中心橫坐標(biāo);式(6)和式(7)用于計(jì)算設(shè)施i的p、d點(diǎn)橫坐標(biāo)。

(8)

(9)

(10)

yip=yid,?i∈Q。

(11)

式(8)和式(9)用于限制分布行的縱坐標(biāo);式(10)和式(11)用于計(jì)算設(shè)施i的p、d點(diǎn)縱坐標(biāo)。

dxij≥xip-xjd,?i,j∈Q,i≠j;

(12)

dxij≥xjd-xip,?i,j∈Q,i≠j;

(13)

dyij≥yip-yjd,?i,j∈Q,i≠j;

(14)

dyij≥yjd-yip,?i,j∈Q,i≠j。

(15)

式(12)和式(13)用于計(jì)算在x方向上設(shè)施i至j的距離;式(14)和式(15)用于計(jì)算在y方向上設(shè)施i至j的距離。

(16)

(17)

(18)

式(16)用于限制同行相鄰設(shè)施滿足安全間隙約束,防止設(shè)施發(fā)生重疊,造成非必要的損失;式(17)和式(18)用于限制鄰行設(shè)施滿足安全間隙約束。

(19)

(20)

式(19)和式(20)用于計(jì)算布局后的設(shè)施所占布置區(qū)域的長度和寬度。

(21)

ut-1≥ut,?t∈T;

(22)

(23)

(24)

αijt+αjit+1≥rit+rjt,1≤i

(25)

αijt,rit,βij∈{0,1} ,?i,j∈Q,i≠j,?t∈T;

(26)

ut,ci,pi,γi∈{0,1},?t∈T,?i∈Q。

(27)

式(21)表示每個(gè)設(shè)施只能布置在一行;式(22)表示行開啟順序;式(23)表示開啟行上布置設(shè)施個(gè)數(shù)的上下限;式(24)和式(25)限制變量αijt的取值;式(26)和式(27)限制決策變量的取值范圍。

2 求解eMRLP的IBBO_LP

2.1 基本生物地理學(xué)算法

生物地理學(xué)算法[16](Biogeography-Based Optimization,BBO)是Simon受生物體塊狀區(qū)域居住現(xiàn)象的啟迪,于21世紀(jì)提出的一種基于生物地理學(xué)理論的算法。該算法通過模擬生物間的遷移與變異不斷更改棲息地的環(huán)境,進(jìn)而優(yōu)化其適宜居住指數(shù)(Habitat Suitability Index,HSI)。BBO廣泛應(yīng)用于各個(gè)領(lǐng)域,如倉庫調(diào)度[17]、電力系統(tǒng)優(yōu)化[18]、機(jī)械設(shè)計(jì)[19]等,且已被證實(shí)在求解過程中具有較高的穩(wěn)定性與收斂性。因此,本文結(jié)合eMRLP的離散化與連續(xù)化并存的特性,構(gòu)建了融合BBO與線性規(guī)劃的兩階段算法,針對(duì)BBO在全局搜索上的不足,分別對(duì)遷移與變異操作進(jìn)行改進(jìn),并引入反向?qū)W習(xí)機(jī)制進(jìn)一步豐富種群多樣性,通過模擬退火操作,有效避免算法陷入局部最優(yōu),增強(qiáng)全局搜索能力。

2.2 改進(jìn)生物地理學(xué)算法

2.2.1 解序列編碼與解碼

針對(duì)eMRLP的特征,設(shè)計(jì)雙層整數(shù)的編碼方式,可行解表示為[S,C],S為可行解的前n項(xiàng),采用實(shí)數(shù)編碼,表示設(shè)施序列;C為可行解的后n項(xiàng),采用0-1編碼,表示設(shè)施旋轉(zhuǎn)矢量。定義第i個(gè)棲息地為xi=[s1,s2,…,sn,c1,c2,…,cn],s為設(shè)施編號(hào),c為其對(duì)應(yīng)設(shè)施的旋轉(zhuǎn)矢量,若c=1則該設(shè)施發(fā)生旋轉(zhuǎn),否則保持原有狀態(tài);棲息地種群為X={x1;x2;…;xN},其中N為棲息地種群數(shù)量。針對(duì)MRFLP,自動(dòng)換行策略因其簡捷高效等優(yōu)點(diǎn)得到廣泛應(yīng)用,它是指限定區(qū)域內(nèi)設(shè)施布置遵循從上到下、從左到右的順序,在滿足約束條件下緊密布置的策略。本文采用自動(dòng)換行策略進(jìn)行解碼,針對(duì)解碼過程中產(chǎn)生的不可行解(即設(shè)施布置區(qū)域超過原工廠限定區(qū)域),引入懲罰函數(shù),如式(28),為保證算法在前期搜索過程中的種群多樣性以及提高算法后期不可行解的淘汰速率,將懲罰因子設(shè)計(jì)為伴隨迭代遞增的指數(shù)函數(shù)：

(28)

δ=δ0θt。

(29)

式中：δ為懲罰因子,δ0為懲罰因子初始值,t為當(dāng)前迭代次數(shù),θ為大于1的常數(shù)。

為便于讀者理解,以n=8的多行布局為例,該序列的編碼、解碼方式如圖2所示。前述解序列為x=[8,5,7,3,6,1,2,4,0,1,1,0,1,1,1,0],通過自動(dòng)換行策略得出分行矢量hs=[3,2,3,0,0,0,0,0],則該布置方案為：第一行分布設(shè)施數(shù)為3,設(shè)施序列為[8,5,7],旋轉(zhuǎn)矢量為[0,1,1];第二行分布設(shè)施數(shù)為2,設(shè)施序列為[3,6],旋轉(zhuǎn)矢量為[0,1];第三行分布設(shè)施數(shù)為3,設(shè)施序列為[1,2,4],旋轉(zhuǎn)矢量為[1,1,0]。

圖2 編碼、解碼過程

2.2.2 分階段遷移操作

遷移是BBO中最重要的操作之一,通過棲息地的HSI衡量其發(fā)生遷移的可能性。棲息地的HSI越大,生活的物種越多,生存空間飽和競(jìng)爭較為激烈,致使遷出率大,遷入率小;反之,生活的物種越少,生存空間充足競(jìng)爭越小,致使遷出率小,遷入率大。經(jīng)文獻(xiàn)[20]驗(yàn)證,在遷移機(jī)制中使用雙曲正切模型求解性能較優(yōu),因此本文將采用雙曲正切的遷移模型,如式(30)所示：

(30)

式中：λi為遷入率;μi為遷出率;a為雙曲正切模型參數(shù),取1.1;npop為種群數(shù)量;I、E分別為最大遷入率和遷出率,均取1。

傳統(tǒng)的BBO中,HSI較高的棲息地不易發(fā)生變化,從而導(dǎo)致陷入局部最優(yōu)。為彌補(bǔ)該不足,本文增添?xiàng)⒌匦畔⒔涣骷白晕艺{(diào)節(jié)機(jī)制以豐富種群多樣性。如圖3a所示,若隨機(jī)數(shù)不大于遷入率,則進(jìn)行遷移操作,否則進(jìn)行階段性優(yōu)化操作：若迭代次數(shù)未超過總迭代次數(shù)的1/3,則棲息地間采用部分映射交叉操作進(jìn)行信息交流,如圖3b所示;若迭代次數(shù)未超過總迭代次數(shù)的2/3,棲息地采用片段逆轉(zhuǎn)操作,如圖3c所示;否則棲息地采用單點(diǎn)變異操作進(jìn)行自我改善,如圖3d所示。

圖3 遷移操作

2.2.3 反向?qū)W習(xí)機(jī)制

(31)

2.2.4 自適應(yīng)變異操作

變異也是構(gòu)成BBO的主要操作,由于外界因素(如水澇、地震等自然災(zāi)害)造成棲息地環(huán)境突變,原本相對(duì)飽和的生存狀態(tài)被打破,因此能夠有效避免算法早熟收斂的現(xiàn)象。該操作通過對(duì)變異概率的自適應(yīng)調(diào)整,使得收斂的速率與精度都得到極大提高。自適應(yīng)變異概率公式如下：

(32)

式中：pmmax、pmmin為變異概率的上、下限,newobj為變異操作后解的目標(biāo)值,avgobj為新種群的目標(biāo)平均值,newobjmax為種群中個(gè)體的最大目標(biāo)值,目標(biāo)值obj為HSI的倒數(shù)。變異操作采用單點(diǎn)逆向插入方式,如圖4所示。

圖4 變異操作

2.2.5 模擬退火局部搜索

模擬退火是一種基于固體退火原理的隨機(jī)搜索算法,搜索中以具有時(shí)變特征的概率判斷新解的接受可能性,使得迭代過程能夠有效跳出局部極小并最終趨于全局最優(yōu)。根據(jù)蒙特卡洛準(zhǔn)則,計(jì)算t時(shí)刻固體內(nèi)粒子趨于平衡狀態(tài)的概率e^(-ΔE/t),其中E模擬為成本與面積總量。針對(duì)當(dāng)前種群中HSI最高的棲息地采用退火操作構(gòu)造鄰域解,并通過退火機(jī)制不斷優(yōu)化解的結(jié)構(gòu),最終以貪心策略作為最優(yōu)個(gè)體更新的判斷依據(jù)。退火操作及局部搜索流程如圖5所示。

a 退火操作

2.2.6 雙閾值停止準(zhǔn)則

為權(quán)衡求解質(zhì)量與效率,設(shè)置雙閾值停止機(jī)制,進(jìn)一步排除冗余迭代次數(shù),縮短了求解時(shí)長。模擬退火局部搜索中,若解的連續(xù)未更新次數(shù)T>T_max或溫度T0低于終止溫度Tf,則內(nèi)部檔案搜索工作完成并跳出進(jìn)行外部檔案的迭代,若外部檔案中最優(yōu)解連續(xù)未更新次數(shù)it>it_max或迭代次數(shù)t達(dá)到最大迭代次數(shù)MaxIt,則認(rèn)為全部搜索已完成,迭代終止,當(dāng)前最優(yōu)棲息地即為最優(yōu)解。

2.3 IBBO算法步驟

IBBO的具體步驟如下：

步驟1初始化參數(shù),如最大迭代次數(shù)MaxIt,棲息地?cái)?shù)量npop,初始溫度T0,終止溫度Tf,外部閾值it_max,退火閾值T_max,退火因子alpha等;

步驟2初始化種群N,計(jì)算HSI(xi),取HSI最高的棲息地X為最優(yōu)解;

步驟3對(duì)N進(jìn)行分階段遷移操作得到種群N_1;

步驟4對(duì)種群N_1進(jìn)行反向?qū)W習(xí)操作得到種群N_2;

步驟5對(duì)種群N_2進(jìn)行自適應(yīng)變異操作得到種群N_3;

步驟6混合N_1、N_2、N_3并按HSI由高到低排序,取前npop個(gè)個(gè)體組成種群N_new,按一定比例取N的前n1個(gè)個(gè)體與N_new的前n2個(gè)個(gè)體更新初始種群及最優(yōu)個(gè)體X;

步驟7對(duì)X進(jìn)行模擬退火局部搜索操作,并更新X;

步驟8t>1時(shí),若外部檔案更新,則it=0,否則It=it+1,若it>it_max則輸出當(dāng)前最優(yōu)解X,否則執(zhí)行第9步;t≤1時(shí),直接轉(zhuǎn)步驟9;

步驟9令t=t+1,若t>MaxIt,則輸出當(dāng)前最優(yōu)解X,否則重復(fù)步驟3～步驟9。

IBBO的算法流程如圖6所示。

圖6 IBBO流程圖

2.4 精確求解

算法第一階段采用自動(dòng)換行策略求得可行解X,并以此確定變量αijt、rit、ut、yt,隨后對(duì)1.3節(jié)中所提數(shù)學(xué)模型進(jìn)行線性化,將可行解X及其決策變量代入線性規(guī)劃(Linear Programming,LP)模型,最終求得設(shè)施在各行上的精確位置及目標(biāo)值。LP模型的目標(biāo)函數(shù)為式(3),約束為式(4)～式(7)、式(10)～式(16)、式(19)和式(20)。

3 實(shí)驗(yàn)結(jié)果分析

3.1 算法驗(yàn)證

本文所有實(shí)驗(yàn)均在裝有Intel(R) Core(TM) i5-9500處理器的臺(tái)式電腦上運(yùn)行,主頻為3 GHz,Windows 10操作系統(tǒng),內(nèi)存8.00 GB。鑒于當(dāng)前研究中未有對(duì)eMRLP的運(yùn)算結(jié)果,因此為驗(yàn)證本文所提模型的準(zhǔn)確性,應(yīng)用MATLAB R2016b調(diào)用精確求解器Gurobi對(duì)模型進(jìn)行求解,并將計(jì)算結(jié)果作為算法的依據(jù)。為驗(yàn)證IBBO_LP的求解性能,應(yīng)用IBBO_LP、BBO_LP及IBBO對(duì)eMRLP的規(guī)模為5～49中若干個(gè)算例進(jìn)行求解,其中S5為從S9中提取規(guī)模為5的算例,其余均為設(shè)施布局領(lǐng)域[21-22]的經(jīng)典算例,取自文獻(xiàn)[23]。在大量的實(shí)驗(yàn)和調(diào)試后,設(shè)定參數(shù)如表1所示(IBBO與IBBO_LP參數(shù)一致,floor(x)表示對(duì)x向下取整),參考文獻(xiàn)[24]取α1=0.7、α2=0.3。為保證結(jié)果的可信性,每個(gè)算例算法均運(yùn)行10次,并將求解結(jié)果(保留小數(shù)點(diǎn)后兩位)整理至表2,gap為求解偏差,obj為最優(yōu)目標(biāo)值,t為平均運(yùn)行時(shí)間,SD為標(biāo)準(zhǔn)差。

表1 工廠布置區(qū)域尺寸及算法參數(shù)

表2 Gurobi求解器、IBBO_LP及BBO_LP求解結(jié)果

表2中,Gurobi能在有限的時(shí)間內(nèi)求得小規(guī)模算例的最優(yōu)解,驗(yàn)證了所提模型的準(zhǔn)確性,然而隨著問題規(guī)模的擴(kuò)大,求解時(shí)間爆炸式遞增,因此為保證求解效率,將求解器的運(yùn)行時(shí)間限制為18 000 s,“—”代表運(yùn)行至限定時(shí)間時(shí)仍求不到可行解。為便于比較,表中目標(biāo)最優(yōu)值加粗顯示。

由表2可以看出,IBBO_LP在求解S5、S9時(shí),目標(biāo)值與Gurobi的求解結(jié)果相同,且對(duì)于15～30規(guī)模,IBBO_LP所得目標(biāo)值均優(yōu)于Gurobi,且其求解時(shí)間遠(yuǎn)遠(yuǎn)低于Gurobi,由此證明了所提算法求解eMRLP的正確性及高效性。通過比較BBO_LP與IBBO_LP的前兩列結(jié)果可看出,后者在運(yùn)行時(shí)間低于前者的情況下,所求目標(biāo)值仍比前者優(yōu),表明算法在求解質(zhì)量及求解效率方面的改進(jìn)效果較為顯著。通過比較IBBO與IBBO_LP的目標(biāo)值可以明顯看出,在自動(dòng)換行基礎(chǔ)上加入線性規(guī)劃階段求得設(shè)施的精確位置,能夠使可行解得到進(jìn)一步優(yōu)化。此外,通過比較3種算法求解結(jié)果的標(biāo)準(zhǔn)差SD可以看到,IBBO_LP在求解大多數(shù)算例時(shí),其SD相較于其余兩種算法較小,也說明了改進(jìn)算法的求解穩(wěn)定性較高。

3.2 算法性能分析

為進(jìn)一步驗(yàn)證所提算法求解eMRLP的性能,選擇規(guī)模為5～30中的10個(gè)算例,用BBO_LP、IBBO_LP分別對(duì)其進(jìn)行求解,對(duì)于每個(gè)算例算法均被運(yùn)行10次,儲(chǔ)存求解結(jié)果作為初始數(shù)據(jù)。運(yùn)用公式對(duì)所得數(shù)據(jù)進(jìn)行百分化處理,處理后的值為求解偏差gap,其求解公式為gap=(g-G)/G×100%,其中：g為當(dāng)前目標(biāo)值,G為該組數(shù)據(jù)中最優(yōu)目標(biāo)值。以10組gap值作為統(tǒng)計(jì)數(shù)據(jù),繪制盒式圖,如圖7所示,紅實(shí)線、黑虛線,矩形盒的上下邊緣及上下黑實(shí)線分別代表數(shù)據(jù)的中位數(shù)、平均值、上下四分位數(shù)及數(shù)據(jù)最值。

圖7 IBBO_LP與BBO_LP結(jié)果盒式圖

通過圖7可看出,在求解小規(guī)模算例時(shí),IBBO_LP求解的gap值均為0,說明算法10次運(yùn)行結(jié)果相同,算法穩(wěn)定性較強(qiáng)。在求解中大規(guī)模算例時(shí),IBBO_LP的矩形盒縱向長度比BBO_LP小,說明IBBO_LP所得數(shù)據(jù)較為集中;此外,IBBO_LP求解的矩形盒中黑色虛線位置均低于BBO_LP,表明IBBO_LP所得數(shù)據(jù)偏差值較小,離散度較低。

與此同時(shí),選取S9算例,運(yùn)用BBO、IBBO對(duì)其進(jìn)行求解,并繪制迭代圖。如圖8所示,改進(jìn)前BBO在迭代約15次后,目標(biāo)值不再變化,算法陷入局部最優(yōu)解。由迭代收斂曲線可知,IBBO在前15次迭代中目標(biāo)值優(yōu)化速度明顯優(yōu)于BBO,且在第27和57次時(shí)因退火機(jī)制的作用,算法跳出當(dāng)前最優(yōu)解,在全局搜索過程中目標(biāo)值進(jìn)一步優(yōu)化。IBBO設(shè)置雙閾值,只需迭代80次便得到更高質(zhì)量的解。因此,改進(jìn)后的算法在求解精度及求解速度上都有明顯的優(yōu)勢(shì),也再次證明了本文對(duì)算法的改進(jìn)操作使得其性能得到大幅度提升。

圖8 IBBO、BBO求解S9結(jié)果迭代圖

4 實(shí)例驗(yàn)證

為進(jìn)一步說明IBBO_LP在求解多行布局問題上的高效性,應(yīng)用該算法求解文獻(xiàn)[25]中12規(guī)模的車間(長108 m、寬78 m)布局問題,該問題未涉及安全間隙及物料裝卸點(diǎn)約束且目標(biāo)僅為物流成本,因此將IBBO簡化為單目標(biāo)算法,其編碼方式調(diào)整為單層整數(shù)編碼,鄰域操作均轉(zhuǎn)變?yōu)橄鄳?yīng)的單層變換,安全間隙設(shè)置為0。在算法的LP階段,目標(biāo)函數(shù)為式(1);約束條件中將裝卸點(diǎn)簡化至設(shè)施中心,其對(duì)應(yīng)的距離公式調(diào)整為：

dxij≥xi-xj,?i,j∈Q,i≠j;

(33)

dxij≥xj-xi,?i,j∈Q,i≠j。

(34)

文獻(xiàn)[25]采用多行布置模型對(duì)原車間布局進(jìn)行改進(jìn),并采用遺傳算法(Genetic Algorithm,GA)對(duì)其求解,最終得到物流成本F1=1 973 116 t·m,比原布局降低29.5%。為對(duì)比明顯,本文首先將文獻(xiàn)中的最優(yōu)布局[4,8,12,6,11,9,5,3,2,1,10,7]代入算法的LP階段,得到F2=1 916 079 t·m,與F1相比減少2.89%,因此運(yùn)用LP求解設(shè)施的精確位置,能獲得更優(yōu)的布局方案。求解方案如圖9所示。

應(yīng)用本文所提算法IBBO_LP進(jìn)行求解,如下設(shè)置算法參數(shù)：MatIt=200,npop=100,T0=2000,Tf=1,it_max=floor(MaxIt/3),T_max=30。為保證數(shù)據(jù)準(zhǔn)確性,將算法運(yùn)行10次,取其中最優(yōu)解作為最終布局方案如圖10a所示,該方案的物流成本F3=1 783 588 t·m,相較于文獻(xiàn)[25]降低了9.61%,再次驗(yàn)證了該算法在求解車間多行布局上的優(yōu)越性。然而,物流成本的降低卻增加了布局面積,考慮到車間布局實(shí)際,兼顧兩方面的需求,通過雙目標(biāo)IBBO_LP求得最優(yōu)布局方案如圖10b所示。方案P4與P1相比,成本降低2.03%,布局面積降低10%,在降低物流成本的同時(shí)也縮減了設(shè)施布置后的占地面積,節(jié)約了土地資源,進(jìn)一步增加了企業(yè)運(yùn)營的效益。

a IBBO_LP單目標(biāo)求解布局方案P3

5 結(jié)束語

針對(duì)設(shè)施安全間隙及物料裝卸點(diǎn)等在多行布局研究中的不足,本文提出了具有安全間隙及物料裝卸點(diǎn)的多行布局問題。針對(duì)該問題的雙重特性,構(gòu)建了智能算法與線性規(guī)劃相結(jié)合的兩階段算法。通過對(duì)標(biāo)準(zhǔn)算例及實(shí)例的求解,驗(yàn)證了所提算法的優(yōu)越性能。本文主要成果如下：

(1)考慮設(shè)施安全間隙及物料裝卸點(diǎn)在多行布局中的影響,以最小化物流成本及布局面積為目標(biāo),構(gòu)建了混合整數(shù)規(guī)劃模型,并運(yùn)用Gurobi進(jìn)行求解,驗(yàn)證了模型的準(zhǔn)確性;

(2)針對(duì)問題特性,融合智能算法與線性規(guī)劃的優(yōu)勢(shì),提出了兩階段方法。第一階段通過IBBO優(yōu)化設(shè)施的相互位置并確定位置有關(guān)變量;第二階段通過LP模型確定設(shè)施在各行上的精確位置,得出最優(yōu)解;

(3)對(duì)24個(gè)標(biāo)準(zhǔn)算例進(jìn)行求解,通過比較4種方法的求解結(jié)果,證明了IBBO無論是在求解質(zhì)量還是求解效率上都有良好的表現(xiàn)。此外,選取10個(gè)算例結(jié)果繪制求解偏差盒式圖,數(shù)據(jù)表明了算法具有較好的穩(wěn)定性。

(4)應(yīng)用IBBO_LP求解實(shí)際車間布局問題,比較4種布局方案得出,方案P4在物流成本及布局面積上均低于原文獻(xiàn)的P1,驗(yàn)證了本文所提算法在求解多行布局問題上的優(yōu)越性能。

本文為簡化模型,將物料裝卸點(diǎn)固定在設(shè)施同一側(cè)邊線上。在未來研究中,可將同邊約束釋放,根據(jù)實(shí)際復(fù)雜車間布局情況規(guī)劃裝卸點(diǎn)位置。布局評(píng)價(jià)中,物流擁擠度、運(yùn)輸時(shí)間等也是較為重要的因素,因此可增加模型中的目標(biāo)函數(shù),進(jìn)一步完善多行布局問題。