劉俊琦，張則強，王沙沙，曾艷清

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

1 問題的描述

“工業(yè)4.0”概念的提出，使得先進制造業(yè)成為未來發(fā)展的必然趨勢和關(guān)鍵內(nèi)容。加快發(fā)展方式轉(zhuǎn)變，促進工業(yè)邁向中高端不僅是建設(shè)制造強國的重要舉措，也是新常態(tài)下打造新的國際競爭優(yōu)勢的必然選擇。為取得競爭優(yōu)勢，制造業(yè)越來越重視高效低成本生產(chǎn)。設(shè)施布局問題[1-6]存在于多種類型的制造和服務(wù)系統(tǒng)中，如制造業(yè)中生產(chǎn)車間布局[5]，服務(wù)業(yè)中辦公區(qū)域布局[7]以及醫(yī)院走廊兩側(cè)醫(yī)務(wù)室與病房合理布局[8]，合理的布局直接關(guān)系到作業(yè)效率和運作成本。因此，在制造業(yè)、服務(wù)業(yè)和學術(shù)界中，設(shè)施布局問題受到廣泛關(guān)注。

作為設(shè)施布局問題的一種特殊形式，過道布置問題(Corridor Allocation Problem, CAP)[9]是一種典型的具有NP-hard屬性的組合優(yōu)化問題,其問題規(guī)模的擴大及約束條件的增加均使得精確求解難度大幅增加，因其具有較高的研究價值以及廣闊的應(yīng)用前景，使CAP自提出以來便迅速成為設(shè)施布局領(lǐng)域的研究熱點。過道布置問題及其混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)模型是由Amaral等[9]在2012年首次提出并建立的，且應(yīng)用3種啟發(fā)式方法求解該問題，驗證了該模型的正確性和算法的有效性;Ghosh等[10]應(yīng)用改進遺傳算法及分散搜索算法(Scatter Search, SS)分別對CAP的不同規(guī)模問題標準算例進行測試，兩種算法在結(jié)果上均可以得到高質(zhì)量的較優(yōu)解，且后者算法的收斂速度和運行效率均優(yōu)于前者;Ahone等[11]采用禁忌搜索算法(Tabu Search,TS)和改進模擬退火算法對CAP大規(guī)模算例問題進行測試求解，改進模擬退火算法在各方面均表現(xiàn)出良好的求解性能;Kalita等[12]在原始CAP問題模型的基礎(chǔ)上，將過道總長度考慮到過道布置問題當中，建立了非線性雙目標優(yōu)化問題數(shù)學模型，即設(shè)施總長度與設(shè)施間物流總成本最優(yōu)，并應(yīng)用遺傳算法對標準算例進行測試，驗證了算法的有效性;毛麗麗等[13]構(gòu)建了含有總流量入口和通道寬度的混合整數(shù)規(guī)劃模型，同時改進分散搜索算法并進行應(yīng)用，通過對大規(guī)模問題的求解測試發(fā)現(xiàn)，所設(shè)計算法的求解質(zhì)量和求解速度均優(yōu)于分散搜索算法與禁忌搜索算法;為了更符合實際生產(chǎn)情況，管超等[14-15]提出并構(gòu)建了雙層過道布置問題以及雙目標混合整數(shù)規(guī)劃模型,并對問題應(yīng)用花授粉算法與遺傳變鄰域算法進行求解，結(jié)果表明兩種算法均能較好地求解過道布置問題。

