受約束的過道布置問題建模及優(yōu)化方法

劉俊琦，張則強，龔舉華，張 裕

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

設(shè)施布局問題（FLP）是制造系統(tǒng)中一項復(fù)雜且關(guān)鍵的研究內(nèi)容，其布局的合理程度與企業(yè)生產(chǎn)效率及運營成本密切相關(guān).一般而言，F(xiàn)LP主要研究設(shè)施在其所屬空間范圍內(nèi)的合理布置，使生產(chǎn)中的物流與信息流更為高效化，最終降低企業(yè)的布局成本及物流成本[1-2].

作為設(shè)施布局問題的一種特殊形式，過道布置問題（CAP）以及其混合整數(shù)規(guī)劃（MIP）模型由Amaral[3]在2012年首次提出并建立，隨后對CAP的MIP模型進行精確求解，但因CAP具有的NP-Hard特性，求解時間呈指數(shù)增長，因此Amaral提出了求解CAP的啟發(fā)式算法.為了高效計算更大規(guī)模問題，學(xué)者們開始探索啟發(fā)式方法，Ghosh與Kothari[4]應(yīng)用帶有局部搜索的遺傳 （GA）算法和結(jié)合路徑重連的分散搜索（SS）算法對CAP進行求解，對比兩種算法，在均能求解較優(yōu)的效果上，后者運行效率上更具優(yōu)勢.Ahonen等[5]對不同規(guī)模的CAP算例分別采用改進模擬退火 （SA）算法和禁忌搜索 （TS）算法進行測試，綜合分析兩種算法的求解質(zhì)量和求解時間后發(fā)現(xiàn)，模擬退火算法在求解性能上更具優(yōu)勢.隨著研究的深入，人們不斷地對CAP進行完善，使其更符合實際的生產(chǎn)生活情景.Kalita等[6-7]于2014年提出以最小化過道長度以及總物流成本為目標的無約束多目標過道布置問題，隨后在雙目標過道布置問題的基礎(chǔ)上加入相鄰設(shè)施間無間隙的約束，并采用改進GA對問題進行求解.Zhang等[8]考慮了實際情況下通道寬度對CAP的影響，建立了考慮通道寬度的CAP模型，隨后應(yīng)用改進SS求解；劉思璐等[9]提出考慮設(shè)施深度的過道布置問題并應(yīng)用煙花算法（IFWA）進行求解.在考慮CAP所用占地面積問題后，管超等[10-12]提出并改進雙層CAP模型，隨后分別應(yīng)用啟發(fā)式算法、改進花授粉算法（IDFPA）以及改進SA進行問題的測試，測試結(jié)果表示，在不同問題下幾種方法均可以有效地求解雙層CAP.劉俊琦等[13]提出考慮多縱向傳輸路徑的過道布置問題，并采用混合禁忌搜索的模擬退火算法進行求解，結(jié)果表明所提混合算法具有一定的先進性；王沙沙等[14]考慮帶有多路徑交互的環(huán)形過道布置問題并應(yīng)用蟻獅算法求解；陳鳳等[15]提出考慮設(shè)施方向的雙目標過道布置問題，并采基于Pareto占優(yōu)和模擬退火搜索的多目標分散搜索算法進行求解，結(jié)果表明所提算法對于雙目標過道布置問題有良好的求解效率.

上述研究對CAP問題進行了深入討論與完善，但CAP常常被作為無關(guān)系約束問題.Kalita等[16]在最新的cbCAP研究中提出考慮同行、非同行以及相反行3種約束的cbCAP，為受約束的過道布置問題奠定了基礎(chǔ).但是在實際生產(chǎn)或服務(wù)部門中，設(shè)施間除上述3種約束外，往往還存在著其他某種特殊的聯(lián)系.Liu等[17]在約束布局中指出，在醫(yī)院布局中將需要在各層間頻繁移動的部門放置在電梯口附近，將需要頻繁在部門間移動的部門放置在同一層可以極大程度地減少運輸成本.在傳統(tǒng)車間的零部件加工過程中，工序間存在優(yōu)先順序，如果在某個工序前存在未完成的緊前工序[18]，則該工序?qū)蛭赐瓿傻木o前工序而被停滯，例如拆卸線平衡問題中的緊前任務(wù)關(guān)系[19].Kalita等[20]提出的基于順序靈活性的制造系統(tǒng)中指出：產(chǎn)品的制作順序可以通過執(zhí)行某些操作而變化，而其他的操作不受任何優(yōu)先約束的限制.在柔性更強的制造車間中，部分操作的排序更為普遍.對存在操作排序工序的設(shè)施應(yīng)當(dāng)滿足優(yōu)先關(guān)系布置，對無優(yōu)先順序約束操作涉及的設(shè)施則以合理的順序布置[21]，并最小化設(shè)施間的總物流成本.因此，在CAP中考慮設(shè)施間的相互關(guān)系具有十分重要的意義.

