毛麗麗，張則強(qiáng)，朱立夏

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

1 引言

合理的設(shè)施布局可以節(jié)約10%～30%的搬運(yùn)和等待成本，提高生產(chǎn)效率[1]。過(guò)道布置問(wèn)題（Corridor Allocation Problem，CAP）作為設(shè)施布局問(wèn)題[2-4]的一種特例，是典型的NP-hard問(wèn)題，求解難度較大，且在工業(yè)和服務(wù)部門中應(yīng)用廣泛[5-6]，如教學(xué)樓、醫(yī)院、行政辦公樓、大型購(gòu)物中心、半導(dǎo)體生產(chǎn)線等的布置。因而，該問(wèn)題自2012年首次提出以來(lái)便引起了廣大學(xué)者的高度關(guān)注。

過(guò)道布置問(wèn)題指將一系列給定數(shù)目的設(shè)施布置到過(guò)道的兩側(cè)，并尋求一種最優(yōu)布置，使全部設(shè)施對(duì)間的總流量（物流量、人流量）成本最小，要求同一行任意兩相鄰設(shè)施間沒(méi)有間隙，且上下兩行設(shè)施均從過(guò)道的最左邊同一點(diǎn)開(kāi)始布置。

Amaral[7]首先提出了過(guò)道布置問(wèn)題，建立了該問(wèn)題的混合整數(shù)規(guī)劃模型，并采用三種啟發(fā)式方法對(duì)規(guī)模不超過(guò)30的測(cè)試問(wèn)題進(jìn)行試驗(yàn)，結(jié)果表明啟發(fā)式方法的求解效率明顯優(yōu)于精確方法，但其求解時(shí)間仍有待進(jìn)一步改善。為提高求解效率，Ghosh等[8]應(yīng)用遺傳算法和分散搜索算法來(lái)求解該問(wèn)題，試驗(yàn)結(jié)果表明兩種智能算法均能獲得近優(yōu)解，且在運(yùn)行效率上分散搜索算法較遺傳算法更具優(yōu)勢(shì)。但在求解設(shè)施數(shù)為42和49規(guī)模的測(cè)試問(wèn)題時(shí)，分散搜索的最大求解時(shí)間為3 716.16 s，還有進(jìn)一步提升的空間。Ahonen等[9]采用模擬退火算法和禁忌搜索算法對(duì)不同規(guī)模的過(guò)道布置問(wèn)題進(jìn)行了驗(yàn)算與對(duì)比，模擬退火算法在求解質(zhì)量和求解效率方面表現(xiàn)出了更優(yōu)的搜索性能。但文中模擬退火算法求解問(wèn)題規(guī)模為15的測(cè)試?yán)訒r(shí)，其平均求解時(shí)間為12.02 s，而在求解問(wèn)題規(guī)模為30的測(cè)試?yán)訒r(shí)，其平均求解時(shí)間僅為4.58 s，不符合問(wèn)題規(guī)模越大求解時(shí)間越長(zhǎng)的規(guī)律。上述文獻(xiàn)為過(guò)道布置問(wèn)題的研究提供了參考，但求解性能還有進(jìn)一步改善的空間。

分散搜索算法采用其框架中的一系列系統(tǒng)性方法代替搜索過(guò)程的隨機(jī)性實(shí)現(xiàn)對(duì)問(wèn)題的優(yōu)化，具有全局搜索能力強(qiáng)、靈活性好、易與其他算法相結(jié)合等優(yōu)點(diǎn)。目前已成功應(yīng)用于許多組合優(yōu)化問(wèn)題，如無(wú)人機(jī)路徑規(guī)劃問(wèn)題[10]、拆卸序列優(yōu)化問(wèn)題[11]、車間調(diào)度問(wèn)題[12]、配電系統(tǒng)規(guī)劃問(wèn)題[13]等。參考已有文獻(xiàn)，尚未發(fā)現(xiàn)有關(guān)分散搜索算法和模擬退火算法相結(jié)合求解過(guò)道布置問(wèn)題的公開(kāi)報(bào)道。

