基于多縱向傳輸通道的雙層過道布置問題建模與優(yōu)化

劉俊琦，張則強，管 超，龔舉華

(西南交通大學(xué) 機械工程學(xué)院，四川 成都 610031)

1 問題的提出

設(shè)施布局問題(Facility Layout Problem，F(xiàn)LP)是一種經(jīng)典的運籌學(xué)難題，其以最小化物流成本為目標(biāo)[1]對設(shè)施進行合理的組合排序，并作為當(dāng)前制造業(yè)發(fā)展的重要內(nèi)容，存在于多種類型的制造和服務(wù)系統(tǒng)[2-6]，如制造業(yè)中的生產(chǎn)車間布局[5]、服務(wù)業(yè)中的辦公區(qū)域布局[7]、醫(yī)院走廊兩側(cè)病房的安置[8]，布局優(yōu)化是否合理直接影響作業(yè)效率和運作成本。因此，近幾十年來，F(xiàn)LP一直受到制造業(yè)、服務(wù)業(yè)和學(xué)術(shù)界的廣泛關(guān)注[9-10]。

過道布置問題(Corridor Allocation Problem, CAP)[11]是FLP的一種形式，其模式與雙行布局問題(Double Row Facility Layout Problem, DRFLP)[12-13]比較相似(如圖1和圖2)，兩者的區(qū)別在于CAP遵循以下兩個約束：①上下兩行的布置起點均為通道的最左邊，即坐標(biāo)原點；②相鄰兩個設(shè)施之間沒有間隙。CAP是一種典型的具有NP-hard屬性的組合優(yōu)化問題，擴大問題規(guī)模和增加約束條件均會大大增加精確求解的難度，由于具有較高的研究價值和廣闊的實際應(yīng)用前景，CAP自提出以來便快速成為設(shè)施布局領(lǐng)域的研究熱點。

AMARAL[11]于2012年首次提出并建立了CAP的混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)模型，并以設(shè)施間總物流成本最小為優(yōu)化目標(biāo)提出3種啟發(fā)式算法，分別對其進行求解測試，驗證了該模型的正確性和算法的有效性；GHOSH等[14]采用改進遺傳算法和分散搜索算法(Scatter Search, SS)分別對CAP的不同規(guī)模問題進行測試，進一步提高了求解該問題的運算效率；AHONEN等[15]分別采用禁忌搜索(Tabu Search,TS)算法和改進模擬退火(Simulated Anneal, SA)算法對CAP大規(guī)模問題進行求解，兩種算法均可得到當(dāng)前最優(yōu)解，經(jīng)對比，改進SA算法在求解效率和求解質(zhì)量上均優(yōu)于TS算法；KALITA等[16-17]在原始CAP模型的基礎(chǔ)上，考慮通道總長度，在原CAP模型中增加最小化通道長度的優(yōu)化目標(biāo)，建立了非線性雙目標(biāo)優(yōu)化問題數(shù)學(xué)模型，即設(shè)施總長度與設(shè)施間物流總成本最優(yōu)，并分別應(yīng)用基于序列置換遺傳算法和改進遺傳算法對標(biāo)準(zhǔn)算例進行測試，驗證了兩種算法的有效性。上述文獻研究的CAP均為單層問題，然而在實際工業(yè)制造領(lǐng)域或服務(wù)部門中，當(dāng)設(shè)施數(shù)量過于龐大且布局面積受限時，為了提高空間利用率、降低成本，越來越多的多層空間布局被采用，為了更好地結(jié)合實際情況，管超等[18]提出并構(gòu)建了雙層過道布置問題(Double Floor Corridor Allocation Problem ,DFCAP)MIP模型，隨后采用花授粉算法進行求解[19]，驗證了所提MIP模型的正確性以及算法的有效性；為了更好地貼合實際，管超等[20]在初始DFCAP的基礎(chǔ)上考慮通道寬度對CAP的影響，建立了混合整數(shù)非線性規(guī)劃模型，并采用改進SA算法進行算例測試，結(jié)果表明改進抽樣過程的SA算法能夠很好地求解所提問題。隨著多樓層設(shè)施布局在實際生產(chǎn)生活中應(yīng)用的增多，而且傳統(tǒng)單貨梯存在一定的運輸成本浪費，越來越多的智能加工車間采用多縱向傳輸通道運輸?shù)姆绞剑鐖D3所示(某企業(yè)多通道雙層縱向運輸機)。參考已有文獻,尚未發(fā)現(xiàn)有關(guān)多縱向傳輸通道運輸方式CAP研究的報道，因此本文以DLCAP為基礎(chǔ)，提出一種基于多縱向傳輸通道的拓展雙層過道布置問題(Extend Double Floor Corridor Allocation Problem ,EDFCAP)，并采用LINGO優(yōu)化器對所提模型進行精確求解，為后續(xù)模型與算法的驗證提供理論依據(jù)。