上述文獻對于CAP的建模與求解情況雖然已經(jīng)有了廣泛且深入的研究，但仍存在模型過于理想化或求解質(zhì)量不高以及求解效率欠理想的情況。物流交互點作為設(shè)施布局中的重要影響因素，在實際情況中合理的設(shè)置可以極大程度地減少運輸上的浪費，降低成本。初始CAP在一定意義上將物流交互點抽象成了方便計算的一維坐標點，在加入通道寬度后，演變成二維坐標點，文獻[16]探究了物流交互點在Y軸上位置對物流成本的影響。但迄今為止，未有文獻考慮設(shè)施物流交互點在X軸上不規(guī)則布置位置對總物料搬運成本的影響，傳統(tǒng)CAP的物流交互點為了簡化過道布置問題的計算復雜程度，僅將物流交互點設(shè)置在靠近過道邊線設(shè)施長度的中點，但在實際過道布置問題中，存在物流交互點不規(guī)則設(shè)置(設(shè)施的物料搬運點并非全部設(shè)置在靠近過道一側(cè)的設(shè)施邊線中點處)，如圖1所示為成都某醫(yī)院住院部樓層布局圖所示，走廊末尾兩房間的開門處在房間的角落位置，結(jié)合實際調(diào)研情況，將實際CAP物流交互點簡化成不規(guī)則交互坐標，即將走廊末尾兩房間坐標點抽象成角點，而非設(shè)施在過道邊線處的中點。本文以上述不規(guī)則交互點問題和過道寬度為研究對象，以含有過道寬度的過道布置問題為研究基礎(chǔ)，提出一種擴展的考慮不規(guī)則物流交互點的過道布置問題(EXtend Corridor Allocation Problem, EX-CAP)，使得過道布置問題更加貼近實際情況，一定程度的降低了物流成本。

雞群優(yōu)化(Chicken Swarm Optimization, CSO)算法是由Meng等[17]于2014年首次提出的一種模擬雞群群體覓食行為的仿生算法，是一種全局優(yōu)化算法，相比粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[18]，遺傳算法(Genetic Algorithm, GA)[19-21]等一系列尋優(yōu)算法，具有操作簡單、收斂速度快和收斂精度高[22]的優(yōu)點，且雞群算法求解過程具有方向特性[23]，可以沿著更好的方向?qū)?yōu)。目前，雞群算法在求解連續(xù)函數(shù)問題方面已被廣泛應(yīng)用，如軌跡優(yōu)化[24]，非線性系統(tǒng)的參數(shù)估計問題[25]、聚類分析問題[26]等優(yōu)化問題。除此之外，雞群算法也逐漸被改進并應(yīng)用于求解離散化問題，如求解0-1背包問題[27]、柔性作業(yè)車間調(diào)度問題[28]等，參考已有文獻，雞群算法在求解離散化問題上亦能取得了良好的求解結(jié)果。但綜合對雞群算法進行離散化處理、編碼方式采用實數(shù)編碼等操作，在設(shè)施布局方面的應(yīng)用尚未有公開報道，因此本文采用雞群算法來求解過道布置問題。

傳統(tǒng)雞群算法主要解決連續(xù)性問題[29]，對于高維度問題易出現(xiàn)過早陷入局部最優(yōu)和早熟收斂的情況[30]。針對這些問題，本文主要從兩方面進行改進：①對雞群算法進行離散化設(shè)計，采用遺傳算法中的交叉、變異等操作增加解的多樣性，防止陷入局部最優(yōu);②全局搜索中將雞群中已分組的個體按照所設(shè)定的代數(shù)參數(shù)G進行重新分組。與此同時，在局部搜索過程，對小雞位置更新的模塊加入定向策略，穩(wěn)定求解的優(yōu)化性。綜上所述，本文旨在考慮物流交互點在過道邊線水平方向上的變動對過道布置以及總成本的影響，根據(jù)問題特征，構(gòu)建符合該特征的混合整數(shù)規(guī)劃模型(MIP)，采用LINGO優(yōu)化器對所提出的模型進行精確求解以驗證模型正確性，并設(shè)計一種基于遺傳的混合雞群算法(GA-CSO)對EX-CAP問題進行大規(guī)模求解。為了更好地說明所提優(yōu)化算法具有更廣泛的適用性，將GA-CSO算法應(yīng)用到求解原始過道布置問題中并與相關(guān)文獻進行對比。結(jié)果表明，對于所引用初始CAP算例優(yōu)化，GA-CSO均表現(xiàn)出良好的求解速度和求解質(zhì)量。

1 考慮不規(guī)則物流交互點位置的CAP

1.1 問題描述