鑒于現(xiàn)有研究的不足，本文結(jié)合過(guò)道布置問(wèn)題特點(diǎn)以及分散搜索算法求解組合優(yōu)化問(wèn)題的優(yōu)勢(shì)，提出一種混合分散搜索算法（Hybrid Scatter Search，HSS）求解該問(wèn)題。通過(guò)引入模擬退火操作[14]，對(duì)參考集中的解進(jìn)行局部?jī)?yōu)化，并設(shè)計(jì)了雙層參考集、動(dòng)態(tài)參考集更新方法等多種改進(jìn)機(jī)制。通過(guò)對(duì)大量不同規(guī)模的測(cè)試問(wèn)題的試驗(yàn)與對(duì)比，驗(yàn)證了所提算法求解過(guò)道布置問(wèn)題良好的求解性能。

2 過(guò)道布置問(wèn)題

2.1 問(wèn)題描述

過(guò)道布置問(wèn)題如圖1所示，指將n個(gè)不同的矩形狀設(shè)施布置到過(guò)道兩側(cè)，找到一種使全部設(shè)施對(duì)間的總流量（物流量、人流量）成本最小的布置方案，確定過(guò)道兩側(cè)每一行上的設(shè)施數(shù)量及其排列順序，要求同一行任意兩相鄰設(shè)施間沒(méi)有間隙，且上下兩行設(shè)施均從過(guò)道的最左邊同一點(diǎn)開(kāi)始布置。圖中有陰影部分的小圓圈表示流量交互點(diǎn)，表明每個(gè)設(shè)施的流量交互點(diǎn)均位于設(shè)施靠過(guò)道邊線中點(diǎn)。

圖1 過(guò)道布置問(wèn)題

2.2 基本假設(shè)條件

（1）每個(gè)設(shè)施靠過(guò)道邊線的寬度及各設(shè)施對(duì)間的流量為已知量。

（2）每個(gè)設(shè)施的流量交互點(diǎn)均位于設(shè)施靠過(guò)道邊線中點(diǎn)。

（3）同一行相鄰兩設(shè)施間沒(méi)有間隙。

（4）上下兩行設(shè)施均從過(guò)道最左邊同一點(diǎn)開(kāi)始布置。

（5）假設(shè)上下兩行設(shè)施間的過(guò)道寬度為0。

（6）設(shè)施布置不受場(chǎng)地大小及其他條件限制。

2.3 變量與參數(shù)定義

為描述方便，模型中用到的數(shù)學(xué)符號(hào)的意義如下：

n：?jiǎn)栴}規(guī)模，即設(shè)施的數(shù)目；

I：設(shè)施集合，I={1,2,…,n}；

i,j：設(shè)施編號(hào)，i,j∈ I；

cij：設(shè)施i,j之間的流量成本， ?i∈I1,?j∈I2，I1={1,2,…,n-1},I2={i+1,i+2,…,n};

li：設(shè)施i的寬度；

dij：設(shè)施i和設(shè)施j靠過(guò)道邊線中點(diǎn)間的橫坐標(biāo)距離；

αij：二進(jìn)制變量，若設(shè)施i,j分配在同一行，且設(shè)施i布置在設(shè)施 j的左邊，則αij=1，否則αij=0。

2.4 數(shù)學(xué)模型

過(guò)道布置問(wèn)題的混合整數(shù)規(guī)劃模型[7]M1如下：

式中，目標(biāo)函數(shù)（1）表示最小化總流量成本，約束（2）和（3）用于計(jì)算各設(shè)施間的距離，約束（4）用以防止同行的設(shè)施位置發(fā)生重疊放置，約束（5）～（8）用于確定決策變量αij，式（9）給定決策變量αij的定義域。

3 混合模擬退火及分散搜索算法

3.1 多樣性初始解產(chǎn)生方法

