求解物流配送中心選址問題的蜘蛛猴算法

徐小平，楊 轉，劉 龍

1.西安理工大學 理學院，西安710054

2.西安理工大學 自動化與信息工程學院，西安710048

1 引言

隨著互聯網的興起，物流產業也得到了快速地發展，物流配送中心的選址設計和優化方案顯得格外重要。在物流系統中，配送中心的選址是指在一個具有若干供應點及若干需求點的范圍內選擇一定數量的地點來設置配送中心的優化過程[1]。配送中心在供貨點與用戶之間發揮著良好紐帶的作用，屬于物流系統中的一個關鍵環節，它決定著物流的配送距離、成本及配送模式，進而影響物流產業的效率[2-4]。因此，研究物流配送中心選址問題具有重要的意義。然而，物流配送中心選址問題涉及的變量及約束條件非常多，屬于典型的NP 難問題[5]，以至于一些傳統的方法難以解決該問題。目前，已有許多學者利用群智能算法對該問題進行了研究，如：差分進化算法（Differential Evolution，DE）[6]、粒子群算法（Particle Swarm Optimization，PSO）[7]、猴 群 算 法（Monkey Algorithm，MA）[8]等。但是這些算法普遍存在過早地局部收斂，求解精度不高等缺點。

2014年，Banasal等人模擬自然界中蜘蛛猴的覓食行為提出了蜘蛛猴優化算法（Spider Monkey Optimization，SMO）[9]，基于蜘蛛猴的裂變融合社會結構這一特點，將該算法抽象為局部和全局更新機制。其突出特點在于敏感參數少，魯棒性強且具有良好的全局收斂性，尤其在求解多峰、多維復雜函數中有較好的效果。目前，該算法已應用到壓力容器設計[10]、灰度圖像[11]及倫納德-瓊斯[12]等諸多問題中。但是在解決具體問題時，基本蜘蛛猴算法存在求解精度不高的缺點。因此，有必要對蜘蛛猴算法進一步改進來提高尋優性能。

2 物流配送中心選址模型

物流中心選址問題是指：在有限個數量的位置中，選取一些地點作為配送中心，并為所有位置提供貨物，使得在滿足供應各個位置所需的要求下，總成本最低。因此，本文作如下假設：（1）配送中心必須滿足所有位置的需求；（2）每個需求點有且只能由一個配送中心進行供應；（3）不考慮其他費用。基于上述假設，其目標是使各位置的需求量到與之最近配送中心的距離的乘積之和最小，由此可建立如下模型。

其中，目標函數min F 表示被選中的物流中心j 到由它配送的位置i 的需求量與距離乘積之和的最小值；是所有位置的編號集合；k 為被選中的物流中心j 到由它配送的位置i 的最大距離；Mi表示其余位置到物流中心的距離小于k 的備選物流中心的集合；hi表示位置i 的需求量；dij表示位置i 到離它較近的物流中心j 之間的距離；zij是0-1 變量，當zij為1時，表示物流配送中心j 將為位置i 供貨物；ej表示位置點和物流中心之間的需求分配關系，ej也是0-1 變量，當ej為1 時，表示位置i 被選為物流中心；r 為被選中的物流中心數量。

3 蜘蛛猴優化算法及其改進

3.1 基本蜘蛛猴優化算法（SMO）

基本蜘蛛猴算法具體如下：

（1）解的表示和初始化設Xi=(xi1,xi2,…,xin) 為目標函數的一個可行解，表示第i 只蜘蛛猴當前的位置，由下式生成：

其中，i=1,2,…,P，P 表示群體規模，Xij表示第i 只蜘蛛猴在第j 維的分量，Xminj和Xmaxj分別為第j 維的下限和上限，j=1,2,…,n，n 為優化問題的維數，是上均勻分布的隨機數。

（2）局部領導階段

該過程是每個蜘蛛猴在自己的局部小范圍內通過迭代尋找優化問題的目標函數值的過程，蜘蛛猴基于局部領導者以及小組其他成員的經驗來更新當前位置。若新位置適應度值優于原來位置適應度值，則蜘蛛猴就更新到新位置，具體過程如下：