在文獻[5]的基礎(chǔ)上，本文考慮上下兩行設(shè)施序列末端設(shè)施物流交互點的位置對物流成本的影響,假設(shè)設(shè)施的形狀為大小不等的矩形(如圖2)，已知每個設(shè)施在X軸方向上的長度與各個設(shè)施間的物流量，將設(shè)施間的總物流成本最小作為目標函數(shù)，明確排列在通道兩側(cè)的設(shè)施數(shù)目，將設(shè)施與一個總流量入口(N+1)按照某種序列隨機排列在通道兩側(cè)，理想狀態(tài)下布局不受場地大小以及其他條件限制，且相鄰設(shè)施之間無間隙，上下兩行設(shè)施坐標均符合笛卡爾坐標系，最左側(cè)起始點為坐標軸原點O，假定排在末尾的設(shè)施物流交互點設(shè)置在靠近坐標軸原點的角點上。

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

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

I為所有設(shè)施的集合，I={1,2,3,…,n,n+1}；

i,j為設(shè)施的編號，i,j∈I；

cij為設(shè)施間的物流成本；

dij為設(shè)施i,j之間物流交互點在X軸方向的距；

w為通道寬度；

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

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

qij為二進制決策變量，若設(shè)施i與設(shè)施j在被布置于同一行，則qij=1,否則qij=0。

1.2 EX-CAP交互點位置的約束條件

在CAP中，通常為簡化求解方式，基于應(yīng)用笛卡爾坐標系確定的物流交互點一般設(shè)置在設(shè)施邊線中點，若根據(jù)實際情況將物流交互點布置在角點上并建立數(shù)學模型則更為復雜，其原因在于對原始CAP問題所建立的數(shù)學模型中，均未考慮預先確定的位置上的設(shè)施，在求解過程中易簡化對兩個設(shè)施之間距離的求解方式。對此，為進一步考慮交互點位置的過道布置問題(EX-CAP)，引入二進制變量β，則物流交互點位置坐標為：

1≤i≤n+1,1≤m

(1)

1≤j≤n+1,1≤m

(2)

其中：βim表示i設(shè)施放置在m或者N位置上，若放置在該位置上則βim=1，否則βim=0;βiN，βjm，βjN同理;N為第二行末端設(shè)施位置。

1.3 EX-CAP模型

結(jié)合上述含有未統(tǒng)一物流交互點的約束條件，構(gòu)造擴展過道布置問題模型(EX-CAP)：

(3)

1≤i

(4)

1≤i

(5)

1≤i

(6)

-αij+αik+αjk-αji+αki+αkj<0，

i,j,k∈I,i

(7)

-αij+αik-αjk+αji-αki+αkj≤1，

i,j,k∈I,i

(8)

αij+αik+αjk+αji+αki+αkj≥1，

1≤i

(9)

βim+βiN≤1,1≤i≤N,1≤m

(10)

βjm+βjN≤1,1≤j≤N,1≤m

(11)

βim+βjm≤1,1≤i,j≤N,1≤m

(12)

βiN+βjN≤1,1≤i,j≤N,1≤m

(13)

qij=αij+αji,1≤i,j≤n+1,i≠j；

(14)

αij∈{0,1},1

(15)

qij∈{0,1},1

(16)

βim∈{0,1},1≤i≤N,1≤m

(17)

其中：目標函數(shù)(3)表示總物流成本最小化。約束(4)和約束(5)用于計算各物流交互帶點之間在水平軸方向上的最小距離;約束(6)預防了同行的設(shè)施布置重疊情況的出現(xiàn);約束(7)～約束(13)確定決策變量,其中約束(10)～約束(13)相互約束，設(shè)施i有且僅有一個位置可以放置，同時有且僅有一個設(shè)施放置在m處，設(shè)施j以及N位置同理;約束(14)驗證設(shè)施i和j是否所在同一行;約束(15)～約束(17)定義決策變量的定義域。

2 求解EX-CAP的GA-CSO算法

2.1 基本雞群算法

雞群算法(CSO)是一種通過模擬生物種群來解決實際優(yōu)化問題的仿生學算法，該算法的優(yōu)化方式從雞群中的等級制度和行為習慣衍生而來，主要體現(xiàn)在角色劃分、等級制度的建立以及按照等級制度派生出的隨從行為、學習行為和覓食行為等行為規(guī)律，通過雞群中的一系列制度和行為作出如下假設(shè)：