解的編碼和解碼示意圖如圖2所示，本文結(jié)合過(guò)道布置問(wèn)題的特點(diǎn)，采用一種基于設(shè)施編號(hào)的編碼方式，通過(guò)這種方式可將一種布置方案編碼成一個(gè)設(shè)施編號(hào)的序列。對(duì)于設(shè)施數(shù)目為8的過(guò)道布置問(wèn)題，隨機(jī)排列8個(gè)不同的自然數(shù)就可得到該問(wèn)題的一個(gè)可行解，例如x=[1 4 6 3 7 5 2 8]。假設(shè)此時(shí)布置在上下行的設(shè)施個(gè)數(shù)分別為3個(gè)和5個(gè)，圖中用符號(hào)“|”表示分隔點(diǎn)，則解x解碼為：從過(guò)道最左邊為起始點(diǎn)，從左往右排列，布置在第一行的各設(shè)施編號(hào)依次為1、4、6，布置在第二行的各設(shè)施編號(hào)依次為3、7、5、2、8。

圖2 解的編碼和解碼

由于分散搜索算法對(duì)初始解的依賴性強(qiáng)且及其敏感，故初始種群中的解必須是高質(zhì)量和多樣性好的解。鑒于此，本文采用Kothari和Ghosh[15]提出的多樣性產(chǎn)生方法DIV-1代替隨機(jī)法構(gòu)建初始種群，使初始解在解空間具有良好的分散性。解的多樣性評(píng)價(jià)標(biāo)準(zhǔn)見(jiàn)公式（10）：

式中，解x1和x2之間的偏離距離d(x1,x2)為解x1和x2對(duì)應(yīng)位置上兩個(gè)設(shè)施編號(hào)差值的絕對(duì)值加權(quán)和。定義解x1和x2之間的最小偏離距離為解x1和x2之間的偏離距離與解x1和x2的倒置解之間的偏離距離的最小值。

過(guò)道布置問(wèn)題的多樣性初始種群的產(chǎn)生過(guò)程為：首先，隨機(jī)交換種子解x=[1,2,…,n]中兩個(gè)設(shè)施的位置產(chǎn)生US個(gè)候選解構(gòu)成候選種群，并從中選出ES個(gè)目標(biāo)函數(shù)值最小的候選解構(gòu)成精英種群，接著將精英種群中最大最小偏離距離對(duì)應(yīng)的兩個(gè)精英解作為初始解移到初始種群中。然后循環(huán)以下操作，直至產(chǎn)生PS個(gè)初始解：計(jì)算當(dāng)前精英種群中任意一個(gè)精英解和初始種群中所有解的最小偏離距離，將最大最小偏離距離對(duì)應(yīng)的精英解從精英種群移到初始種群中。

3.2 參考集產(chǎn)生方法

針對(duì)傳統(tǒng)參考集中僅包含高質(zhì)量解，容易陷入局部最優(yōu)的不足，本文采用包含b個(gè)高質(zhì)量和多樣性解的雙層參考集[16]來(lái)為增加解的多樣性，擴(kuò)大搜索范圍，避免算法過(guò)早收斂。雙層參考集Refset由兩個(gè)子集Refset1和Refset2組成，即 Refset={Refset1，Refset2}，Refset1、Refset2中分別包含b1個(gè)高質(zhì)量解和b2個(gè)多樣性解，且滿足b1+b2=b。高質(zhì)量和多樣性解通過(guò)目標(biāo)函數(shù)值選取，即在初始種群中選取b1個(gè)總流量成本最小的解作為高質(zhì)量解、b2個(gè)總流量成本最大的解作為多樣性解，得到初始 Refset={x1,…,xb1,xb1+1,…,xb}。其中，解 xk(k∈I)的總流量成本 f(xk)按從小到大排列，即 f(x1)最小，f(xb)最大。

3.3 子集產(chǎn)生方法

根據(jù)分散搜索算法的原理，采用子集產(chǎn)生方法對(duì)Refset中的解進(jìn)行操作，產(chǎn)生一系列用于子集合并方法的候選解集。為避免產(chǎn)生重復(fù)的子集，提高求解效率，改進(jìn)常用的二元子集產(chǎn)生方法，生成兩種類型的二元子集，用 X1、X2表示：X1型的子集由Refset中未更新的解連續(xù)成對(duì)選取得到；X2型的子集由Refset中新添加的解和未更新的解組合得到。