其中，LLkj是第k 個局部群體領導者在第j 維的分量，Xrj是隨機地從第k 個群體中選出的第r 個蜘蛛猴的第j 維分量( r ≠i )，R( 0,1) 是[0 ,1] 上均勻分布的隨機數，R( -1,1) 是[- 1,1] 上均勻分布的隨機數，k ∈[1 ,MG ]，MG 為最大組數。

（3）全局領導階段

在這一階段，蜘蛛猴基于全局領導者以及局部小組成員的經驗來更新其位置，且蜘蛛猴位置更新受到概率值probi的約束，如果rand( )＜probi，則進行以下的更新：

其中，GLj是全局領導者在第j(j ∈1,2,…,n) 維的分量，fitnessi表示第i 個蜘蛛猴對應的適應度值，max fitness 表示最大的適應度值，為相應的目標函數值。

（4）全局領導學習階段

全局領導者運用貪婪選擇過程來更新其位置，將整個種群中具有最大適應度值的蜘蛛猴選為全局領導者；檢查全局領導者的位置是否更新，如果位置沒有更新，則全局限制計數增加1。

（5）局部領導學習階段

局部領導者運用貪婪選擇過程來更新它們的位置，將每個局部群體中具有最高適應度值的蜘蛛猴選為局部領導者；如果局部領導者的位置沒有更新，則局部限制計數( )

llc 增加1。（6）局部領導決策階段如果局部領導者的位置在預先決定的迭代次數沒有更新，即llc 達到了局部領導限制( )lll ，那么該組中的所有成員基于擾動率( )pr 的大小用式（1）的隨機初始化或用下式來更新位置：

其中，r1和r2是[ ]0,1 上均勻分布的隨機數。

（7）全局領導決策階段

如果全局領導者的位置在預先決定的迭代次數沒有更新，即glc 達到了全局領導限制( )gll ，那么將整個群體進行分組。每次執行該階段時，也會啟動局部領導學習階段，用來選取新建小組的局部領導者。將群體分組直到達到MG，又重新組成一個群體，即MG=1。

通過以上過程使得蜘蛛猴群不斷更新位置，直至目標函數在連續迭代的優化值沒有變化，或到達預先設定迭代次數，則算法終止，輸出最優位置和最優函數值。

3.2 基于Laplace 分布的偽反向蜘蛛猴優化算法（LOBSMO）

基本蜘蛛猴算法中蜘蛛猴的位置更新在局部領導階段、全局領導階段及局部領導決策階段進行，這三個階段的目的是控制算法的搜索精度。為了提高基本蜘蛛猴算法優化性能，這里在算法的解初始化及以上三個階段提出了如下的改進思想。

（1）初始化的改進

蜘蛛猴的初始化位置會對最優結果產生一定的影響，初始化位置分布越均勻，越有利于搜索到最優結果。相比較均勻分布產生隨機數的方法，使用Laplace分布產生隨機數更有利于探索搜索空間，發現新的潛在解，因此，該策略可以保證搜索空間的多樣性，避免陷入局部最優，逐漸向全局最優解靠近。故采用Laplace 分布的方法來產生蜘蛛猴群的初始位置，具體由如下函數來產生隨機變量，Laplace分布的概率密度函數為：

分布函數為：

從而：

其中，lap( p,q )是Laplace 分布，p ∈( -∞,∞)是位置參數，q ＞0 是尺度參數，函數f 始終關于p 對稱，且在[0 ,p] 上遞增，在[ p,∞]上遞減。如圖1為Laplace分布和均勻分布200次迭代生成隨機數的曲線比較，直觀地得出：使用Laplace 分布產生隨機數更有利于探索搜索空間，有助于找到潛在解。

圖1 拉普拉斯分布和均勻分布生成隨機數的比較

（2）局部領導階段的改進