SA算法和TS算法為近年來國內(nèi)外均比較關(guān)注的算法[15,21-22]，兩種算法在求解NP-hard屬性問題上均具有良好的求解性能，如路徑規(guī)劃問題[23-24]、0-1背包問題[25-26]和車間調(diào)度問題[27]等。除此之外，兩種算法均在CAP方向得到廣泛應(yīng)用，如CAP[15]、圓環(huán)CAP[28]。傳統(tǒng)的TS算法利用禁忌表鎖住部分最優(yōu)解，有意識避開已找到的局部最優(yōu)解，從而搜索更多區(qū)域，其全局能力較強，但對初始解的要求較高，而傳統(tǒng)SA算法對初始解的要求則不高。因此，結(jié)合問題特征，本文根據(jù)兩種算法的特性和優(yōu)點對兩種算法進行混合改進(帶有禁忌搜索操作的模擬退火算法(Simulated Annealing algorithm with Tabu search, TSA))，使其在降低初始解的前提下提高全局搜索的概率。最后，為更好地說明所提算法的性能，將TSA與多種算法求解不同類型CAP的結(jié)果對比，表明TSA在求解精度與效率方面更勝一籌。

2 考慮多縱向通道的EDFCAP數(shù)學(xué)模型

2.1 問題描述

本文旨在考慮設(shè)施布置在場地所用面積有限及單一縱向運輸通道存在浪費等問題對設(shè)施布局的影響，在文獻[17]的基礎(chǔ)上提出基于多縱向傳輸通道的EDFCAP。在基本DFCAP中，兩個樓層之間的交互通道為最左側(cè)的貨梯，而EDFCAP是在2層的每一個物流交互點處設(shè)置一個與1層交互的縱向通道，并在每個通道處安裝往復(fù)式升降機(如圖4)，而且縱向運輸通道數(shù)量與上層設(shè)施數(shù)量相同。EDFCAP同初始DFCAP一樣，分別在1層和2層通道的左右兩側(cè)布置設(shè)施，并按照設(shè)施之間的物流關(guān)系對設(shè)施進行排序，從而最小化總物流成本。

2.2 基本假設(shè)條件

(1)假設(shè)條件

1)已知每個設(shè)施在X軸方向上的長度與各個設(shè)施間的物流量，設(shè)施的形狀為大小不等的矩形。

2)每個設(shè)施的物流交互點為該設(shè)施靠近過道邊線的設(shè)施長度中點。

3)排列在通道兩側(cè)的設(shè)施數(shù)目已知，上下兩行設(shè)施坐標(biāo)均符合笛卡爾坐標(biāo)系，最左側(cè)起始點為坐標(biāo)軸原點O。

4)相鄰兩個設(shè)施間沒有間隙，且每層設(shè)施之間的通道寬度為0。

5)不同層的設(shè)施之間通過可移動升降貨梯進行物流交互，假設(shè)貨梯的寬度和長度均為0，僅考慮其升降高度，且升降高度h為已知量(h=10)。

6)各個設(shè)施之間的物料搬運長度采用曼哈頓距離計量。

(2)定義參數(shù)和變量

F為樓層集合，F(xiàn)={1,2}；

f為樓層編號，f∈F；

n為問題的規(guī)模；