3.4 子集合并方法

針對(duì)二元子集的特點(diǎn)，采用部分映射交叉算子對(duì)子集產(chǎn)生方法產(chǎn)生的子集進(jìn)行合并操作，如圖3所示。首先，在父代解中隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，用“|”表示，則交叉點(diǎn)間的元素即為映射元素，圖3中6和2、3和1、7和4均互為映射元素。然后將父代解復(fù)制到子代解中，交換子代解交叉點(diǎn)間的映射部分，并將映射部分之外和映射部分相同的元素修改為其對(duì)應(yīng)的映射元素，如子代解1中的第一個(gè)元素為1，而映射部分已存在該元素，故將其修改為對(duì)應(yīng)的映射元素3，以此類推，即可得到交叉后的最終解。

3.5 解改進(jìn)方法及模擬退火操作

圖3 部分映射交叉

本文采用插入法作為局部搜索方法，對(duì)初始種群中的解或子集合并產(chǎn)生的新解進(jìn)行局部改進(jìn)。進(jìn)而利用模擬退火操作較強(qiáng)的局部搜索能力及其跳出局部最優(yōu)的機(jī)制再次優(yōu)化參考集中的解，以提高獲得全局最優(yōu)解的概率?；诖?，提出一種兩階段混合改進(jìn)策略。

第一階段：針對(duì)每一個(gè)子集合并產(chǎn)生的解，采用插入法將設(shè)施序列中的某個(gè)設(shè)施從其所在的位置移除，并插入到該序列的另外一個(gè)位置產(chǎn)生一個(gè)新解；比較插入前后解的目標(biāo)函數(shù)值，保留目標(biāo)函數(shù)值較小的解。重復(fù)執(zhí)行該操作，直至完成所有插入鄰域的搜索，最終輸出的最小目標(biāo)函數(shù)值對(duì)應(yīng)的解即為改進(jìn)后的解。插入法的原理如圖4所示。

圖4 插入法

第二階段：為減小運(yùn)算量，提高算法求解效率，僅將Refset中目標(biāo)函數(shù)值最小的解x1作為初始解，運(yùn)用模擬退火操作作為局部改進(jìn)法進(jìn)一步優(yōu)化解x1。

模擬退火操作中各參數(shù)定義為：初始溫度T0，終止溫度Tend，降溫速率q，鏈長(zhǎng)L。Metropolis接受準(zhǔn)則為：

其中，增量df=f(x)-f(x1)，f為目標(biāo)函數(shù)值，T為當(dāng)前退火溫度，解x為隨機(jī)交換解x1中的設(shè)施產(chǎn)生的新解。

3.6 參考集更新方法

比較解改進(jìn)方法后產(chǎn)生的新解與當(dāng)前Refset中解的質(zhì)量或多樣性，更新Refset。為實(shí)時(shí)更新參考集，及時(shí)利用新解的優(yōu)良特征，加快算法的收斂速度，本文采用動(dòng)態(tài)參考集更新方法[16]，即每生成一個(gè)新解，就對(duì)Refset進(jìn)行一次更新。若新解的質(zhì)量或多樣性優(yōu)于Refset中的解，則用新解替換Refset中質(zhì)量或多樣性方面最差的解。

3.7 算法步驟

本文以分配給第一行的設(shè)施數(shù)nu大于所設(shè)定的第一行最大設(shè)施數(shù)T2為算法的終止準(zhǔn)則。HSS流程如圖5所示。

HSS具體步驟如下：

步驟1算法參數(shù)初始化：n,PS,b,T0,Tend,L,q，內(nèi)循環(huán)最大迭代次數(shù)iItermax等，令nu=T1。

步驟2按照多樣性初始解產(chǎn)生方法生成初始種群。

步驟3插入法優(yōu)化初始種群。

步驟4生成初始參考集。

步驟5初始化算法全局近優(yōu)解xopt=x1，其中，x1為初始參考集中目標(biāo)函數(shù)值最小的解；令計(jì)數(shù)器count和i均為0。

