朱俊杰,李 琳,2*,曹 力,2,劉曉平,2

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,安徽 合肥 230601;2.工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室,安徽 合肥 230009)

設(shè)備布局問題是工業(yè)生產(chǎn)領(lǐng)域的一個(gè)重點(diǎn)研究問題,主要研究對于給定的一組工業(yè)生產(chǎn)設(shè)備,在已知設(shè)備間的物流量和物流關(guān)系等數(shù)據(jù)的情況下,確定設(shè)備在生產(chǎn)車間內(nèi)的精確布局,從而實(shí)現(xiàn)生產(chǎn)成本、設(shè)備占地面積等目標(biāo)的最優(yōu)化.設(shè)備布局對于工業(yè)生產(chǎn)意義重大,Tompkins等[1]的研究指出,良好的設(shè)備布局可以減少工業(yè)生產(chǎn)中10%～30%的成本.物流場景的布局問題從廣義上屬于設(shè)備布局問題的一種,但其也有自身的特點(diǎn):對于物流場景,其主要功能是對物料進(jìn)行分揀、運(yùn)輸和存儲(chǔ),物流場景中主要有關(guān)鍵設(shè)備和輸送設(shè)備兩類設(shè)備,前者指各種加工、分揀和存儲(chǔ)設(shè)備,后者則用于連接不同的關(guān)鍵設(shè)備,以實(shí)現(xiàn)物料在關(guān)鍵設(shè)備間的運(yùn)輸.為便于表述,下文以設(shè)備代指關(guān)鍵設(shè)備,以輸送線代指輸送設(shè)備.

為了解決面向物流場景的布局問題,可從傳統(tǒng)設(shè)備布局問題開始研究.設(shè)備布局問題已被證明是一個(gè)非確定性多項(xiàng)式困難(NP-hard)問題,其解空間十分龐大,同時(shí)對于多目標(biāo)設(shè)備布局問題來說,在求解多個(gè)目標(biāo)時(shí)可能存在沖突,以上兩個(gè)原因?qū)е略O(shè)備布局問題難以求出精確的全局最優(yōu)解.元啟發(fā)式算法能在可接受的時(shí)間空間代價(jià)下求出該問題的可行解，對于解決這類問題有著很好的效果.目前在設(shè)備布局領(lǐng)域有大量關(guān)于元啟發(fā)式優(yōu)化算法的研究，包括遺傳算法[2-6]、粒子群算法[7-9]、模擬退火算法[10-14]、人工免疫算法[15-16]、差分進(jìn)化算法[17]、禁忌搜索算法[18]、教與學(xué)算法[19]等,學(xué)者們結(jié)合具體的布局問題,或加入新的搜索策略[2-5,9,11],或加入新的約束處理策略[8],或建立全新的布局模型[6-7,10],或?qū)⒍喾N優(yōu)化算法融合[20],以提高布局算法的時(shí)間效率和最終布局效果.

針對設(shè)備布局問題,目前已有大量成熟的布局方法,但針對面向物流場景的混合布局問題,傳統(tǒng)的設(shè)備布局方法還存在一些缺陷.主要表現(xiàn)為:1) 由于輸送線同時(shí)具備設(shè)備屬性和路線屬性,其中設(shè)備屬性是指輸送線本身也是設(shè)備,和其他設(shè)備一樣需要滿足重疊等約束,路線屬性是指其用于連接不同的關(guān)鍵設(shè)備,可將其看成線路,每條輸送線的長度和走向要在確定設(shè)備位置并進(jìn)行布線后方可確定,因此傳統(tǒng)的設(shè)備布局方法并不適用于輸送線.2) 傳統(tǒng)的設(shè)備布局方法由于沒有考慮輸送線布局,一般均采用理想的曼哈頓距離來表示設(shè)備間的距離,但這并不符合實(shí)際.如圖1所示,按照曼哈頓距離計(jì)算的輸送路徑會(huì)導(dǎo)致設(shè)備與輸送線發(fā)生沖突,同時(shí)這樣也未考慮兩者之間的布局約束、設(shè)備與輸送線的連接位置等因素.3) 目前很多文獻(xiàn)[4-5,13-19]將設(shè)備按照行和列進(jìn)行布局,設(shè)備位置不能連續(xù)變化,而本文中的設(shè)備和輸送線位置均可連續(xù)變化,這樣更符合實(shí)際,同時(shí)也導(dǎo)致約束處理過程更復(fù)雜,需要提出全新的約束處理策略.