Nf為f層設(shè)施的集合；

i,j,s為設(shè)施的編號；

cij為設(shè)施間的單位距離物流成本；

nf為布置在第f層的設(shè)施數(shù)目；

Rf,i為布置在第f層的第i個設(shè)施，f∈F；

dRf,i,Rf,j為f層的設(shè)施i與j之間的物流交互點在水平方向的距離；

li為設(shè)施在通道邊線方向上的長度；

αij為二進制變量,如果設(shè)施i,j分配在同一行,且設(shè)施i被放置在設(shè)施j的左側(cè),則αij= 1，否則αij= 0。

2.3 考慮上下兩層設(shè)施交互點位置距離約束條件

(1)基本DFCAP路徑分析

基本DFCAP將貨梯放在通道的最左側(cè)，其兩層設(shè)施之間的路徑如圖5所示。

對于DFCAP，其設(shè)施的相對位置具有和傳統(tǒng)單層CAP相同的性質(zhì)，即均以坐標(biāo)原點為起點，以X軸正方向沿通道兩側(cè)布置，且相鄰兩個設(shè)施之間無間隙，因此其第1層與第2層設(shè)施坐標(biāo)可表示為：

設(shè)施i與設(shè)施s的物流交互距離dR1,iR2,s的約束條件為

(1)

(2)EDFCAP路徑分析

EDFCAP采用移動升降貨梯進行運輸，其運輸路徑如圖6所示。

在EDFCAP中，任意兩個設(shè)施之間的距離為dR1,iR2,s=h+|xR1,i-xR2,s|，因為在求解過程中，dR1,iR2,s均存在取值上限，所以將距離約束條件等價為dR1,iR2,s≥h+|xR1,i-xR2,s|，從而分解為如下線性約束條件：

(2)

(3)

2.4 基于移動貨梯的雙層過道布置問題數(shù)學(xué)模型

基于上述符號定義與問題描述，完整的EDFCAP的數(shù)學(xué)模型如下：

(4)

(5)

(6)

(7)

(8)

(9)

-αRf,iRf,j+αRf,iRf,k+αRf,jRf,k-αRf,jRf,i+
αRf,kRf,i+αRf,kRf,j≤1,
i,j,k∈Nf,i

(10)

-αRf,iRf,j+αRf,iRf,k-αRf,jRf,k+αRf,jRf,i-
αRf,kRf,i+αRf,kRf,j≤1,
i,j,k∈Nf,i

(11)

αRf,iRf,j+αRf,iRf,k+αRf,jRf,k+αRf,jRf,i+
αRf,kRf,i+αRf,kRf,j≥1,
i,j,k∈Nf,i

(12)

αRf,iRf,j∈{0,1},
1≤i,j≤n,i≠j,f∈F。

(13)

3 求解拓展雙層過道布置問題的TSA

針對所提EDFCAP求解的復(fù)雜性，本文提出一種以SA算法為主體框架的融合2-Opt路徑重連策略、記憶功能、禁忌搜索操作、inversion操作的TSA，以穩(wěn)定地求得全局最優(yōu)解。

3.1 編碼、解碼與2-opt路徑重連策略

(1)編碼與解碼

針對EDFCAP的特征，本文采用實數(shù)編碼設(shè)施序列，并對所編碼的設(shè)施序列進行解碼。以n= 11的經(jīng)典算例為例，假定其中某一可行解的序列編碼為[11 9 7 5 3 1 6 8 4 2 10]，若給定奇數(shù)號碼的設(shè)施布置在第1層，偶數(shù)號碼的設(shè)施布置在第2層，則第1層布置6個設(shè)施，第2行布置5個設(shè)施。每一層設(shè)施為整體設(shè)施序列的子序列，則解碼的子序列可以劃分為第1層第1行[11 9 7]與第1層第2行[5 3 1]、第2層第1行[6 8 4]與第2層第2行[2 10]，上述可行解的整數(shù)編碼與解碼過程如圖7所示。

(2)2-Opt序列重連策略