克隆選擇 （CSA）算法和禁忌搜索算法是近年來國內(nèi)外均比較關(guān)注的算法[22-27].兩種算法在求解具有NP-hard屬性的問題上均有良好的求解性能，如路徑規(guī)劃問題[24]和裝配線平衡問題[21]等組合優(yōu)化問題.除此之外，兩種算法也均在設(shè)施布局方向上得到廣泛應(yīng)用，如雙行布局問題[26]、圓環(huán)過道布置問題[23].傳統(tǒng)的克隆選擇算法其并行性較高，但容易較早地陷入局部最優(yōu)，而禁忌搜索算法可以利用禁忌表鎖住部分最優(yōu)解，有意識地避開，從而搜索更多區(qū)域，其全局搜索能力較強.因此，本文考慮兩種算法的特性及優(yōu)點并進行混合，提出一種自適應(yīng)禁忌克隆選擇算法（ACSATS）.將禁忌搜索操作作為克隆選擇算法的局部搜索操作，并在變異操作中設(shè)置自適應(yīng)變異概率.利用克隆變異與選擇操作實現(xiàn)種群的擴張與收縮，提高全局搜索的概率.

1 受約束過道布置問題模型

1.1 問題描述

CAP根據(jù)設(shè)施的具體排布來確定各個設(shè)施的精確位置以及設(shè)施間的相對位置關(guān)系，圖1為過道布置問題設(shè)施之間距離的計算方式，圖1中：xi為設(shè)施i的位置坐標；dij為設(shè)施i到設(shè)施j的距離.在實際布局活動中，設(shè)施間會存在較為復(fù)雜的關(guān)系，會映射在布局中并影響整體物流成本.因此，本文在傳統(tǒng)過道布置問題中加入固定設(shè)施位置及排序約束，將其拓展為受約束的過道布置問題（CCAP）.該問題的提出使過道布置問題更加貼合實際，為過道布置問題在實際應(yīng)用中提供了一定的理論依據(jù).

圖1 過道布置問題距離計算方式Fig.1 Distance calculation method of CAP

1.2 基本假設(shè)條件

1）設(shè)施形狀為規(guī)則矩形，且相鄰設(shè)施間沒有間隙；

2）設(shè)施靠近過道邊線的長度以及設(shè)施間的單位距離物流交互成本為已知量；

3）各個設(shè)施的物流交互點位于設(shè)施靠近通道一側(cè)的設(shè)施邊線中點；

4）上、下兩行設(shè)施間的通道寬度為所有設(shè)施中設(shè)施長度的最小值；

5）上、下兩行設(shè)施均從最左邊的同一水平線開始布置，該水平線可看作在X軸方向坐標為0的點所對應(yīng)的線；

6）設(shè)施布置情況不受區(qū)域大小以及其他條件限制.

1.3 新增約束條件

在文獻[3]所論述的過道布置問題模型的基礎(chǔ)上，結(jié)合實際情況下車間、醫(yī)院和商場等設(shè)施布置情況，以最小化總物料搬運成本為目標，將給定設(shè)施沿通道兩側(cè)進行布置，并滿足以下兩種類型的約束.

1）定位約束：設(shè)施將被放置在指定位置.

2）排序約束：某種設(shè)施因自身所帶屬性或與其他設(shè)施具有一些特殊關(guān)系，從而使其與其他設(shè)施存在位置上的相對關(guān)系，此處的排序約束假定為考慮位置上的先后關(guān)系.

1.4 CCAP的數(shù)學(xué)模型

在數(shù)學(xué)模型中所應(yīng)用到表示參數(shù)以及決策變量的符號如表1所示.

表1 參數(shù)名稱與定義Tab.1 Parameter names and definition

CCAP完整的數(shù)學(xué)模型為

Objective function

式（2）與式（3）用于計算各物料搬運點之間在水平軸方向上的物流交互點之間距離；式（4）防止同行的設(shè)施布置出現(xiàn)重疊的情況；式（5）～ （7）確定決策變量αij；式（8）確定決策變量qij；式（9）與式（10）給定決策變量αij與qij的定義域.