(1)等級制度 在雞群中有公雞、母雞和小雞順序排列的幾種角色存在，該序列將個體的適應(yīng)度值作為劃分依據(jù)，適應(yīng)度值排在前列的若干個體身份設(shè)定為公雞，排在中間的個體設(shè)定為母雞，最后的設(shè)定為小雞。同時，將雞群分為若干個子種群，每個子種群中均有一只公雞作為代表，帶領(lǐng)若干只母雞和小雞。在等級制度下，一個子種群內(nèi)的組間調(diào)配關(guān)系和組內(nèi)母子關(guān)系將保持不變，這種狀態(tài)每隔G代更新一次。

(2)行為規(guī)律 在雞群中，具有良好適應(yīng)度值的公雞占主導地位，具有良好的支配權(quán)，且先于其他個體尋得食物。子群中每個個體均會圍繞公雞進行行動，并假設(shè)母雞或小雞具有偷取其他個體已經(jīng)發(fā)現(xiàn)的食物的能力，母雞圍繞公雞進行覓食，小雞圍繞母雞覓食。

在當前應(yīng)用的CSO算法中，雞群中每個個體都對應(yīng)優(yōu)化問題的一個解?；綜SO算法分別對公雞母雞和小雞位置更新定義各自的公式，在求解連續(xù)性問題上具有較高的求解效率，其尋優(yōu)過程如圖3所示。

基本CSO算法的偽代碼如下：

Initialization parameter

Begin

Calculate the fitness value for each individual

for T=1:Tmax

If mod(T,G)==1

Redefining the intra-and Inter-grouprelationships of Rooster Hens

endif

Update Rooster location

Update hen location

Update Chicken location

endfor

end

2.2 基于遺傳的混合雞群算法(GA-CSO)

2.2.1 初始雞群產(chǎn)生方法

針對設(shè)施布局中的過道布置問題具有組合優(yōu)化的特性，采用基于設(shè)施編碼序列的整數(shù)編碼方式定義個體位置，每只個體的位置X用一個序列來表示，且根據(jù)雞群中所需定位的維度來確定序列的長度，在X中每一維數(shù)字表示相應(yīng)設(shè)施的編號，序列中編號的最大值不超過最大維度。

X={x1,x2,x3,…,xi,…，xn},

1

式中i為設(shè)施索引，且i的范圍不超過最大維度。每種排布序列代表雞群中某一個體，同時也代表一種布局方案。以經(jīng)典n=9的經(jīng)典算例為例，假定其中某一可行解的序列為x=[9 4 5 6 8 1 7 3 2]，若給定第一行設(shè)施數(shù)目為4個設(shè)施，則可行解被劃分為兩個序列為[9 4 5 6]和[8 1 7 3 2]，該序列的整數(shù)編碼與解碼過程如圖4所示。

2.2.2 GA-CSO算法的離散化設(shè)計

(1)離散化設(shè)計 傳統(tǒng)的遺傳算法(Genetic Algorithm, GA)是根據(jù)生物進化的特征和遺傳學機理為原理進行的設(shè)計，是一種通過自然進化等方式隨機搜索適應(yīng)度值的方法，其優(yōu)點在于可以直接面向?qū)ο筮M行尋優(yōu)，不會受到連續(xù)函數(shù)或微分形式的約束和限制，可以極大程度地簡化編碼與解碼形式，同時GA具有一定的自適應(yīng)性，通常GA以群體中個體為對象，并采用隨機搜索方式作用在已編碼的參數(shù)空間內(nèi)，使其打開搜索進程。GA主要的算子包括選擇、交叉和變異等，其中交叉操作是作為GA算法的重要特征性操作，同時也是離散化設(shè)計與保持種群中個體多樣性的重要操作。

傳統(tǒng)雞群算法應(yīng)用公式計算公雞、母雞與小雞的覓食位置，很難適用于離散化問題。針對該問題，提出采用遺傳算法中的交叉操作算子與之混合的方式對公雞、母雞和小雞的位置進行更新，其中公雞個體采用同一等級內(nèi)進行交叉操作，母雞則根據(jù)行為與同組內(nèi)的公雞進行交叉操作，其中交叉操作采用部分映射交叉(Partially-Mapped Crossover，PMX)，具體操作如圖5所示。