局部領導階段中是由隨機數產生的步長，這種步長時大時小，具有不確定性。在覓食過程中，步長越大，有利于提高算法全局探索能力，但會降低尋優精度，可能會出現振蕩現象；步長越小，強調算法局部開發能力，有利于提高尋優精度，但搜索速度會降低。針對這個問題，現采用指數遞減與隨機對數遞減分段的步長取代隨機步長，使步長具有自適應性，有效平衡了全局探索能力與局部開發能力，具體更新公式如下：

從而改進后的位置更新公式為：

其中，A=0.5×rand( ).G 表示當前的迭代次數，N 表示總的迭代次數，amax和amin分別是步長的最大值和最小值。

（3）全局領導階段的改進

擬改進全局領導階段的位置更新方程，算法本身的搜索方式會對收斂速度及尋優精度有一定的影響，為了避免算法過早收斂及使蜘蛛猴快速收斂到全局最優解，故在全局領導階段改變搜索方式，直接由全局領導者引導覓食，提高了算法的收斂速度；同時，為進一步平衡算法的搜索速度與收斂精度，加入了動態學習因子：

從而改進后的搜索方式為：

其中，zmax、zmin分別是學習因子的最大和最小值，z0為平衡因子，fi表示第i 個蜘蛛猴的目標函數值，fmax、fmin分別表示目標函數值的最大值、最小值。

（4）局部領導決策階段的改進

在局部領導決策階段，隨著算法的不斷進化，當前的局部最優解越來越接近全局最優解，那么對算法的局部搜索能力要求就越高。而該階段蜘蛛猴群的位置是不斷變化的，毫無規律，具有很大的隨機性，不利于在局部小范圍內尋找最優解。為了克服這個缺點，引入偽反向學習策略來產生偽反向種群，增加了種群的多樣性，這樣蜘蛛猴群能夠在局部小范圍內進行精細搜索，避免了跳過最優解的弊端，然后從當前種群和偽反向種群進行精英選擇，從而有效地找到最優解。具體過程如下：

根據概率論，有50%的反向解會更優。因此，基于當前解和反向解，反向解具有加速收斂并提高算法精度的潛力。

若偽反向解的適應度值優于當前解的適應度值，則用偽反向解QOX 替換當前解X ；否則，當前解X 保持不變。這樣，在用式（12）更新蜘蛛猴群位置之前利用上述偽反向學習策略產生全局領導者的位置，以便于更精確地找到最優解，從而提高了算法的尋優性能。

3.3 數值實驗與分析

為了驗證所給LOBSMO 的有效性，選取了9 個經典測試函數進行性能測試。

（1）Sphere函數：

（2）Ellipsoidal函數：

（3）Griewank函數

第二個樂段（B段）就像是一首勞動大軍的進行曲，調性轉為C大調。右手好像是三個聲部的勞動者的合唱，左手是強而有彈性的節奏襯托。音樂雄強，氣勢宏大，這是李樹化鋼琴曲中最雄強有力的作品。

（4）Ackley函數：

（5）Zakharov函數：

（6）Levi Montalvo 2函數：

（7）Alpine函數：

（8）Levi Montalvo 1函數：

（9）2D tripod函數：

以上9個測試函數的理論最優值均為0，其中f1、f2為單峰函數，f3～f7為多峰函數，f8、f9為復合函數，在20維的情況下進行仿真實驗。表1給出了LOBSMO在9個測試函數獨立運行50次得到的最優值、平均值及標準差。為了說明改進算法的優越性，將LOBSMO 與文中所提的DE[13]、PSO[14]、MA[15]及SMO[9]進行了比較，結果如表1。且各算法的參數設置如下，DE：雜交概率CR=0.5 ，變異概率F=0.1 ；PSO：學習因子c1=c2=1.496 ，慣性權重最大值wmax=0.9 ，慣性權重最小值wmin=0.2，速度最大值vmax=6；MA：步長a=0.1，視野長度b=0.5 ，跳區間[c ,d ]=[- 1,1] ，爬的迭代次數Nc=10；SMO：MG=5，gll=50，lll=1 500，pr=0.8；LOBSMO：pr=0.4，p=1，q=2，amax=0.8，amin=0.5，zmax=0.8，zmin=0.5，z0=0.5。其他參數與SMO相同，5 種算法種群規模都設為50。總迭代次數為1 000，在20維情況下進行測試。