步驟6按照3.3節(jié)～3.6節(jié)內(nèi)容進(jìn)行子集產(chǎn)生、子集合并、插入法改進(jìn)解、更新參考集操作。

步驟7運(yùn)用模擬退火操作對(duì)當(dāng)前參考集中目標(biāo)函數(shù)值最小的解x1進(jìn)行進(jìn)一步優(yōu)化。

圖5 HSS流程圖

步驟8比較算法全局近優(yōu)解xopt的目標(biāo)函數(shù)值f(xopt)和當(dāng)前解x1的目標(biāo)函數(shù)值f(x1)的大小，若f(x1)＜f(xopt)，則xopt=x1，令count=0；否則count=count+1。

步驟9若count＞h1，即在當(dāng)前nu下全局近優(yōu)解xopt連續(xù)h1次未改進(jìn)，則nu=nu+1，轉(zhuǎn)步驟11；否則i=i+1，直接進(jìn)入下一步。

步驟10若i＞iItermax，則nu=nu+1，進(jìn)入下一步；否則轉(zhuǎn)步驟6。

步驟11若nu≤T2，則轉(zhuǎn)步驟2；否則輸出算法全局近優(yōu)解xopt及其目標(biāo)函數(shù)值f(xopt)，算法終止。

3.8 算法復(fù)雜度分析

從HSS算法的流程可以看出，算法的計(jì)算時(shí)間主要花費(fèi)在迭代過(guò)程中，對(duì)于分配給第一行的設(shè)施數(shù)為nu、參考集規(guī)模為b、問(wèn)題規(guī)模為n、內(nèi)循環(huán)最大迭代次數(shù)為iItermax的問(wèn)題，算法的時(shí)間復(fù)雜度主要由以下幾個(gè)部分組成：產(chǎn)生多樣性初始種群的時(shí)間復(fù)雜度為O(n2)，插入法的時(shí)間復(fù)雜度為O(3n4)，生成初始參考集的時(shí)間復(fù)雜度為O(1)，產(chǎn)生子集的時(shí)間復(fù)雜度為O(1)，合并子集的時(shí)間復(fù)雜度為O(1)，內(nèi)循環(huán)中插入法的時(shí)間復(fù)雜度為O(3b2n4/2-3bn4)，更新參考集的時(shí)間復(fù)雜度為O(1)，模擬退火操作的時(shí)間復(fù)雜度為O(2 292n3-458n3lg(n-1))。因此，內(nèi)循環(huán)迭代iItermax次時(shí)，總的時(shí)間復(fù)雜度最差為：

本文中參數(shù)nu的取值區(qū)間跨度為3，因此，整個(gè)HSS算法的時(shí)間復(fù)雜度為：

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證所提HSS的有效性，針對(duì)設(shè)施數(shù)從9～49不同規(guī)模的24個(gè)過(guò)道布置問(wèn)題，應(yīng)用所提HSS進(jìn)行測(cè)試，并與基本SA、SS的求解結(jié)果進(jìn)行對(duì)比。算法實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Intel Core i3-2100 M，3.1 GHz，2 GB內(nèi)存，在Windows 7操作系統(tǒng)下使用MATLAB R2010b軟件開(kāi)發(fā)了所提算法的實(shí)驗(yàn)程序。測(cè)試數(shù)據(jù)來(lái)源于文獻(xiàn)[7，17-20]。

兼顧求解性能與求解效率，經(jīng)多次運(yùn)算測(cè)試，算法部分參數(shù)設(shè)置如下：T1=floor(n/2)-2,T2=floor(n/2),nu=[T1,T2]，Tend=0.1/n，L=2n，q=0.99，b=8，b1=b2=4，iItermax=200；針對(duì)n不超過(guò)15的小規(guī)模問(wèn)題，T0=100，h1=5，US=2floor((n-1)/2)，ES=14，PS=12；針對(duì) n大于 15的大規(guī)模問(wèn)題，T0=10 000，h1=15，US=1 000，ES=500，PS=40。其中，參數(shù)nu的取值區(qū)間設(shè)置參考文獻(xiàn)[7]。

