考慮不規(guī)則物流交互點(diǎn)的過道布置問題建模與優(yōu)化

劉俊琦，張則強(qiáng)，王沙沙，曾艷清

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

1 問題的描述

“工業(yè)4.0”概念的提出，使得先進(jìn)制造業(yè)成為未來發(fā)展的必然趨勢和關(guān)鍵內(nèi)容。加快發(fā)展方式轉(zhuǎn)變，促進(jìn)工業(yè)邁向中高端不僅是建設(shè)制造強(qiáng)國的重要舉措，也是新常態(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ùn)作成本。因此，在制造業(yè)、服務(wù)業(yè)和學(xué)術(shù)界中，設(shè)施布局問題受到廣泛關(guān)注。

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

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

雞群優(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)點(diǎn)，且雞群算法求解過程具有方向特性[23]，可以沿著更好的方向?qū)?yōu)。目前，雞群算法在求解連續(xù)函數(shù)問題方面已被廣泛應(yīng)用，如軌跡優(yōu)化[24]，非線性系統(tǒng)的參數(shù)估計(jì)問題[25]、聚類分析問題[26]等優(yōu)化問題。除此之外，雞群算法也逐漸被改進(jìn)并應(yīng)用于求解離散化問題，如求解0-1背包問題[27]、柔性作業(yè)車間調(diào)度問題[28]等，參考已有文獻(xiàn)，雞群算法在求解離散化問題上亦能取得了良好的求解結(jié)果。但綜合對雞群算法進(jìn)行離散化處理、編碼方式采用實(shí)數(shù)編碼等操作，在設(shè)施布局方面的應(yīng)用尚未有公開報(bào)道，因此本文采用雞群算法來求解過道布置問題。

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

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

1.1 問題描述

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

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

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

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

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

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

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

w為通道寬度；

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

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

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

1.2 EX-CAP交互點(diǎn)位置的約束條件

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

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)一物流交互點(diǎn)的約束條件，構(gòu)造擴(kuò)展過道布置問題模型(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)

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

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

2.1 基本雞群算法

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

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

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

在當(dāng)前應(yīng)用的CSO算法中，雞群中每個(gè)個(gè)體都對應(yīng)優(yōu)化問題的一個(gè)解?；綜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ù)編碼方式定義個(gè)體位置，每只個(gè)體的位置X用一個(gè)序列來表示，且根據(jù)雞群中所需定位的維度來確定序列的長度，在X中每一維數(shù)字表示相應(yīng)設(shè)施的編號，序列中編號的最大值不超過最大維度。

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

1

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

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

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

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

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

2.2.3 變異算子與終止準(zhǔn)則

在上述局部搜索階段，對雞群中的公雞、母雞和小雞分別進(jìn)行了離散化設(shè)計(jì)，在離散化設(shè)計(jì)的基礎(chǔ)上，對其進(jìn)行變異操作，其變異方式采用多點(diǎn)變異操作。在變異的過程中，設(shè)置變異概率Pm并比較隨機(jī)值R與Pm的大小，當(dāng)Pm>R時(shí)，發(fā)生變異，通過變異操作不斷地?cái)U(kuò)大搜索廣度，不斷更新當(dāng)前最優(yōu)解。同時(shí)為了提高GA-CSO算法的求解效率，與遺傳算法等求解CAP算法進(jìn)行比較，本文采用以最大迭代次數(shù)Tmax作為終止條件，Tmax的取值根據(jù)問題求解規(guī)模n及最優(yōu)值的穩(wěn)定程度而定，設(shè)置T為雞群更新次數(shù)的計(jì)數(shù)器，若T>Tmax，則算法終止，返回當(dāng)前最優(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，計(jì)算雞群適應(yīng)度值并建立適應(yīng)度表fitness，比較并挑選當(dāng)前最優(yōu)適應(yīng)度值fitbest和全局最優(yōu)序列(布置方案)Xbest，將適應(yīng)度值排序，按照雞群內(nèi)等級占比劃分為公雞、母雞、小雞和母雞媽媽以及確定種群內(nèi)分組。

步驟3進(jìn)入迭代，令T=1。

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

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

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

步驟7兩只公雞進(jìn)行交叉變異，將得到的第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ìn)行交叉變異，將得到的第j只母雞放入表中其原來對應(yīng)位置。

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

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

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

步驟13比較并挑選當(dāng)前產(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 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證所提模型的正確性，采用LINGO優(yōu)化器對上述所構(gòu)建模型進(jìn)行不同規(guī)模的算例求解。本文實(shí)驗(yàn)所采用的計(jì)算機(jī)硬件配置為Intel(R)酷睿i5-8400、主頻2.8 GHz、內(nèi)存8 GB，Windows10操作系統(tǒng)。除應(yīng)用LINGO優(yōu)化器對所提問題進(jìn)行小規(guī)模算例驗(yàn)證外，為了驗(yàn)證所提混合雞群算法(GA-CSO)的求解性能，應(yīng)用MATLAB R2016b進(jìn)行計(jì)算求解。本文分別應(yīng)用GA-CSO對初始CAP問題的9～49不同規(guī)模進(jìn)行計(jì)算并將結(jié)果與文獻(xiàn)[9]的遺傳算法、分散搜索算法、文獻(xiàn)[10]的模擬退火以及文獻(xiàn)[12]的改進(jìn)分散搜索算法進(jìn)行對比，經(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ù)具有一定準(zhǔn)確性，對每種算例均進(jìn)行至少10次的運(yùn)算。

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

續(xù)表1

3.1 EX-CAP模型的驗(yàn)證

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

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

續(xù)表2

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

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

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

續(xù)表3

3.2 算法驗(yàn)證

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

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

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

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

續(xù)表5

由表5可知，隨著規(guī)模的增大，求解時(shí)間與問題規(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運(yùn)算時(shí)間隨著問題規(guī)模的增大也大幅度地增加;而GA-CSO與ISS相比，隨著規(guī)模的增大，各項(xiàng)指標(biāo)均可以平緩增長。

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

4 結(jié)束語

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

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

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

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

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