根據表1各項結果得出：LOBSMO對于f2、f3和f9的求解結果達到了理論最小值0。對于f5，PSO的標準差為0，但其最優值和平均值都為1 000，說明每次求解的值都很大，精度低。除了f5，LOBSMO對每個測試函數求解的最優值、平均值和標準差都優于DE、PSO、MA及SMO。因而，所提的改進策略效果較優。圖2 展示了5 種算法關于f1、f8的收斂曲線圖，從圖中可看出：LOBSMO的收斂精度明顯優于其他4種算法。

表1 LOBSMO與對比算法關于測試函數的結果

圖2 5種算法的收斂曲線圖

表2 LOBSMO與4種算法的Wilcoxon秩和檢驗結果

由表2的P 和H 值可總結出：對于全部9個測試函數，LOBSMO 與SMO、MA、PSO、DE 的Wilcoxon 秩和檢驗結果中，H=1 說明每兩組數據都有顯著差異，P值都小于1×10-10，并且LOBSMO 的精度高，因此，LOBSMO 優于所對比的算法，其尋優性能得到了很大的改善。

4 改進的蜘蛛猴算法求解物流中心選址問題

4.1 求解步驟

利用改進的蜘蛛猴優化算法求解物流配送中心選址問題，就是以式（1）為目標函數，尋找其最小值。在求解過程中，它們的對應關系為：算法中每個蜘蛛猴的位置對應求解問題的一組可行解，種群規模對應備選的方案數目，搜索空間的維數對應備選的城市個數，選出全局領導者的位置對應配送中心。具體求解步驟如下：

步驟1 設定蜘蛛猴算法的參數值，如種群規模P，總的迭代次數N 等參數。

步驟2 用round( )函數對式（15）中的分量取整，給出種群中每個蜘蛛猴的初始位置。計算出蜘蛛猴群中個體當前位置的適應度值，找出當前最優的位置及對應的適應度值并記錄，將每個小組中適應度值最優的蜘蛛猴選為局部領導者后，將局部領導者中具有最優適應度值的猴子選為全局領導者。

步驟3 執行局部領導階段，用分段步長式（16）取代隨機步長。根據式（17）不斷進行覓食，計算該階段位置更新后，蜘蛛猴群中個體當前位置的適應度值，如果有更好的適應度值，則更新蜘蛛猴群位置到較好適應度值相對應的位置。

步驟4 執行全局領導階段，由式（19）產生新的蜘蛛猴位置，向全局領導者位置靠近。

步驟5 依次執行全局領導學習階段、局部領導學習階段，判斷全局和局部領導者的位置是否更新，如果全局領導者的位置沒有更新，則glc 增加1；如果局部領導者的位置沒有更新，則llc 增加1。

步驟6 執行局部領導決策階段之前，用偽反向學習策略式（20）、（21）產生全局領導者，再根據式（12）繼續更新蜘蛛猴的位置，計算蜘蛛猴群中個體當前位置的適應度值，如果有更好的適應度值，則更新蜘蛛猴群位置到較好適應度值相對應的位置。

步驟7 執行全局領導決策階段，判斷glc 是否達到了gll ，如果達到則將整個大群體進行分組，即局部群體數增加1；群體分組直到達到MG ，又重新組成一個群體，即MG=1。

步驟8 重復步驟3～7，直至滿足終止條件，算法結束，輸出最優位置和最優適應度值，即得到物流中心的城市位置編號和最優值。

4.2 仿真實驗

這里采集了中國31 個城市的坐標，從中選出6 個配送中心。如表3 為城市坐標和所需配送的貨物量，表中，( x,y )代表中國31個城市的坐標，hi表示各城市的需求量。

表3 31個城市的位置及其對應的需求量