(2)定向化策略 基本CSO算法，小雞只向母雞媽媽學習，這便限制了小雞的學習方式，且無法保證小雞一定是向更好的方向進行位置更新。但在自然界中，小雞的學習方式更為多樣化，同時由于追隨母雞媽媽的緣故，小雞容易隨同組的母雞媽媽一起陷入局部最優(yōu)，因此采用定向策略與離散化策略將小雞個體的交叉對象由原有的母雞媽媽更換成當前在種群中地位最高、適應(yīng)性更強的個體，這樣小雞個體在更新后仍具備良好的尋優(yōu)方向且易于跳出局部最優(yōu)。

2.2.3 變異算子與終止準則

在上述局部搜索階段，對雞群中的公雞、母雞和小雞分別進行了離散化設(shè)計，在離散化設(shè)計的基礎(chǔ)上，對其進行變異操作，其變異方式采用多點變異操作。在變異的過程中，設(shè)置變異概率Pm并比較隨機值R與Pm的大小，當Pm>R時，發(fā)生變異，通過變異操作不斷地擴大搜索廣度，不斷更新當前最優(yōu)解。同時為了提高GA-CSO算法的求解效率，與遺傳算法等求解CAP算法進行比較，本文采用以最大迭代次數(shù)Tmax作為終止條件，Tmax的取值根據(jù)問題求解規(guī)模n及最優(yōu)值的穩(wěn)定程度而定，設(shè)置T為雞群更新次數(shù)的計數(shù)器，若T>Tmax，則算法終止，返回當前最優(yōu)值fitbest。

2.3 混合雞群算法流程

上述離散雞群算法步驟如下：

步驟1初始化種群并定義相關(guān)參數(shù)：雞群數(shù)量N，雞群等級占比rPercent、hPercent、mPercent，設(shè)施規(guī)模(維度)n，群內(nèi)更新代數(shù)G，交叉概率Pc，變異概率Pm。

步驟2產(chǎn)生初始種群表Chrom，計算雞群適應(yīng)度值并建立適應(yīng)度表fitness，比較并挑選當前最優(yōu)適應(yīng)度值fitbest和全局最優(yōu)序列(布置方案)Xbest，將適應(yīng)度值排序，按照雞群內(nèi)等級占比劃分為公雞、母雞、小雞和母雞媽媽以及確定種群內(nèi)分組。

步驟3進入迭代，令T=1。

步驟4建立新種群表newChrom與新適應(yīng)度表newfitness。

步驟5如果T%G=1(取余數(shù))，重新建立雞群等級制度，對雞群的等級制度和組內(nèi)關(guān)系進行更新。

步驟6令i=1:rNum,開始公雞位置更新循環(huán)，生成i以外的另一只公雞anotherooster。

步驟7兩只公雞進行交叉變異，將得到的第i只公雞放入，表中其原來對應(yīng)位置。

步驟8令j=(rNum+1):(rNum+hNum)，開始母雞位置更新循環(huán)。

步驟9根據(jù)雞群內(nèi)部等級制度與組內(nèi)關(guān)系，確定母雞在組內(nèi)所對應(yīng)的公雞roosterj，并將第j只新母雞hensj與roosterj進行交叉變異，將得到的第j只母雞放入表中其原來對應(yīng)位置。

步驟10令k=(rNum+hNum+1):N，開始小雞的循環(huán)。

步驟11根據(jù)雞群內(nèi)部等級制度與組內(nèi)關(guān)系，確定小雞所在種群中母雞最優(yōu)位置以及母雞序列，將小雞與其進行交叉、變異，得到的小雞序列放入表中其原來對應(yīng)位置。

步驟12計算新表newfitness中的適應(yīng)度值。

步驟13比較并挑選當前產(chǎn)生的最優(yōu)適應(yīng)度值newfitbest，若newfitbest

步驟14令T=T+1。

步驟15比較T≤Tmax，繼續(xù)執(zhí)行步驟5～步驟14，否則輸出全局最優(yōu)值fitbest以及所對應(yīng)的最優(yōu)位置序列。