為了更好地產(chǎn)生新的解序列，達到充分搜索鄰域空間的目的，在原2-opt基礎(chǔ)上對所產(chǎn)生的第1層新解和第2層新解進行序列重連，如圖8所示。

相比于傳統(tǒng)2-opt操作產(chǎn)生n個解序列，重連操作產(chǎn)生的解序列數(shù)為n2個，極大地增加了解的多樣性；同時，在確定層與層之間布置的設(shè)施序編號不發(fā)生混亂的前提下，僅當(dāng)新解的適應(yīng)度值優(yōu)于當(dāng)前最優(yōu)解時，輸出新解。

3.2 記憶功能

傳統(tǒng)SA算法收斂于全局最優(yōu)解的關(guān)鍵在于Metropolis準(zhǔn)則能以一定概率接受惡化解，使算法跳出局部最優(yōu)，為避免在一定概率接受惡化解同時發(fā)生丟失當(dāng)前最優(yōu)解的情況，在SA算法中嵌入記憶功能，用于記錄當(dāng)前最優(yōu)解。在進行模擬退火操作之初，記錄初始解序列s0，并令xopt=s0，f(xopt)=f(s0)，在執(zhí)行每一次Metropolis準(zhǔn)則后，比較當(dāng)前產(chǎn)生的可行解序列stemp對應(yīng)的適應(yīng)度值f(stemp)與歷史最優(yōu)解f(xopt)。若f(stemp)

3.3 禁忌搜索操作

采用具有局部搜索能力較強的全局迭代算法——TS算法改善SA算法的給定解，TS算法的操作步驟如圖9所示。TS算法中：①鄰域解的構(gòu)成采用本文所提2-opt路徑重連策略，并從所構(gòu)成的鄰域解中挑選候選解；②特赦準(zhǔn)則為基于適應(yīng)度值準(zhǔn)則，即從當(dāng)前鄰域解中集中挑選候選解，并從候選解集中挑取最佳候選解，如果最佳候選解的適應(yīng)度值優(yōu)于歷史最優(yōu)值，達到best so far 狀態(tài)，則藐視該解的禁忌特性，接受該解，并將其所對應(yīng)適應(yīng)度值作為禁忌對象加入禁忌表，同時更新禁忌表中其他禁忌對象的禁忌長度，作為TS算法中的核心策略，特赦準(zhǔn)則增強了算法局部搜索性能，提高了獲得全局最優(yōu)解的概率；③算法中的禁忌對象為設(shè)施布置序列對應(yīng)的適應(yīng)度值；④兼顧求解時間和求解效率，經(jīng)過多次求解測試，所提算法中TS算法的操作參數(shù)禁忌長度Tlength=round((n(n-1)/2)0.5)；⑤候選解集為鄰域解的真子集。

3.4 逆轉(zhuǎn)操作與終止準(zhǔn)則

為了避免算法陷入局部最優(yōu)，每次結(jié)束禁忌搜索操作后，記錄當(dāng)前最優(yōu)解序列xbest，分別對輸出的最優(yōu)解對應(yīng)序列的第1層和第2層進行inversion擾動(在每一層對應(yīng)的序列中等概率隨機選取兩個不同的設(shè)施編碼，并對兩個設(shè)施編號中的所有設(shè)施進行逆轉(zhuǎn))，如圖10所示。同交叉算子相比，inversion擾動可以使子代在跳出局部最優(yōu)的同時最大程度地繼承父代信息。本文以最外層迭代次數(shù)K為終止條件，K的取值根據(jù)問題求解規(guī)模n及最優(yōu)值的穩(wěn)定程度確定，設(shè)置i為混合SA算法完整流程次數(shù)的計數(shù)器，若i>k則算法終止，輸出所記錄的最優(yōu)值f(xbest)和解序列xbest。

3.5 TSA步驟

TSA流程如圖11所示。

步驟1初始化參數(shù)，包括初始溫度T0、降溫速率q、結(jié)束溫度Tend、Metropolis鏈長L、最外層迭代次數(shù)K、禁忌搜索最大迭代次數(shù)Nmax。

步驟2隨機產(chǎn)生初始解S0。