圖1 兩種不同的最短距離Fig.1 Two different kinds of shortest distance

為此，本文首先建立一個(gè)考慮物料搬運(yùn)總成本和輸送線總成本的多目標(biāo)優(yōu)化數(shù)學(xué)模型,然后使用混合方法進(jìn)行布局.混合布局方法分為兩部分:第一部分為多目標(biāo)元啟發(fā)式布局算法,用于實(shí)現(xiàn)設(shè)備布局、解的更新與迭代,該部分可以選擇不同的元啟發(fā)式算法,目前在設(shè)備布局領(lǐng)域,研究較多的為多目標(biāo)遺傳算法和多目標(biāo)粒子群算法(MOPSO),模擬退火算法則一般用于解決單目標(biāo)設(shè)備布局問題[10,12-14],或者使用加權(quán)的方法將多目標(biāo)問題歸一化為單目標(biāo)問題再求解[11].因此,為了驗(yàn)證本文方法的有效性和適用性,本文分別選擇MOPSO和非支配排序遺傳算法2(NSGA2)[21]這兩種較為通用的多目標(biāo)元啟發(fā)式算法.第二部分為布線算法,用于實(shí)現(xiàn)輸送線布局,本文沒有使用理想的曼哈頓距離表示設(shè)備間路徑,而是使用一種基于多目標(biāo)評估的路徑搜索算法實(shí)現(xiàn)輸送線的布置,并結(jié)合實(shí)際問題,對該布線算法中的路徑點(diǎn)矩陣構(gòu)造策略和路徑點(diǎn)選擇評估函數(shù)等進(jìn)行了修改.此外在方法中加入了處理關(guān)鍵設(shè)備和輸送線約束的策略.最后通過同基于MOPSO和NSGA2的傳統(tǒng)設(shè)備布局方法對比,驗(yàn)證本文方法對于解決物流場景中關(guān)鍵設(shè)備和輸送線混合布局問題的有效性.

1 問題描述和數(shù)學(xué)建模

1.1 問題描述

本文在已知物流設(shè)備的種類與數(shù)目,以及物料種類、物料量、運(yùn)轉(zhuǎn)路線等條件下,實(shí)現(xiàn)對設(shè)備與輸送線的自動(dòng)化布局,從而實(shí)現(xiàn)物料搬運(yùn)總成本和輸送線總成本最小的目標(biāo).

結(jié)合相關(guān)物流背景知識和實(shí)際情況,列出本文問題的假設(shè)條件:

1) 車間大小固定且足夠容納所有設(shè)備和輸送線;

2) 所有設(shè)備大小固定,且均視為矩形,若不是矩形,則用一個(gè)包絡(luò)矩形近似表示設(shè)備形狀,如圖2(a)所示;

3) 設(shè)備的朝向分為上下左右4種,默認(rèn)方向?yàn)橄蛏?規(guī)定y軸正方向?yàn)樵O(shè)備上方;

4) 每個(gè)設(shè)備的加工效率和出入口位置已知;

6) 設(shè)備與設(shè)備之間,以及設(shè)備與輸送線間有最短距離限制;

7) 輸送線分為用于物料的長距離直線運(yùn)輸(如直線輸送機(jī))和用于實(shí)現(xiàn)物料轉(zhuǎn)向的輸送機(jī)(如萬向輪和轉(zhuǎn)彎輸送機(jī));

8) 輸送線有最短的長度限制.這里的長度指的是一條輸送線上兩個(gè)相鄰轉(zhuǎn)彎點(diǎn)間的長度,因輸送線也需考慮尺寸,故要求兩個(gè)轉(zhuǎn)彎點(diǎn)間的路線長度不小于一個(gè)轉(zhuǎn)向輸送機(jī)的長度,否則會(huì)導(dǎo)致設(shè)備發(fā)生如圖2(c)所示的重疊,違反了物理約束;

圖2 物流設(shè)備布局的問題舉例Fig.2 Problem examples of logistics equipent layout

9) 所有輸送線的輸送速度相同;

10) 輸送線只允許向水平或垂直方向延伸,不允許出現(xiàn)斜向的輸送線;

11) 物料的種類、數(shù)量和經(jīng)過的設(shè)備路線已知.

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

1.2.1 布局坐標(biāo)系