算法流程如圖6所示。

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

為驗證所提模型的正確性，采用LINGO優(yōu)化器對上述所構(gòu)建模型進行不同規(guī)模的算例求解。本文實驗所采用的計算機硬件配置為Intel(R)酷睿i5-8400、主頻2.8 GHz、內(nèi)存8 GB，Windows10操作系統(tǒng)。除應(yīng)用LINGO優(yōu)化器對所提問題進行小規(guī)模算例驗證外，為了驗證所提混合雞群算法(GA-CSO)的求解性能，應(yīng)用MATLAB R2016b進行計算求解。本文分別應(yīng)用GA-CSO對初始CAP問題的9～49不同規(guī)模進行計算并將結(jié)果與文獻[9]的遺傳算法、分散搜索算法、文獻[10]的模擬退火以及文獻[12]的改進分散搜索算法進行對比，經(jīng)過大量算例測試和程序調(diào)試后確定的參數(shù)設(shè)置如表1所示。此外,兼顧求解效率與質(zhì)量，在大量數(shù)據(jù)測算后總結(jié)得出Nu∈[T1,T2]，其中T1=floor(n/2)-2，T2=floor(n/2)。為了更好地說明情況并保證所使用的數(shù)據(jù)具有一定準確性，對每種算例均進行至少10次的運算。

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

續(xù)表1

3.1 EX-CAP模型的驗證

因符合問題特征的MIP數(shù)學模型中含有非線性約束條件,致使LINGO優(yōu)化器求解過程中無法在較為合理的時間內(nèi)對大規(guī)模算例進行高效求解。通過表2可得：10規(guī)模算例已經(jīng)無法在合理時間內(nèi)求解出最優(yōu)解，因此在原有小規(guī)模S9算例基礎(chǔ)上，提取S9中5到8規(guī)模數(shù)據(jù)進行求解計算，針對大于11規(guī)模的測試問題，將其運算時間設(shè)置在1 800 s，若無法求得計算結(jié)果則用“-”表示。

表2 LINGO精確解與GA-CSO算法的計算結(jié)果

續(xù)表2

此外，結(jié)合表2的求解結(jié)果，計算LINGO與GA-CSO的求解偏差gap，繪制箱線圖(如圖7)，該圖主要顯示出6個數(shù)據(jù)的節(jié)點，可以很好地反映原始數(shù)據(jù)分布的特征以及離散情況。圖7中上下線框、中間線、點畫線分別表示一組數(shù)據(jù)的上下四分位、中位值、平均值，此外上下框線的邊緣線表示最值到四分位數(shù)的取值區(qū)間，上下四分位、中位值、平均值。從圖7中可以看出，對于GA-CSO所計算的小規(guī)模問題，其偏差基本為0，而在求解S9H、S10、S11問題時，其求解偏差為：1.34、1.82、0.95，由此可得GA-CSO具有較為良好的求解性能。

物流交互點的變動致使總物流成本也發(fā)生變動，因此對不同因素下的CAP問題數(shù)學模型求解結(jié)果進行對比(如表3)，并計算其節(jié)約率Sr。對比發(fā)現(xiàn)：所提出的EX-CAP問題的物流成本均小于僅考慮考慮通道寬度及總流量入口CAP問題的物流成本，且最高降低29.77%，可以看出所提出的EX-CAP問題在一定程度上可以為實際生產(chǎn)布局提供部分理論指導。

表3 考慮不同因素的CAP問題模型求解對比

續(xù)表3

3.2 算法驗證

為驗證改進雞群算法在求解過道布置一類問題的有效性和普適性，除對所提問題進行求解驗證外，對設(shè)施數(shù)小于等于15規(guī)模的算例進行測試，采用混合雞群算法求解初始過道布置問題，每個測試問題采用10次計算取其平均值的方式以增強數(shù)據(jù)的說服力度，將所得結(jié)果與CAP-GA、CAP-SS、CAP ISS和CAP SA作比較，小規(guī)模CAP各算法測試結(jié)果、對比數(shù)據(jù)如表4所示。經(jīng)表4分析可知，幾種算法均可以在較短的時間內(nèi)尋得最優(yōu)值，但本文所提的GA-CSO在求解效率上更勝一籌。