用LOBSMO 求解該問題時，算法參數設置與3.3節中數值實驗與分析的參數相同。用LOBSMO 求解一次31 個城市的物流中心選址問題，得到的最優值為5.496 5E+005，選出的配送中心為5-9-12-17-20-27。接著，利用DE、PSO、MA 及SMO 進行一次求解得到的最優值分別為6.860 9E+005、6.205 2E+005、5.827 2E+005、6.014 4E+005；相應的配送中心分別為8-11-16-17-21-26，1-2-3-4-5-7，3-5-9-14-20-27，5-9-14-19-22-28。這5種算法求解過程收斂曲線如圖3所示。進一步利用5個算法分別對31 個城市物流選址問題進行50 次求解，得到的最優值、平均值、中位數和標準差如表4所示。

圖3 對31維物流中心選址尋優曲線圖

為了進一步說明LOBSMO 的有效性，收集了中國100 個城市的坐標，要選出21 個物流配送中心。如表5為各城市具體的坐標及對應的貨物量。利用以上5 個算法分別求解這100 個城市的物流中心選址問題，LOBSMO、DE、PSO、MA 及SMO 求解的最優值分別為1.077 3E+006、1.206 7E+006、1.202 6E+006、1.109 5E+006、1.127 7E+006；求解的物流配送中心分別為4-5-9-12-16-21-27-33-37-47-55-58-59-63-73-75-80-90-93-94-99，1-7-12-27-29-31-43-48-52-60-63-64-67-72-78-80-87-89-94-96-10，1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21，4-10-14-22-29-32-36-37-43-46-47-49-55-56-61-72-75-80-86-97-99，1-3-4-10-11-15-22-24-25-27-30-37-51-58-66-74-75-80-81-91-94。求解過程的收斂曲線均如圖4所示。用5種算法分別進行50次求解，其最優值、平均值、中位數和標準差仍如表4所示。

表4 5種算法求解31維及100維選址問題的結果

從對31個和100個城市的仿真結果可得出：LOBSMO都能求解到最優值，即需求量與運輸距離乘積之和的最小值。SMO、MA 的求解效果次之，DE 尋優結果最差。同時LOBSMO得到的平均值、標準差都最小，說明每次的求解結果都比較接近而且較優，具有一定的魯棒性。且由圖3及圖4可看出，LOBSMO可以快速地求解到最優值，說明了該改進算法有效地平衡了求解精度與收斂速度之間的關系。

圖4 100維物流中心選址尋優曲線圖

箱型圖[17]是用來說明一組數據分散程度情況的統計圖。為了更直觀地觀察LOBSMO 的優越性，將5 種算法分別求解31維及100維實例得到的50次結果用箱型圖展示出來，如圖5及圖6所示。

表5 100個城市的位置及其對應的需求量

圖5 31維物流配送中心選址問題的箱型圖

圖6 100維物流配送中心選址問題的箱型圖

由圖5及圖6可得出，LOBSMO求解不同維度的實例50次得到的最大值、最小值（圖中黑色橫線）及中位數（圖中紅線）都優于SMO、MA、PSO及DE，而且LOBSMO具有最小的高度。MA的尋優結果次之，DE高度最大，故其效果最差。因而，改進蜘蛛猴算法的優化性能有了明顯提高。

5 結束語

針對蜘蛛猴優化算法求解物流中心選址問題效果不佳這一問題，本文提出了基于Laplace 分布的偽反向蜘蛛猴算法來求解該問題。首先，在基本蜘蛛猴算法中，用Laplace分布產生隨機數來初始化蜘蛛猴群，增加了初始種群的多樣性。在局部領導階段，采用非線性遞減分段的步長，有效平衡了全局探索與局部開發能力。改變了全局領導階段的覓食方式，加快了收斂速度。局部領導決策階段引入偽反向學習策略，避免算法陷入局部最優。通過9個測試函數和Wilcoxon秩和檢驗，說明所提改進算法是可行的。然后，利用改進算法分別求解31維及100維的物流中心選址問題。最后，結合所求結果及箱型圖驗證了該算法的優越性，為解決多維復雜優化問題提供了一種有效的方法。