設(shè)備布局在二維平面中進(jìn)行.如圖3所示,建立了一個(gè)二維坐標(biāo)系統(tǒng),用于表示車間的坐標(biāo)范圍、設(shè)備位置和輸送線路信息.其中,O點(diǎn)為坐標(biāo)系原點(diǎn),x軸為車間的長度所在邊,y軸為車間的寬度所在邊,點(diǎn)的幾何位置用二維坐標(biāo)表示,Ein和Eout分別表示車間入口和出口.設(shè)備所在包絡(luò)矩形的中心坐標(biāo)表示其布局位置,輸送線路則使用路線起始點(diǎn)、終點(diǎn)以及各轉(zhuǎn)彎點(diǎn)間的連線表示.

圖3 布局坐標(biāo)系Fig.3 Layout coordinate system

1.2.2 目標(biāo)函數(shù)

目標(biāo)1為物料搬運(yùn)總成本f1(x)最小,f1(x)如式(1)所示.由于單個(gè)車間內(nèi)可能有多種物料需要進(jìn)行加工、運(yùn)輸和存儲(chǔ),所以設(shè)置物料種類數(shù)目為K，Sk表示物料k的總量,Lk表示物料k經(jīng)過的輸送線總長度.對于物料k，其經(jīng)過的設(shè)備及所在設(shè)備出入口的序列構(gòu)成了在車間中的運(yùn)輸路線,序列的總長度即為Lk.

(1)

目標(biāo)2為輸送線總成本f2(x)最小,f2(x)如式(2)所示.這里將輸送線成本分為直線輸送機(jī)和轉(zhuǎn)彎輸送機(jī)兩部分計(jì)算,其中LS表示直線輸送機(jī)的總長度,CS表示單位長度直線輸送機(jī)的成本，ST表示轉(zhuǎn)彎輸送機(jī)的總數(shù),CT表示單個(gè)轉(zhuǎn)彎輸送機(jī)的成本,LS和ST在輸送線布局完成后得到,CS和CT為已知量.本文中,允許兩條輸送線中間有公用部分,在計(jì)算成本時(shí)公用部分僅計(jì)算一次.

f2(x)=LS×CS+ST×CT.

(2)

1.2.3 約束條件

布局時(shí),設(shè)備與輸送線要滿足一系列約束條件:

1) 根據(jù)設(shè)備要位于車間內(nèi)，有如式(3)～(6)所示的約束條件.

Xi-0.5li≥0,?i∈{1,2,…,I}，

(3)

Yi-0.5wi≥0,?i∈{1,2,…,I}，

(4)

Xi+0.5li≤L,?i∈{1,2,…,I},

(5)

Yi+0.5wi≤W,?i∈{1,2,…,I}.

(6)

其中，I表示設(shè)備總數(shù),Xi和Yi分別表示設(shè)備i的x軸和y軸坐標(biāo),li表示設(shè)備i的長度,wi表示設(shè)備i的寬度，L表示車間長度,W表示車間寬度.

2) 設(shè)備之間不能重疊,但有最小距離限制.本文同時(shí)處理這兩個(gè)約束,通過給設(shè)備4個(gè)方向各設(shè)置一個(gè)禁區(qū)距離,布局時(shí)只需實(shí)現(xiàn)設(shè)備外層范圍間不重疊,就同時(shí)實(shí)現(xiàn)了設(shè)備重疊和距離約束.如式(7)所示,I(ai)表示設(shè)備i考慮禁區(qū)距離后的內(nèi)部范圍.

I(ai)∩I(aj)=?,i≠j,?i,j∈{1,2,…,I}.

(7)

3) 輸送線布局約束.首先見1.1節(jié)中的8),輸送線有最短長度約束,同時(shí)直線輸送機(jī)設(shè)備本身也有一個(gè)最短長度,其長度不能小于這個(gè)最小值.綜合這兩個(gè)因素,加入輸送線長度約束,Lmn表示兩個(gè)轉(zhuǎn)彎點(diǎn)m和n之間的輸送線長度.WC表示輸送機(jī)本身的寬度,LCM表示直線輸送機(jī)的最短長度限制.轉(zhuǎn)彎點(diǎn)間的長度約束如式(8)所示.

Lmn≥LCM+WC.

(8)

不同輸送線之間也不能發(fā)生重疊,如式(9)所示,I(li)和I(lj)表示任意兩條輸送線的設(shè)備范圍.