步驟3令i=1，k=1，count=1，若i≤K則執(zhí)行步驟9，反之輸出xbest，f(xbest)。

步驟4執(zhí)行2-opt操作和Metropolies操作，同時開啟記憶功能，令k=k+1。

步驟5若k≤L，則執(zhí)行步驟4，否則執(zhí)行步驟6。

步驟6結(jié)束循環(huán)時，輸出記憶功能中記錄的xopt，f(xopt)，若count= 1，f(x0) =f(xopt)，x0=xopt，則執(zhí)行步驟8，否則執(zhí)行步驟7。

步驟7若f(xopt)

步驟8降溫T0=qT0，S0=x0。

步驟9若T0>Tend，則執(zhí)行步驟4，否則輸出x0，f(x0)。

步驟10執(zhí)行禁忌搜索操作，并輸出f(x0*)，x0*。

步驟11若f(x0*)

步驟12執(zhí)行inversion擾動操作。

步驟13i=i+ 1。

步驟14若i≤K，則初始化溫度T0，k=1，count=1并執(zhí)行步驟4，否則輸出xbest，f(xbest)。

4 實驗結(jié)果與分析

為了驗證所提EDFCAP數(shù)學(xué)模型的正確性，采用精確解優(yōu)化器LINGO對上述模型進行精確求解，本文實驗所采用的個人計算機硬件配置為 Intel(R) 酷睿 i5-8400、主頻 2.8 GHz、內(nèi)存 8 GB ，Windows10 操作系統(tǒng)。同時，為了驗證所提TSA的求解性能，采用MATLABR2016b進行求解測試，隨后將計算結(jié)果與文獻[18]的啟發(fā)式算法進行對比。為了避免問題參數(shù)的影響，選取與文獻[18]相同的問題參數(shù)，問題參數(shù)與算法參數(shù)設(shè)置如表1和表2所示。實際設(shè)施布置中占地面積最小的情況一般為：每一層設(shè)施數(shù)目相差較小，且每層中兩行設(shè)施數(shù)目相差較小。本文假設(shè)上下兩層設(shè)施數(shù)目均為定值，即第1層均布置編號為奇數(shù)的設(shè)施，第2層均布置編號為偶數(shù)的設(shè)施。然而對于本文所構(gòu)建的MIP模型，上下兩層設(shè)施數(shù)目和奇偶設(shè)施序號設(shè)施布置并不局限于上述假設(shè)。

表1 問題參數(shù)設(shè)置(問題規(guī)模25≤n≤36)

表2 算法參數(shù)設(shè)置

4.1 EDFCAP模型驗證

為了驗證所提模型的正確性，根據(jù)所構(gòu)建MIP數(shù)學(xué)模型的線性特性，應(yīng)用LINGO優(yōu)化器中的分支定界法對初始進行精確求解，測試算例S9，S9H，S10，S11，Am12，Am13，Am15，N25的運算時間Times分別為0，1，2，1.6，1，0.9，1.9，1.2，9.6，1 109.4(單位：s)。隨著問題規(guī)模的增加，LINGO優(yōu)化器求解過程中無法在較合理的時間內(nèi)對大規(guī)模算例進行高效求解，因此為了給所提TSA求解結(jié)果提供參考，針對大于25規(guī)模的算例，將其運算時間設(shè)置在600 s，600 s后仍未求得結(jié)果則用“-”表示。對比表3的數(shù)據(jù)可知，針對小規(guī)模基準(zhǔn)算例，TSA求得的最優(yōu)解與精確算法求得的精確解相同，驗證了所提模型與算法的正確性。

表3 LINGO精確解與TSA對EDFCAP的求解結(jié)果

4.2 TSA驗證

為了說明TSA具有較好的求解性能與一定的普適性，結(jié)合DFCAP和CAP，選取9～49規(guī)模算例中的若干個算例進行驗證，將TSA求解DFCAP和CAP的結(jié)果分別與C2Opt算法[18]求解DFCAP的結(jié)果、改進花授粉算法(Improved Discrete Flower Pollination Algorithm，IDFPA)[19]和改進的煙花算法(Improve Fireworks Algorithm，IFWA)[29]求解CAP的結(jié)果進行對比，如表4和表5所示。