表4 求解小規(guī)模初始CAP問題的各算法計算結(jié)果對比

在對小規(guī)模算例進行計算驗證后，為了可以更進一步說明算法的高效性，應(yīng)用GA-CSO對大CAP原初始問題的大中規(guī)模算例進行求解計算，要求對每種算例進行不少于10次計算，計算結(jié)果及時間均取其平均值，詳細參數(shù)參考表1中的參數(shù)設(shè)置，將所計算出的結(jié)果與Ghosn等[10]的SS算法、GA算法以及毛麗麗等[13]的ISS算法所求結(jié)果進行對比，結(jié)果如表5所示。

表5 GA-CSO求解大規(guī)模原始CAP問題計算結(jié)果

續(xù)表5

由表5可知，隨著規(guī)模的增大，求解時間與問題規(guī)模成正相關(guān)關(guān)系。在求解質(zhì)量方面，除測試問題sko-49-01外，GA-CSO明顯優(yōu)于傳統(tǒng)GA，對于sko-49-01測試問題求解質(zhì)量相同的情況下，GA-CSO的求解結(jié)果在相同問題規(guī)模下明顯優(yōu)于GA。不難看出，隨著問題的規(guī)模增大，SS與GA運算時間隨著問題規(guī)模的增大也大幅度地增加;而GA-CSO與ISS相比，隨著規(guī)模的增大，各項指標均可以平緩增長。

此外,根據(jù)計算得到的結(jié)果，選定S11算例為基礎(chǔ)數(shù)據(jù)，繪制如圖8所示的迭代收斂圖，為了對比結(jié)果明顯，選用所含參數(shù)類別大致相同的GA與其作參照，并將GA設(shè)置與GA-CSO相同的算法參數(shù)。由圖8可以看出，當兩種算法均可以在有限的迭代次數(shù)內(nèi)迭代到相對最優(yōu)值時，GA-CSO算法在迭代至71次時趨于平穩(wěn)狀態(tài)，而GA則在迭代到251次時趨于穩(wěn)定，且在時間方面GA-CSO明顯優(yōu)于GA。因此可以得出結(jié)論：GA-CSO在求解質(zhì)量和效率方面都有相對較好的性能。

4 結(jié)束語

本文結(jié)合實際生產(chǎn)情況，考慮了物流交互點在過道邊線水平方向上的變動對過道布置以及總成本的影響，并構(gòu)建了目標函數(shù)為最小化物流成本的EX-CAP數(shù)學模型，提出一種混合遺傳操作的新型雞群算法對該問題進行求解。通過應(yīng)用LINGO優(yōu)化器所求精確解并與其他算法進行對比驗證，總結(jié)本文主要成果如下：

(1)構(gòu)建了EX-CAP混合整數(shù)非線性規(guī)劃模型，并用LINGO11軟件對該模型的小規(guī)模問題進行了精確求解，驗證了所構(gòu)建的MIP數(shù)學模型的合理性。

(2)將基本CSO與GA結(jié)合，進行離散化設(shè)計，采用部分映射交叉算子(PMX)對解序列進行交叉操作。同時，對于種群中適應(yīng)度值較為落后的個體采用定向化策略使其在一定意義上朝著最優(yōu)解方向進化。

(3)為了驗證所提算法的性能，應(yīng)用其計算求解原CAP問題，并與文獻[10-11,13]等一系列算法求解結(jié)果進行對比，結(jié)果表明：GA-CSO具有操作簡單、收斂速度快的優(yōu)點，且其內(nèi)部的GA中交叉、變異操作以及定向化策略幫助其克服了陷入局部最優(yōu)的難題，具有較好的求解精度和求解效率。

本文所提EX-CAP模型在一定程度上較為貼合實際，但其物料搬運位置仍然不夠靈活。為了更貼近實際生產(chǎn)情況，下一步將設(shè)施的物料搬運點位置從固定在靠近通道邊線中點處改進成在一定范圍內(nèi)設(shè)置進行研究。