I(li)∩I(lj)=?,i≠j.

(9)

1.2.4 布局結(jié)果

布局結(jié)果包含兩部分:

1) 所有設(shè)備的坐標(biāo)及朝向信息.表示為(X1,Y1,D1,X2,Y2,D2,…,Xi,Yi,Di,…,XI,YI,DI)，其中Di表示設(shè)備i的朝向,有Di∈{Dup,Ddown,Dleft,Dright}，即每個(gè)設(shè)備有上下左右4個(gè)朝向.

2 算法描述

本文的混合布局方法整體流程如下:首先輸入物流場景布局參數(shù),然后對設(shè)備位置信息進(jìn)行編碼,根據(jù)具體的元啟發(fā)式優(yōu)化方法產(chǎn)生初始解,并使用各自的啟發(fā)式策略對解進(jìn)行更新,結(jié)合輸送線布局結(jié)果計(jì)算目標(biāo)函數(shù)值,根據(jù)目標(biāo)函數(shù)值對解進(jìn)行選擇和迭代,同時(shí)對關(guān)鍵設(shè)備和輸送線布局的約束進(jìn)行處理,通過不斷迭代得到最終布局結(jié)果.

本文分別基于MOPSO和NSGA2,并結(jié)合基于A*算法改進(jìn)的多目標(biāo)評估路徑搜索算法(具體改進(jìn)見2.3節(jié)),實(shí)現(xiàn)了MOPSO-Route和NSGA2-Route兩種混合布局算法.

算法的整體流程如圖4所示,本文將MOPSO和NSGA2算法嵌入其中,具體地,對于不同的元啟發(fā)式算法,不同的步驟主要是解的編碼和初始化、解的更新、解的篩選與迭代,其他步驟是一樣的.表1給出了它們對應(yīng)具體算法的步驟.

圖4 混合布局算法流程Fig.4 Hybrid layout algorithm flow

表1 MOPSO和NSGA2的不同步驟

2.1 解的編碼和初始化

本文對關(guān)鍵設(shè)備的坐標(biāo)和朝向信息進(jìn)行編碼:

XI,YI,DI],

(10)

為加快算法收斂速度,在初始化時(shí)本文采取一種策略來保證初始解的非重疊性和多樣性,步驟如下:

1) 將車間按照長寬等距離分割為二維網(wǎng)格,分割步長設(shè)為1 m;

2) 檢查待布局設(shè)備是否為空,若為空,結(jié)束;否則,從待布局設(shè)備中隨機(jī)選擇一個(gè)進(jìn)行布局.具體地,從空閑區(qū)域開始,在1 m×1 m范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)設(shè)備位置與朝向信息;

3) 檢查該設(shè)備位置與朝向是否與其他設(shè)備重疊,若不重疊則確定該設(shè)備的位置和朝向,并從待布局設(shè)備中刪除該設(shè)備,然后進(jìn)入步驟2);否則繼續(xù)試探設(shè)備新位置.

2.2 解的更新與迭代

得到初始解后進(jìn)入更新迭代過程.在每次迭代中,首先更新當(dāng)前解以產(chǎn)生新解,然后根據(jù)設(shè)備和輸送線布局結(jié)果計(jì)算新解的目標(biāo)函數(shù)值,接著進(jìn)行解的選擇，更新相關(guān)參數(shù)并產(chǎn)生下一代解集.不同算法的具體更新迭代策略有所不同:

1) 遺傳算法[2-6]通過父染色體之間的交叉、變異產(chǎn)生新個(gè)體,然后采用選擇策略(輪盤賭、錦標(biāo)賽選擇等)結(jié)合目標(biāo)函數(shù)值從父個(gè)體和新個(gè)體中選擇最優(yōu)個(gè)體組成子種群.

2) 粒子群算法[7-9]中,粒子通過跟蹤兩個(gè)極值更新自身,分別為個(gè)體最佳極值Pbest和全局最佳極值Gbest.粒子更新后即產(chǎn)生新一代粒子群,然后計(jì)算新一代粒子群的目標(biāo)函數(shù)值,并以此更新Pbest和Gbest.

2.3 基于多目標(biāo)評估的輸送線布局算法