式（11）表示上述約束中的排序約束；式（12）確定定位約束中的決策變量βhi；式（13）表示定位約束，表示設(shè)施i的物流交互點位置坐標排列在第(C+ 1)個位置；式（14）表示決策變量βhi的定義域.

CCAP的問題特性延續(xù)了基本CAP的NP-hard屬性，對于基本CAP的求解難度已經(jīng)較大，其整數(shù)線性規(guī)劃模型的精確求解難度隨著問題規(guī)模n和約束條件的增加呈指數(shù)級增長，而CCAP在原問題的基礎(chǔ)上加入兩種約束，模型的性質(zhì)發(fā)生實質(zhì)改變，相較于基本問題其精確求解難度更高，因此，對于受約束的過道布置問題，可以利用啟發(fā)式方法以尋求在允許時間內(nèi)獲得近似最優(yōu)值.

2 混合禁忌搜索的克隆選擇算法

傳統(tǒng)的CSA存在局部搜索精度不高的現(xiàn)象，因此，本文對CSA進行改進：將基于兩種約束的適配2-opt操作、禁忌搜索操作以及自適應(yīng)變異概率加入到CSA中，使其更好地求解所提問題.

2.1 編碼、解碼與基于兩種約束的2-opt操作

1）編碼與解碼

設(shè)施的編碼方式采用基于設(shè)施編碼序列的整數(shù)編碼方式進行定義，每個抗體由一組多維實數(shù)向量來表示，向量中每一維度上的數(shù)字表示相應(yīng)設(shè)施的編號.每一個抗體代表一種布局方案，設(shè)施的解碼則根據(jù)問題特性將序列一分為二，第一段表示上行，第二段表示下行.

2）基于兩種約束的2-opt操作

為了克服CSA局部搜索能力較弱的問題以及為后續(xù)的禁忌搜索操作提供較好的初值，在克隆變異之前對選擇的初始抗體進行基于約束的2-opt操作，基于約束的2-opt操作避免了傳統(tǒng)變異操作會產(chǎn)生大量不滿足約束要求的解，大幅度提高了算法的求解效率.2-opt操作后的集合為AG_1.具體的2-opt操作如圖2，以S9測試問題為例.與此同時，設(shè)施約束規(guī)則擬定為

圖2 基于兩種約束的2-opt操作示意Fig.2 Improved 2-opt operation diagram based on two kinds of constraints

1）4號設(shè)施為定位約束，位置位于總物料搬運點的倒數(shù)第二位置；

2）1號設(shè)施與5號設(shè)施為關(guān)系約束，關(guān)系為1號設(shè)施物料搬運點位于5號設(shè)施物料搬運點之前.

2.2 基于禁忌搜索的自適應(yīng)變異操作

在對2-opt更新的抗體進行克隆后，對克隆的抗體進行變異操作，相較于傳統(tǒng)的變異操作，本文進行了相應(yīng)的改進，分別用禁忌搜索算子與自適應(yīng)變異算子組合的方式進行變異操作：

1）禁忌搜索算子

將集合AG_1中具有最高親和力的抗體（i=1）作為禁忌搜索算子的初始解，隨后進行禁忌搜索操作，TS中鄰域解構(gòu)造采用片段互換的進化方式，候選解的選取則按照親和力從高到低的排序進行部分選取，候選解個數(shù)為S，經(jīng)多次試驗，候選解個數(shù)在表2中給出.表中：N為種群數(shù)量；Itermax_1為最大迭代次數(shù)；G為迭代終止系數(shù)；α為克隆系數(shù)；抗體克隆規(guī)模Ni=round(αN/i)，終止條件itermax_2=GItermax_1.作為禁忌搜索的核心，特赦準則在一定程度上增強了其算法的平衡能力及其求解精度，禁忌搜索算子的禁忌對象為親和力值，禁忌長度T=round(n(n–1)/2).

表2 CSA與ACSATS算法求解CCAP與CAP的參數(shù)Tab.2 Algorithm parameters of CSA and ACSATS in solving CCAP and CAP

2）自適應(yīng)變異算子

自適應(yīng)變異操作為高效的局部搜索操作，近年來被廣泛采用[28-32]，而克隆選擇算法其以變異操作為主[26]，因此對變異概率Pm大小的選取至關(guān)重要.相比于傳統(tǒng)的變異操作，自適應(yīng)變異操作的變異概率會隨著親和力的高低進行變化，對于具有較好親和力的抗體，盡可能地減小其變異，最大程度地保證其優(yōu)良特性，而對于親和力較差的抗體，則希望通過變異對其親和力值進行相應(yīng)的改善.因此，本文采用任子武等[28]提出的變異概率公式對集合AG_1中i> 1抗體所對應(yīng)的克隆體進行自適應(yīng)變異，如式（15）.