為更準(zhǔn)確地說(shuō)明所提算法的求解性能，針對(duì)每種算法，每個(gè)測(cè)試問(wèn)題均運(yùn)行10次，共計(jì)720個(gè)計(jì)算結(jié)果。為更加簡(jiǎn)潔直觀地展現(xiàn)三種算法的計(jì)算結(jié)果，對(duì)其進(jìn)行了整理、歸納，得到表1所示結(jié)果，包含了目標(biāo)函數(shù)值f和解的偏差gap。其中，與當(dāng)前已知最優(yōu)目標(biāo)函數(shù)值f0的偏差gap定義為gap=(f-f0)/f0×100%，“*”表示文獻(xiàn)[7]中用精確方法求得的最優(yōu)解的目標(biāo)函數(shù)值，“+”表示啟發(fā)式方法求得的近優(yōu)解的目標(biāo)函數(shù)值，“++”表示文獻(xiàn)[9]求得的近優(yōu)解的目標(biāo)函數(shù)值。

從表1可以看出：針對(duì)設(shè)施數(shù)小于15的8個(gè)小規(guī)模測(cè)試問(wèn)題，HSS均求得了最優(yōu)解；針對(duì)大規(guī)模測(cè)試問(wèn)題，HSS求得的近優(yōu)解的f與f0的偏差均不超過(guò)0.03%，特別是對(duì)于問(wèn)題 N-30-01、N-30-02、N-30-03、N-30-04、N-30-05、sko-42-01和sko-49-01，HSS均求得了 f0，偏差為0，驗(yàn)證了HSS求解CAP的有效性。

對(duì)比表1中三種算法的求解結(jié)果：在所測(cè)試的24個(gè)問(wèn)題中，HSS求得的近優(yōu)解的f均比SA、SS求得的f更接近 f0；SA、SS的求解結(jié)果與 f0的最大偏差分別為0.18%、8.88%，大于HSS的最大偏差0.03%，表明HSS較SA、SS更具有求解優(yōu)勢(shì)。

表1 HSS和SA、SS的求解結(jié)果比較

圖6 SA和HSS的求解偏差對(duì)比

為更直觀地觀察HSS的求解優(yōu)勢(shì)，根據(jù)表1中的計(jì)算結(jié)果，繪制了HSS分別與SA、SS的求解偏差對(duì)比圖，如圖6、7所示。由圖可知，針對(duì)每個(gè)測(cè)試問(wèn)題，HSS的求解偏差gap均小于等于SA、SS的gap，表明HSS具有良好的求解性能；隨著問(wèn)題規(guī)模的增加，SA的求解偏差曲線波動(dòng)劇烈，SS的求解偏差呈逐漸上升的趨勢(shì)，而HSS的求解偏差增長(zhǎng)平緩，體現(xiàn)了HSS具有良好的求解平穩(wěn)性。由此可知，所提混合分散搜索算法較單一搜索算法和模擬退火算法在求解質(zhì)量和平穩(wěn)性方面具有優(yōu)勢(shì)。

為進(jìn)一步驗(yàn)證所提混合分散搜索算法的求解性能，將HSS與文獻(xiàn)[7]中的精確方法和啟發(fā)式方法、文獻(xiàn)[8]中的遺傳算法（CAP-GA）和分散搜索算法（CAP-SS）的求解結(jié)果進(jìn)行對(duì)比，得到如表2所示結(jié)果，包含了目標(biāo)函數(shù)值f和CPU運(yùn)算時(shí)間。

圖7 SS和HSS的求解偏差對(duì)比