表4 TSA和C2Opt算法求解DFCAP的結(jié)果對比

表5 算法TSA，IDFPA，IFWA求解CAP的結(jié)果對比

由表4可知，C2Opt和TSA兩種算法的求解時間的增長均較平穩(wěn)，且對于sko-49-05問題，TSA的求解結(jié)果優(yōu)于C2Opt算法。由表5可知，對于小規(guī)模算例，3種算法求解出的目標(biāo)值相等；對于較大規(guī)模算例，除sko-49-05問題外，TSA的目標(biāo)值均可達到IDFPA和IFWA的目標(biāo)值，且在sko-42-04，sko-49-03問題上求得的目標(biāo)值更優(yōu)，因此TSA具有較高的求解質(zhì)量與普適性。

在驗證基本DFCAP后，進一步說明所提算法的高效性。由于所提算法包括SA算法和TS算法，應(yīng)用SA算法和TS算法分別求解所提EDFCAP，并與TSA進行對比，如表6所示。為了準(zhǔn)確測試算法性能，算法均重復(fù)運行60次，將最優(yōu)目標(biāo)值記錄在表中第3，5，7列。同時，為了更好地說明算法的穩(wěn)定性，針對每個測試問題，統(tǒng)計3種算法的60次運算結(jié)果并計算標(biāo)準(zhǔn)差SD，如表6中的4，6，8列所示。

表6 各算法求解EDFCAP的結(jié)果對比

由表6可知，在相同參數(shù)下，針對9～15規(guī)模問題，3種算法均可得到最優(yōu)解，但大于15規(guī)模后，TSA的求解質(zhì)量明顯優(yōu)于TS算法和SA算法；為了直觀地展現(xiàn)TSA的求解性能，將3種算法在不同規(guī)模下的求解標(biāo)準(zhǔn)差繪制成折線圖，如圖12所示。從圖中可見，除AKv-80-05問題外，TSA求解問題的標(biāo)準(zhǔn)差指標(biāo)均小于TS算法和SA算法，因此具有良好的求解穩(wěn)定性。

根據(jù)計算結(jié)果，選定Am15問題算例并繪制如圖13所示的迭代收斂圖。為了對比明顯，選用所含參數(shù)類別大致相同的SA算法做參照，將TSA和SA算法的參數(shù)設(shè)置為相同，由圖可見兩種算法的迭代收斂速度，當(dāng)兩種算法均可在有限次數(shù)內(nèi)迭代到相對最優(yōu)值時，TSA在59次時趨于平穩(wěn)狀態(tài)，SA算法則在94次時趨于穩(wěn)定。因此TSA收斂速度較快，具有較強的搜索性能。

5 結(jié)束語

鑒于DFCAP在實際生產(chǎn)生活中的廣泛應(yīng)用，本文探究了多縱向傳輸通道對DFCAP的影響，主要成果如下：

(1)構(gòu)建EDFCAP模型，利用LINGO優(yōu)化器對問題進行精確求解，驗證了所提問題模型的正確性。

(2)設(shè)計一種求解EDFCAP的TSA，該算法在SA中嵌入TS操作，采用2-opt序列重連的方式作為解的更新操作，極大地增強了算法的求解性能。

(3)應(yīng)用所提TSA求解EDFCAP，并將求解結(jié)果與精確求解結(jié)果進行對比，驗證了算法的有效性。

(4)將TSA應(yīng)用于DFCAP與CAP的求解測試，并分別與C2Opt，IDFPA，IFWA進行對比，結(jié)果表明，算法具有一定的普適性與高效性。另外，分別采用SA算法和TS算法求解EDFCAP，并與TSA的求解結(jié)果進行對比，結(jié)果表明TSA有效且相對于原算法顯著提升了求解性能。

未來可以在EDFCAP的基礎(chǔ)上考慮更多約束或目標(biāo)以滿足實際需求，同時利用TS算法與SA算法的優(yōu)勢，與其他算法混合來增強求解性能。