式中：Pm1、Pm2分別為變異概率的上限、下限，且Pm1=0.1,Pm2=0.6；fmax、favg分別為2-opt操作后抗體集合中的最高親和力值、親和力平均值；f為參與變異的抗體當(dāng)前適應(yīng)度值，自適應(yīng)變異算子的變異方式為片段逆轉(zhuǎn)操作.

完成變異操作的集合為AG_3.

2.3 混合禁忌搜索的克隆選擇算法流程

采用全局選擇方式對ACSATS再次選擇，將AG_2與AG_3混合并按照親和力的高低進行排序，取前N個抗體，具體的算法流程如圖3所示.

圖3 ACSATS 流程Fig.3 Flow chart of ACSATS

圖中：Iter_1為算法迭代次數(shù)；ftemp為當(dāng)下最優(yōu)解；xtemp為當(dāng)下最優(yōu)解序列；fbest當(dāng)前算法尋的最優(yōu)解；xbest當(dāng)前算法尋的最優(yōu)解序列；Iter_2為最優(yōu)解方案變化計數(shù)器.

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

為了說明模型的合理性以及算法的有效性，在Intel（R）Corei5-8400、2.8 GHz、8 GB的Windows10操作環(huán)境下進行相應(yīng)的測試，由于目前暫無相關(guān)文獻報道CCAP的測試信息，因此，本文采用精確解優(yōu)化器LINGO對所提模型進行精確求解測試，并將其測試結(jié)果應(yīng)用于算法測試中，為其提供校驗依據(jù).在算法驗證部分除應(yīng)用所提算法求解所提CCAP外，將所提ACSATS應(yīng)用至基本CAP中，并將所得的測試結(jié)果與最新的算法進行對比，驗證所提算法的求解性能.經(jīng)過多次測試調(diào)整后，所提ACSATS算法與CSA算法在CCAP、CAP上的算法程序參數(shù)如表2所示，其中對于CCAP，其操作中存在定位設(shè)施插入操作，因此，上、下兩行的分界點nu的取值下限T1=floor(n/2)?2，nu取值上限T1=floor(n/2)，nu∈[T1,T2].對于CAP其上、下兩行的分界點nu的取值下限T1=floor(n/2)?3，nu取值上限T1=floor(n/2).

3.1 模型與所提算法的合理性驗證

為了驗證CCAP模型的合理性，應(yīng)用精確解優(yōu)化器LINGO對所提模型進行精確求解，針對CCAP的約束條件擬定為2.1節(jié)中所假定約束條件且實際設(shè)施布置不局限于上述假設(shè).經(jīng)測試確定所提CCAP模型為非線性規(guī)劃模型，LINGO優(yōu)化器求解過程中無法在較為合理的時間內(nèi)對所選算例進行高效求解，對此，將其運算時間t統(tǒng)一設(shè)置在900 s，對于900 s后仍未求得計算結(jié)果則用“—”表示.

與此同時，為了驗證算法的合理性，應(yīng)用所提ACSATS對所提CCAP進行求解，為了降低求解誤差，應(yīng)用ACSATS對每種算例求解30次.應(yīng)用求解偏差gap1作為算法求解結(jié)果的衡量指標，gap1=(Fmin–F0)/F0× 100%，其中：Fmin為ACSATS所求結(jié)果中的最小值；F0為LINGO所求精確值.算法的運行軟件為MATLAB R2016b.

表3為LINGO精確解與ACSATS算法的計算結(jié)果，由表3可以看出：當(dāng)算例的規(guī)模n≥25時，精確解優(yōu)化器無法在900 s內(nèi)給出相應(yīng)的求解結(jié)果，從側(cè)面反映出精確求解的局限性；S9、S9H和S10問題的gap1=0反映出精確求解與ACSATS算法的求解結(jié)果相同，為ACSATS的求解合理性提供了理論依據(jù)；對于問題S11、Am12a、Am12b、Am13a、Am13b以及Am15算例的gap1<0可以得出，在一定的求解時間內(nèi)，ACSATS的所求結(jié)果明顯優(yōu)于精確求解.

表3 LINGO精確解與ACSATS算法的計算結(jié)果Tab.3 LINGO exact solution and solving results of ACSATS

3.2 算法的高效性驗證

為說明ACSATS的高效性，結(jié)合所提CCAP，選取9 ～ 15規(guī)模的算例并應(yīng)用初始CSA與改進后的ACSATS進行求解結(jié)果的對比，兩種算法的參數(shù)如表2所示，求解結(jié)果如表4所示，表中：FCSA為算法CSA求解的目標值；FACSATS為算法ACSATS求解的目標值.