分析表2可知，對(duì)于小規(guī)模測(cè)試問(wèn)題，HSS均求得了和文獻(xiàn)[7]中精確方法相同的最優(yōu)解，但HSS的求解時(shí)間遠(yuǎn)小于精確方法。隨著問(wèn)題規(guī)模的增大，精確方法的求解時(shí)間呈指數(shù)級(jí)增長(zhǎng)，最大求解時(shí)間為10 298.01 s，且當(dāng)問(wèn)題規(guī)模為15時(shí)，已無(wú)法在合理的時(shí)間內(nèi)求得最優(yōu)解，而HSS的求解時(shí)間增長(zhǎng)緩慢，最大求解時(shí)間僅為16.57 s，遠(yuǎn)小于精確方法的求解時(shí)間。針對(duì)設(shè)施數(shù)為30的測(cè)試問(wèn)題，啟發(fā)式方法和HSS求得了相同的近優(yōu)解，但啟發(fā)式方法的平均求解時(shí)間為HSS的24倍，表明HSS的求解性能優(yōu)于啟發(fā)式方法。

表2 HSS和不同算法的比較

將HSS與CAP-GA的求解結(jié)果進(jìn)行對(duì)比：在求解質(zhì)量方面，對(duì)于設(shè)施數(shù)不超過(guò)30的測(cè)試問(wèn)題，CAP-GA和HSS的求解結(jié)果相同，但對(duì)于設(shè)施數(shù)為42和49的測(cè)試問(wèn)題，HSS的求解質(zhì)量明顯優(yōu)于CAP-GA；在求解時(shí)間方面，針對(duì)每個(gè)測(cè)試問(wèn)題，HSS的求解時(shí)間均遠(yuǎn)小于CAP-GA，且隨著問(wèn)題規(guī)模的增大兩者之間的求解時(shí)間差距大幅度增加，尤其對(duì)于測(cè)試問(wèn)題sko-49-01，CAPGA的求解時(shí)間為HSS的15倍，表明HSS較CAP-GA具有求解優(yōu)勢(shì)。

對(duì)比CAP-SS和HSS的求解結(jié)果可知，對(duì)于前15個(gè)測(cè)試問(wèn)題，HSS以略大于CAP-SS的求解時(shí)間得到了相同的解，但對(duì)于更大規(guī)模的測(cè)試問(wèn)題，HSS的平均求解時(shí)間僅為CAP-SS的1/2，特別是對(duì)于測(cè)試問(wèn)題sko-42-03、sko-42-04、sko-42-05、sko-49-01，HSS 比 CAP-SS 求得了更優(yōu)的解。由此可知，較對(duì)比的CAP-SS，HSS具有求解優(yōu)勢(shì)。

根據(jù)表中數(shù)據(jù)，繪制了如圖8所示的CPU運(yùn)算時(shí)間曲線圖。需要指出的是，HSS的求解時(shí)間隨問(wèn)題規(guī)模的增大而緩慢增加，增長(zhǎng)幅度小于所對(duì)比的CAP-GA和CAP-SS，究其原因，主要在于HSS中設(shè)置了在當(dāng)前主循環(huán)nu下，若算法全局最優(yōu)解xopt連續(xù)h1次未改進(jìn)則跳出該次內(nèi)循環(huán)的機(jī)制。故隨著問(wèn)題規(guī)模的增加，測(cè)試問(wèn)題在算法終止時(shí)的總內(nèi)循環(huán)迭代次數(shù)增幅不大，因而HSS的求解時(shí)間較CAP-GA和CAP-SS增長(zhǎng)緩慢。

圖8 三種算法的CPU運(yùn)算時(shí)間比較

5 結(jié)束語(yǔ)

（1）針對(duì)過(guò)道布置問(wèn)題的求解復(fù)雜性，提出了一種混合模擬退火及分散搜索算法進(jìn)行求解。將模擬退火操作嵌入到分散搜索的解改進(jìn)方法中，進(jìn)一步優(yōu)化參考集中的解，充分利用分散搜索算法的全局搜索能力和模擬退火操作的局部搜索能力，提高獲得全局最優(yōu)解的概率。

（2）結(jié)合問(wèn)題特征，在基本分散搜索算法的基礎(chǔ)上設(shè)計(jì)了雙層參考集，增加解的多樣性，擴(kuò)大搜索范圍，避免算法陷入局部最優(yōu)；采用動(dòng)態(tài)參考集更新方法，實(shí)時(shí)更新參考集，加快算法的收斂速度；改進(jìn)子集產(chǎn)生方法，避免產(chǎn)生重復(fù)的設(shè)施序列，提高算法運(yùn)行效率。