每次更新設(shè)備位置后進(jìn)行輸送線的布局.本文使用基于多目標(biāo)評估的路徑搜索算法實(shí)現(xiàn)不同設(shè)備之間的布線,并根據(jù)具體問題對其進(jìn)行改進(jìn).下面介紹輸送線布局算法過程:

1) 構(gòu)造路徑點(diǎn)矩陣用于尋路.一般采用等間隔劃分二維網(wǎng)格的方式構(gòu)造路徑點(diǎn)矩陣,而在本文問題中,因設(shè)備位置可以連續(xù)變化,難以確定間隔的粒度,故本文選擇利用設(shè)備布局的信息,通過提取布局關(guān)鍵點(diǎn)構(gòu)造路徑點(diǎn)矩陣.如圖5所示,選擇每個(gè)設(shè)備的中心點(diǎn)、出入口點(diǎn)和外圍邊界點(diǎn),并得到各點(diǎn)的x軸和y軸坐標(biāo),通過x軸坐標(biāo)和y軸坐標(biāo)交叉組成二維點(diǎn)陣,即可構(gòu)造一個(gè)路徑點(diǎn)矩陣.

圖5 路徑點(diǎn)矩陣構(gòu)造Fig.5 Path point matrix construction

2) 遍歷1)中的路徑點(diǎn)矩陣,檢測路徑點(diǎn)是否與任意設(shè)備范圍重疊,若存在重疊則將其標(biāo)記為障礙點(diǎn),否則標(biāo)記為可行點(diǎn).

3) 遍歷所有物料的設(shè)備路線,調(diào)用多目標(biāo)評估路徑搜索算法得到一條最短路徑,同時(shí)記錄路徑信息,路徑信息包括路徑起始點(diǎn)、終點(diǎn)和轉(zhuǎn)彎點(diǎn)參數(shù).

由于輸送線路徑只允許水平和垂直方向,可能會(huì)出現(xiàn)部分線路拐點(diǎn)過多的情況.如圖6所示,A→D→C的距離和A→B→C相等,按照原算法的搜索策略會(huì)導(dǎo)致兩者均可能被選擇為路徑,為解決該問題,本文進(jìn)行了以下兩步優(yōu)化:

圖6 拐點(diǎn)數(shù)不同的多條等長路線Fig.6 Multiple equally long routes with different numbers of turning points

a) 添加路徑方向?qū)傩訢cur表示當(dāng)前路徑的方向,Dcur有水平和垂直兩個(gè)取值,每次搜索當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)時(shí),優(yōu)先添加方向和Dcur一致的節(jié)點(diǎn);

b) 修改路徑搜索的成本評估函數(shù):

F(n)=G(n)+H(n)+E(n).

(11)

其中,G(n)和H(n)為預(yù)期路徑成本,E(n)為路徑轉(zhuǎn)彎成本.這樣,在G(n)與H(n)之和相等時(shí),由于轉(zhuǎn)彎點(diǎn)多了E(n)的成本,算法便會(huì)優(yōu)先選擇非轉(zhuǎn)彎點(diǎn)加入路徑.完成輸送線布局后,即可得到所有設(shè)備之間的運(yùn)輸距離,再根據(jù)式(1)計(jì)算出物料搬運(yùn)總成本.

2.4 處理布局約束

2.4.1 關(guān)鍵設(shè)備布局約束

關(guān)鍵設(shè)備布局約束如式(3)～(7)所示,包括設(shè)備位于車間內(nèi)約束和設(shè)備非重疊約束,前者為線性約束,通過設(shè)置每個(gè)坐標(biāo)的上下邊界即可實(shí)現(xiàn).后者為非線性約束不好處理.本文綜合使用設(shè)備位置調(diào)整策略和罰函數(shù)法處理該約束.

設(shè)備位置調(diào)整方法如下:

1) 將設(shè)備按尺寸從小到大排序;

2) 遍歷所有設(shè)備,檢測是否有重疊情況,若無,進(jìn)入步驟5),若存在設(shè)備與當(dāng)前設(shè)備D1重疊,進(jìn)入步驟3);

3) 檢測第一個(gè)與D1重疊的設(shè)備,記為D2,通過將D1移出與D2的重疊范圍來消除二者的重疊.具體地,規(guī)定D1只能向x和y的負(fù)方向移動(dòng),計(jì)算D1在兩個(gè)方向上的移動(dòng)距離,并分別計(jì)算x軸距離與車間長度、y軸距離與車間寬度的比值,選擇比值小的方向作為移動(dòng)方向,從而避免設(shè)備范圍溢出車間.通過不斷移動(dòng)D1,消除D1和其他設(shè)備的重疊;