表4 CSA算法與ACSATS算法對CCAP的求解結(jié)果Tab.4 Solving results of CSA and ACSATS for CCAP

為了更直觀地看出兩種算法的求解數(shù)據(jù)的離散情況，根據(jù)所求540結(jié)果數(shù)據(jù)繪制求解偏差箱形圖（圖4），求解偏差用gap2表示，與gap1不同之處在于gap2中標準值采用兩種算法求解結(jié)果的最小值.

圖4 CSA與ACSATS在9～15規(guī)模下問題求解結(jié)果箱線圖Fig.4 Box-plot of the solution results of CSA and ACATS in the scale of 9?15

圖4中每個盒子的上下框線分別表示對應(yīng)問題數(shù)據(jù)的上、下四分位，每組數(shù)據(jù)中的紅線為該組數(shù)據(jù)的中位值，點劃線代表平均值，此外每組數(shù)據(jù)的上（下）邊緣的黑線代表最大（小）值，“ + ”表示異常值.通過箱線圖可以看出：除測試問題Am13b外，ACSATS所求結(jié)果中測試問題的箱體長度基本為0，異常值相對于CSA較少，表明ACSATS所求結(jié)果的數(shù)據(jù)離散度較小，改進后的算法具有相對顯著的優(yōu)勢.

3.3 ACSATS算法在基本CAP中的應(yīng)用

為了說明ACSATS具有一定通用性，將ACSATS應(yīng)用于求解基本CAP中，算法參數(shù)如表2所示，由于基本CAP沒有兩種約束的限制，因此，基于約束的2-opt操作釋放為標準2-opt操作.將ACSATS求解大規(guī)模CAP算例（n= 42與n= 49）的求解結(jié)果分別與文獻中所提的GA、SS、IDFPA以及IFWA的求解結(jié)果進行對比，如表5所示，下劃線標注的數(shù)據(jù)為算法ACSATS優(yōu)于其他幾組算法的求解結(jié)果.對比表5可知：除sko-49-05算例外，ACSATS算法的求解結(jié)果均能達到當(dāng)前先進算法的求解結(jié)果，甚至更優(yōu)（sko-42-04與sko-49-03）；ACSATS在時間上也具有優(yōu)勢且隨著規(guī)模變化平穩(wěn).因此可以得出，所提算法在求解基本CAP上同樣具有一定的高效性以及普適性，且算法較為穩(wěn)定.

表5 SS、GA、IDFPA、IFWA與ACSATS在42與49規(guī)模問題下測試CAP的求解結(jié)果Tab.5 Results of solving CAP with SS, GA, IDFPA, IFWA and ACSATS in 42 and 49 scale instances

4 結(jié) 論

綜合考慮設(shè)施布局的實際應(yīng)用情況，本文探究了設(shè)施間的相互關(guān)系對布局以及物料搬運成本的影響，主要成果如下：

1）考慮定位與排序兩種約束條件，完成所提受約束的過道布置問題的相關(guān)數(shù)學(xué)模型的構(gòu)建，并利用精確解優(yōu)化器LINGO對模型進行了精確求解，驗證了所提模型的正確性.

2）提出一種改進的混合克隆選擇算法，根據(jù)受約束的過道布置問題的問題特性，算法在原CSA的基礎(chǔ)上加入基于兩種約束的2-opt操作，在變異階段加入禁忌搜索操作并設(shè)置自適應(yīng)變異概率.使之搜索性能更強，對問題更適用.

3）應(yīng)用CSA對9～15規(guī)模的算例進行求解，通過對LINGO、ACSATS以及CSA在相同規(guī)模下的求解結(jié)果，驗證了改進算法存在顯著優(yōu)勢.

4）評估了ACSATS的求解性能，隨后將所提ACSATS算法應(yīng)用于基本CAP中.并對比IDFPA與IFWA對CAP的求解結(jié)果，對比試驗表明該算法在基本CAP上同樣具有良好的求解性能.

CCAP模型的建立極大程度地使得CAP更為貼近實際情況，但CCAP數(shù)學(xué)模型所具備的INLP屬性使其計算難度大幅增加.此外，單目標CCAP并不能完全反饋出其他目標或因素對實際布局情況的影響.因此，在未來的研究中，線性化CCAP模型、考慮更多的假設(shè)或目標函數(shù)以及使用ACSATS快速高效地計算更大規(guī)模算例等研究問題都將值得探索.