（3）應(yīng)用所提算法對(duì)24個(gè)不同規(guī)模的過(guò)道布置問(wèn)題進(jìn)行驗(yàn)算與對(duì)比，結(jié)果表明所提改進(jìn)分散搜索算法在求解質(zhì)量和平穩(wěn)性方面優(yōu)于基本模擬退火算法和分散搜索算法，且較已有的4種方法更具求解優(yōu)勢(shì)。

[1]Drira A，Pierreval H，Hajri-Gabouj S.Facility layout problems：A survey[J].Annual Reviews in Control，2007，31（2）：255-267.

[2]Anjos M F，Hungerl?nder P.A semidefinite optimization approach to space-free multi-row facility layout[J].Zhurnal Mikrobiologii Epidemiologii I Immunobiologii，2012（5）：74-85.

[3]Nordin N N，Zainuddin Z M，Salim S，et al.Mathematical modeling and hybrid heuristic for unequal size facility layout problem[J].Journal of Fundamental Sciences，2009，5（1）：79-87.

[4]張則強(qiáng)，程文明.雙行布局問(wèn)題的分解策略及啟發(fā)式求解方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2014，20（3）：559-568.

[5]Izadinia N，Eshghi K.A robust mathematical model and ACO solution for multi-floor discrete layout problem with uncertain locations and demands[J].Computers&Industrial Engineering，2016，96：237-248.

[6]Lin Q，Liu H，Wang D，et al.Integrating systematic layout planning with fuzzy constraint theory to design and optimize the facility layout for operating theatre in hospitals[J].Journal of Intelligent Manufacturing，2015，26（1）：87-95.

[7]Amaral A R S.The corridor allocation problem[J].Computers&Operations Research，2012，39（12）：3325-3330.

[8]Ghosh D，Kothari R.Population heuristics for the corridor allocation problem[J].Tetrahedron Letters，2012，98（2）：33-40.

[9]Ahonen H，De Alvarenga A G，Amaral A R S.Simulated annealing and tabu search approaches for the corridor allocation problem[J].European Journal of Operational Research，2014，232（1）：221-233.

[10]白杰，楊根科，潘常春，等.基于改進(jìn)分散搜索算法的無(wú)人機(jī)路徑規(guī)劃[J].上海交通大學(xué)學(xué)報(bào)，2011，45（2）：173-178.

[11]Guo X，Liu S，Zhou M，et al.Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and petri nets[J].IEEE Transactions on Cybernetics，2015.

[12]González M，Vela C，Varela R.Scatter search with path relinking for the flexible job shop scheduling problem[J].European Journal of Operational Research，2015，245（1）：35-45.

[13]Grazielle B D P S，Sanches Mantovani J R，Cossi A M.Planning medium-voltage electric power distribution systems through a scatter search algorithm[J].IEEE Latin America Transactions，2015，13（8）：2637-2645.

[14]范志強(qiáng).供應(yīng)鏈訂單分配優(yōu)化模型及其模擬退火算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（25）：28-33.

[15]Kothari R，Ghosh D.A scatter search algorithm for the single row facility layout problem[J].Journal of Heuristics，2014，20（2）：125-142.

[16]Martí R，Laguna M，Glover F.Principles of scatter search[J].European Journal of Operational Research，2006，169（2）：359-372.

[17]Simmons D M.One-dimensional space allocation：An ordering algorithm[J].Operations Research，1969，17（5）：812-826.

[18]Amaral A R S.An exact approach to the one-dimensional facility layout problem[J].Operations Research，2008，56（4）：1026-1033.

[19]Anjos M F，Vannelli A.Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes[J].Informs Journal on Computing，2008，20（4）：611-617.

[20]Anjos M F，Yen G.Provably near-optimal solutions for very large single-row facility layout problems[J].Optimization Methods&Software，2009，24（4/5）：805-817.