4) D1的移動(dòng)可能會(huì)導(dǎo)致新的重疊,如圖7(a)所示,設(shè)備2在消除與設(shè)備3的重疊后,與設(shè)備1又發(fā)生了重疊.故每次消除D1的重疊后,仍需重新遍歷所有設(shè)備,并逐一消除重疊,防止順序在前的設(shè)備出現(xiàn)了新的重疊;

圖7 設(shè)備重疊調(diào)整和坐標(biāo)修正Fig.7 Overlap adjustment and coordinate correction of device

5) 計(jì)算所有設(shè)備的總包絡(luò)矩形范圍,在重疊全部消除后,設(shè)備的位置可能超出車間范圍,如圖7(b)所示.若該范圍小于車間范圍,給包絡(luò)矩形中心設(shè)置一個(gè)車間內(nèi)的隨機(jī)坐標(biāo),并同步修改所有設(shè)備的坐標(biāo);若范圍超出車間范圍,調(diào)整失敗,轉(zhuǎn)而采用罰函數(shù)法.

罰函數(shù)法是一種常用的處理非線性約束的方法[22].具體的,在1)調(diào)整失敗后給目標(biāo)函數(shù)設(shè)置一個(gè)大的正數(shù)作為懲罰值.

2.4.2 輸送線布局約束

輸送線約束如式(8)和(9)所示,本文綜合使用設(shè)備位置調(diào)整策略和罰函數(shù)法處理非重疊約束.

首先介紹設(shè)備位置調(diào)整方法.在本文問題中,不合理的設(shè)備布局會(huì)導(dǎo)致輸送線布局失敗.通過歸納設(shè)備間各種不合理的相對位置,并針對每種情況制定調(diào)整方案,主要是通過移動(dòng)設(shè)備消除不合理位置.圖8中列出了部分不合理情況及其調(diào)整方案.具體調(diào)整過程如下:

1) 取出兩個(gè)有連接關(guān)系的設(shè)備,判斷兩者相對位置是否合理,若不合理,進(jìn)入步驟2),否則繼續(xù)步驟1),若所有設(shè)備相對位置均合理,調(diào)整結(jié)束;

2) 根據(jù)相對位置的類型選擇方案對其進(jìn)行調(diào)整.不同方案的策略相似,即通過平移兩個(gè)設(shè)備,使得輸送線中間的不合理部分被消除.以圖8(b)中第一個(gè)圖為例,讓兩個(gè)設(shè)備的出入口點(diǎn)在x軸上對齊,即可消除過短的輸送線路.接著返回步驟1).

圖8 設(shè)備間不合理相對位置及其調(diào)整Fig.8 Unreasonable relative position of devices and its adjustment

罰函數(shù)法則是通過檢測所有線路的輸送線長度,若發(fā)現(xiàn)存在輸送線長度過短、輸送線之間距離過短的情況,給其目標(biāo)函數(shù)設(shè)置一個(gè)大的正數(shù)作為懲罰值.

3 實(shí)驗(yàn)及分析

為了驗(yàn)證本文算法的有效性,本文選擇了3個(gè)車間布局實(shí)例進(jìn)行實(shí)驗(yàn)分析.其中實(shí)例1為一個(gè)倉儲(chǔ)物流車間,其中有若干多入口多出口設(shè)備,用于驗(yàn)證本文算法對于解決這類布局問題的有效性.車間詳細(xì)參數(shù)見附錄(http:∥jxmu.xmu.edu.cn/upload/20210412.html)表S1和S2.實(shí)例2來自于文獻(xiàn)[9]中的SFLP-1,實(shí)例3來自于文獻(xiàn)[2],3個(gè)實(shí)例的部分參數(shù)見附錄表S3.由于本文研究的是關(guān)鍵設(shè)備與輸送線的混合布局,所以對布局?jǐn)?shù)據(jù)進(jìn)行了修改:

1) 添加了輸送線參數(shù)、設(shè)備的出入口參數(shù),輸送線參數(shù)如附錄表S4所示.對于設(shè)備出入口參數(shù),除實(shí)例1以外,其他實(shí)例中設(shè)備均設(shè)置為單入單出,且出口和入口分別位于設(shè)備默認(rèn)朝向的上方和下方;

