混合模擬退火及分散搜索優(yōu)化過道布置問題

毛麗麗，張則強，朱立夏

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

1 引言

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

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

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

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

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

2 過道布置問題

2.1 問題描述

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

圖1 過道布置問題

2.2 基本假設(shè)條件

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

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

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

（4）上下兩行設(shè)施均從過道最左邊同一點開始布置。

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

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

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

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

n：問題規(guī)模，即設(shè)施的數(shù)目；

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

i,j：設(shè)施編號，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靠過道邊線中點間的橫坐標(biāo)距離；

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

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

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

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

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

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

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

圖2 解的編碼和解碼

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

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

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

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

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

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

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

3.4 子集合并方法

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

3.5 解改進方法及模擬退火操作

圖3 部分映射交叉

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

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

圖4 插入法

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

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

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

3.6 參考集更新方法

比較解改進方法后產(chǎn)生的新解與當(dāng)前Refset中解的質(zhì)量或多樣性，更新Refset。為實時更新參考集，及時利用新解的優(yōu)良特征，加快算法的收斂速度，本文采用動態(tài)參考集更新方法[16]，即每生成一個新解，就對Refset進行一次更新。若新解的質(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ù)值最小的解；令計數(shù)器count和i均為0。

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

步驟7運用模擬退火操作對當(dāng)前參考集中目標(biāo)函數(shù)值最小的解x1進行進一步優(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次未改進，則nu=nu+1，轉(zhuǎn)步驟11；否則i=i+1，直接進入下一步。

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

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

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

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

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

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

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

兼顧求解性能與求解效率，經(jīng)多次運算測試，算法部分參數(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；針對n不超過15的小規(guī)模問題，T0=100，h1=5，US=2floor((n-1)/2)，ES=14，PS=12；針對 n大于 15的大規(guī)模問題，T0=10 000，h1=15，US=1 000，ES=500，PS=40。其中，參數(shù)nu的取值區(qū)間設(shè)置參考文獻[7]。

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

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

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

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

圖6 SA和HSS的求解偏差對比

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

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

圖7 SS和HSS的求解偏差對比

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

表2 HSS和不同算法的比較

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

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

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

圖8 三種算法的CPU運算時間比較

5 結(jié)束語

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

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

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

[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]張則強，程文明.雙行布局問題的分解策略及啟發(fā)式求解方法[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]白杰，楊根科，潘常春，等.基于改進分散搜索算法的無人機路徑規(guī)劃[J].上海交通大學(xué)學(xué)報，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]范志強.供應(yīng)鏈訂單分配優(yōu)化模型及其模擬退火算法[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.