2) 除實(shí)例1以外,其他實(shí)例均沒有車間出入口參數(shù);

3) 添加了設(shè)備之間的距離約束,具體地,設(shè)備4個(gè)方向的禁區(qū)距離均設(shè)為2.5 m;

4) 修改了車間的尺寸,詳見附錄表S3.

本文分別使用傳統(tǒng)設(shè)備布局方法(基于MOPSO和NSGA2實(shí)現(xiàn))以及本文中的混合算法(MOPSO-Route和NSGA2-Route)對3個(gè)實(shí)例進(jìn)行實(shí)驗(yàn).為保證對比的有效性,控制MOPSO與MOPSO-Route,以及NSGA2與NSGA2-Route的算法參數(shù)完全一致.由于傳統(tǒng)設(shè)備布局方法中不涉及輸送線部分,所以只關(guān)注物料搬運(yùn)總成本這一目標(biāo).同時(shí),由于傳統(tǒng)設(shè)備布局方法中輸送長度按照理想的曼哈頓距離計(jì)算,不符合實(shí)際輸送線布局,無法直接與本文算法的結(jié)果對比.所以使用傳統(tǒng)布局算法得到布局結(jié)果后,需計(jì)算出考慮實(shí)際路徑下的輸送線路長度,然后用該實(shí)際長度計(jì)算出物料搬運(yùn)總成本,方可進(jìn)行對比.

本文算法基于C++實(shí)現(xiàn),對于每個(gè)實(shí)例,每種算法獨(dú)立運(yùn)行10次,然后取平均值,結(jié)果如表2所示.表3給出了每種算法運(yùn)行10次的平均運(yùn)行時(shí)間.圖9中給出了每種算法的部分布局結(jié)果圖.

表2 實(shí)例1～3在4種算法下的實(shí)驗(yàn)結(jié)果Tab.2 The experimental results of example 1-3 under four algorithms

由表2可知,在3個(gè)實(shí)例的實(shí)驗(yàn)中,本文的兩種混合算法的布局結(jié)果均優(yōu)于傳統(tǒng)設(shè)備布局算法.

分析表3結(jié)果,由于混合布局算法結(jié)合了多目標(biāo)優(yōu)化算法和基于路徑搜索的布線算法,所以其計(jì)算時(shí)間較長.混合布局算法中，較耗時(shí)的操作主要包括每次迭代時(shí)解的更新和布線過程.且根據(jù)表中數(shù)據(jù)可知,在迭代次數(shù)相同時(shí),NSGA2-Route算法的運(yùn)行效率要低于MOPSO-Route算法.

分析圖9結(jié)果,混合算法布局結(jié)果滿足了設(shè)備和輸送線的各項(xiàng)約束;從圖9中的圓圈標(biāo)記處可以看出,傳統(tǒng)方法得到的布局會(huì)出現(xiàn)輸送線路長度過短、輸送線之間發(fā)生沖突的情況,其布局結(jié)果不具有可行性.

圖9 混合算法布局結(jié)果Fig.9 Hybrid algorithm layout results

4 結(jié)論和展望

物流場景中同時(shí)存在關(guān)鍵設(shè)備和輸送線設(shè)備,而傳統(tǒng)設(shè)備布局方法中只適用于關(guān)鍵設(shè)備的布局.本文針對該問題,提出了一個(gè)結(jié)合多目標(biāo)元啟發(fā)式優(yōu)化方法和布線算法的混合布局算法框架,同時(shí)針對設(shè)備位置連續(xù)變化和混合布局的特點(diǎn),提出了處理關(guān)鍵設(shè)備和輸送線約束的策略.接著,本文分別使用MOPSO和NSGA2作為元啟發(fā)式算法,使用改進(jìn)的多目標(biāo)評估的路徑搜索算法作為布線算法,在混合算法框架下實(shí)現(xiàn)了MOPSO-Route和NSGA2-Route兩個(gè)具體算法,并通過與傳統(tǒng)設(shè)備布局算法(基于MOPSO[7]和NSGA2[21])的對比,驗(yàn)證了本文算法在解決物流場景中混合布局問題上的優(yōu)越性.未來可以進(jìn)一步提高算法效率,實(shí)現(xiàn)對于更大規(guī)模物流場景的高效布局.

表3 算法運(yùn)行時(shí)間