基于HICS算法的電力物資配送中心選址研究

王喜平， 郄少媛， 趙 齊

(1. 華北電力大學 經濟管理學院，河北 保定 071003； 2. 中國郵政研究院技術應用研究中心，北京 100096)

0 引言

物流系統作為國民經濟發展的動脈和基石，被譽為現代經濟發展的加速器。配送中心在整個物流系統中起著承上啟下的樞紐作用。配送中心的選址直接決定著整個物流系統的成本和效率。電力物資配送中心選址則是電力物流系統規劃的基礎和核心。目前我國電力系統中普遍存在物資配送點多、配送責任不明確等問題，致使配送成本高、效率低。因此，對電力物資配送中心選址問題進行研究，不僅有助于提高電力物資的利用效率，而且對提高電力企業的整體物流水平、降低配送成本均具有重要的現實意義。

目前關于配送中心選址的研究可以分為兩類，一類基于傳統的決策理論，如交叉中值法[1]、重心法[2]、熵權法[3]、模糊綜合評價法[4]、灰色關聯度分析[5]等，通過對指標權重與選址方案的排序得到最佳配送中心；第二類基于人工智能技術對選址規劃模型進行人工仿真模擬得到選址的最優解，一般采用的人工智能技術主要有BP人工神經網絡算法[6]、改進遺傳算法[7]、改進模擬退火算法[8]、改進魚群算法[9]等。以上研究共同的缺陷在于尋優結果不夠理想，探索更為有效的優化算法成為學者努力的方向。

布谷鳥算法(Cuckoo Search Algorithm，CS)作為一種新穎的仿生進化群算法，最早是Yang(2009)提出的，主要依據布谷鳥的巢寄生繁殖機理和lévy分形搜索原理，因其具有參數少、操作性強等優點，自提出后便被廣泛用于各種研究領域[10～13]。但原始的布谷鳥算法只能用于求解連續性優化問題，盡管一些學者嘗試對此算法進行改進，如李志平等(2016)提出用云模型對布谷鳥算法進行優化[14]；Ouyang(2016)采取離散的CS算法來處理TSP問題[15]；Fateen(2014)使用基于梯度的布谷鳥搜索算法[16]；陳明和張靠社(2016)對布谷鳥搜索算法進行了自適應改進[17]。但就布谷鳥算法搜尋精度方面還需進行系統全面的研究。基于此，本文擬對布谷鳥算法做進一步改進，并以此求解電力物資配送中心選址問題。

1 問題描述與理論假設

配送中心是對物資進行出庫作業并負責送貨至終端客戶，以達到流通周轉的物流中心。電力物資配送中心是服務于電力企業，使得電力企業運行所需的生產資料以及維持生產所需的維修物資得到有效周轉的物流中心。

目前，我國電力企業物流發展相對不完善，實現既滿足庫存量最小，又能保證客戶需求的目標仍然有很大困難。電力物資配送中心表現出以下特點：(1)各配送中心獨立存在，未形成資源共享；(2)配送中心組織結構混亂；(3)配送中心數量多，責任不明確。以上問題表明，電力物資配送中心的設計及選址方面存在著嚴重的問題。按照當前提倡的物資集約化管理的要求，重新規劃物資配送中心是十分必要的。

電力物資配送中心選址問題可以描述為：在n個物資需求點中選擇m個物資配送中心，使得選取到的m個配送中心與其他n個物資需求點的運輸及存儲等的總成本最低。并同時滿足以下約束條件：配送中心的物資供應量可以滿足物資需求點的需求；一個物資需求點所需要的物資只能由一個配送中心提供；不考慮物資供應上到配送中心的運輸費用。據此，電力物資配送中心選址的數學模型可描述如下：

min(cost)=T+S+P=

ρ·(disti,j-D)·δi,j·ui,j)

(1)

s.t.

?j

(2)

ui,j≤hj,i∈M,j∈N

(3)

(4)

hi∈{0, 1},i∈M

(5)

ui,j∈{0,1},i∈M,j∈N

(6)

M={i|i=1,2,…,m},N={j|j=1,2,…,n}

(7)

式(2)～(7)是約束條件式：式(2)表示j需求點的物資需求僅由唯一物資配送中心供應：式(3)表明每個物資需求點必定有一個物資配送中心為其配送物資；式(4)表示某個物資配送中心選擇的物資需求點數量；式(5)～(7)為相關的定義及整數約束。

2 電力物資配送中心選址模型的算法設計

2.1 基本布谷鳥算法(CS)

CS算法是一種模仿布谷鳥尋覓窩巢產蛋行為的啟發式智能優化算法，算法的具體步驟如下：

(1)種群的初始化：隨機選取n個鳥巢的初始位置，計算n個鳥巢的適應度值，確定初始位置中的最優鳥巢位置，對最優位置保留為寄生巢；

(2)搜尋：搜索每個鳥巢的子代位置，并計算其所在位置的適應度值，進一步比較兩代的適應度值，對最優的位置進行保留；該方法在搜尋的過程中采用Lévy飛行模式，飛行運動的每一步包含兩個因素控制：首先是飛行的方向，運算中一般選取均勻分布函數；其次是步長，其步長服從Lévy分布，布谷鳥算法中使用了Mantegna進行步長的選擇。具體表示為：

(8)

其中，β=k-θ，1<θ<3，α和β都服從正態分布，即

(9)

式中：

(10)

σv=1

(11)

其中，ζ是標準Gamma函數，ζ取1.5，此概率分布的方差和均值都是無界限的。

(12)

(13)

其中，L(θ)：β=k-θ，1<θ<3，步長大小是通過固定的算法實現。

(14)

式中：rand表示隨機數。本文的選址問題區別于一般的萊維飛行中的連續飛行，本文引進離散背包問題的計算公式。

(3)決策：通過比較隨機數r與發現外來鳥蛋的可能性pa進行決策。若r>pa，則表示鳥蛋會被發現并破壞，應隨機改變寄生巢的位置，回到步驟(1)；若r>pa，則表示不會被發現，因此不需要做出改變。若r>pa的情況發生，需要循環進行前面的步驟，挑選出最優的鳥巢位置，做出決策。

(4)比較：若f滿足約束條件或滿足運算的結束條件，則決策即為全局最優解，反之，返回步驟(2)。

基本布谷鳥算法利用 Lévy飛行機制進行尋優，搜尋過程中局部信息運用不充分，致使該算法在每個鳥巢周圍無法細致尋優。該算法表現為高度隨機跳躍性，對收斂性無法確定，收斂性差的情況下，運算時間變長，同時搜索能力較差。

2.2 改進布谷鳥算法

針對基本布谷鳥算法中局部信息運用不充分、收斂性差的問題，提出了對放棄概率、步長因子的改進，同時隨機數的產生部分增添了Halton序列，實現隨機數選取的密集性及科學化。

(1)Halton序列選取隨機數

Halton序列是一種低偏差隨機序列。其構造相對較為簡單，因此得到了廣泛的應用。Halton序列的定義如下：

xn=(φb1(n),…，φbj(n),…，φbd(n))

(15)

Halton序列常常被用來產生空間點，Halton序列的產生，即選取一個質數作為基數，然后不斷地切分，從而形成一些不重復并且均勻的點，每個點的坐標都在0～1之間。以一維數軸生成Halton序列為例：取2作為基數，那么首先對(0,1)進行切分，得到1/2；最終得到的數列為：1/2,1/4,3/4,1/8,5/8,3/8,7/8,1/16,9/16，…。由此可以看出，Halton序列得到的數列分布均勻且密集。將Halton序列運用于布谷鳥算法中隨機數的產生，可以使產生的隨機點分布更為均勻，從而使得布谷鳥搜索的搜索結果更優。

(2)步長及發現概率的改進

在基于Halton序列的改進布谷鳥(HICS)算法基礎上，進一步對鳥巢的放棄概率pa與步長因子?0進行改進。在初始的計算流程中，放棄概率及步長因子需要保證足夠大，增加初始的可行解。隨著計算次數的增加，二者的取值應減小，加快收斂速度。具體pa與?0的公式見(16)。

(16)

式中：t表示當前迭代次數；tmax表示最大迭代次數。pa,max、pa,min表示放棄概率pa的最大值與最小值，同理?max、?min表示?0的最大與最小值。假定取pa,max=0.5，pa,min=0.1，?max=0.015，?min=0.005，tmax=1 000。m1、m2為次冪，控制兩個因子的變化程度。為了保證該算法在整體搜尋能力與局部搜索能力之間的平衡，借鑒相關研究成果，假定m1=0.5，m2=3，pa與?0隨迭代次數變化曲線如圖1所示。

圖1 pa與?0隨迭代次數變化圖

從圖1可以看出，pa在t<750的情況下下降較慢，在t達到750步時，pa仍大于布谷鳥算法中的默認值0.25，在t>750的情況下較快地降至最小值；而在t<200的情況下，隨著t的增大，下降趨勢明顯，當t超過200后，小于布谷鳥算法中默認值0.01，且在迭代后期取值保持在最小值范圍。

以上對于發現概率及搜索步長的改進，能夠避免陷入局部最優解的困境且兼顧算法的收斂性。在迭代后期，加強局部的精細搜尋，使得到的結果相對最優。

3 算例分析

3.1 基礎數據

以A省電力公司作為研究對象，對其電力物資配送中心選址進行研究。該算例中包含22個物資需求點(n=22)。根據A省的宏觀建設規劃，建設3個物資配送中心(n=3)，通過求得配送總成本最優，對其進行科學的物資配送中心選址，以期優化電力物資配送。

根據物資需求點的地理分布，用MATLAB繪制22個物資需求點的相對位置圖，具體見圖2。

圖2 物資需求點相對位置圖

本文涉及的22個物資需求點的needj(需求量)與位置坐標見表1。

關于布谷鳥算法中的相關的參數設置如表2。

3.2 物資配送中心選址結果分析

將以上設置的參數取值代入基于Halton序列的改進布谷鳥算法中，對A省電力物資配送中心進行選址研究。用MATLAB進行程序的運行，得到A省電力物資配送中心選址的優化結果，見表3，收斂性見圖3。

根據表3可以得到，A省物資的總配送費用為14 045元。配送中心 11負責向物資需求點1,8,10,15,19,20,21進行電力物資配送，配送中心7負責向物資需求點2,3,4,5,6,9,17進行電力物資配送，配送中心14負責向物資需求點12,13,16,18,22進行電力物資配送。由圖3可以得出，該算法在迭代300次后趨于穩定。根據歷史經驗，其收斂性相對較好。基于Halton序列的改進布谷鳥算法得到的配送中心選址方案具體如圖4所示。

表1 物資需求點坐標及需求量

表2 參數設定

表3 基于Halton序列的改進布谷鳥算法求解A省配送中心選址的結果

圖3 HICS算法選址優化圖

圖4 HICS算法A省物資配送中心選址及配送圖

為了進一步驗證基于Halton序列的改進布谷鳥算法的有效性與優越性，進一步對比了傳統布谷鳥算法及遺傳算法對A省電力物資配送中心選址的運行結果，具體見表4和圖5。

由表4可得，CS算法得到的 A省物資的總配送費用為14 520元。GA算法得到的 A省物資的總配送費用為14 700元。相比遺傳算法，布谷鳥算法總配送費用較低。這說明布谷鳥算法的尋優能力較好。相比傳統布谷鳥算法和遺傳算法，基于Halton序列的改進布谷鳥算法在收斂速度、計算時間和經濟性上均有顯著提高。

表4 CS及ICS求解A省物資配送中心選址的結果

圖5 對比收斂圖

圖3與圖5的3個收斂圖對比可以發現，HICS算法迭代次數為300次時，迭代結果最優，而CS算法迭代次數為355次左右時，迭代結果收斂；GA算法在迭代400次后，獲得全局的最優解。這說明，布谷鳥算法的收斂速度明顯優于遺傳算法。而基于Halton序列的改進布谷鳥算法，對步長及發現概率作出改進，使得其收斂性優于布谷鳥算法。

上述的運算結果表明，本文將改進的布谷鳥算法用于電力物資配送中心選址問題具有科學性。HICS算法的結果優于CS、GA，說明改進布谷鳥算法的尋優結果更好，且收斂速度、計算精度都有所提高，驗證了改進布谷鳥算法的優越性，改進布谷鳥算法在求解物流配送中心選址問題上是一種有效的算法。改進的布谷鳥算法能夠有效解決多目標離散點的選址問題，選址的結果能夠提高電力物資的利用效率，降低企業配送總費用，指導現實的選址及配送問題。

4 結論

本文提出了一種基于Halton序列的改進布谷鳥算法，求解電力物資配送中心的選址問題。針對CS算法在求解物資配送中心選址問題時存在的搜索精度低，收斂速度慢易陷入局部最優的缺陷，HICS算法對CS算法萊維飛行中的步長及發現概率進行了改進，這一改進可以使算法平衡局部最優與整體最優，同時可以保證算法的收斂速度較快；另外采用低偏差的Halton序列產生隨機數，可以使產生的隨機點分布更為均勻，保證了算法的搜索精度。以A省供電公司電力物資配送中心選址問題為例，進行模型的實證分析，對比分析了GA、CS及HICS的選址結果。結果表明HICS算法能夠有效解決多目標離散點的選址問題，選址的結果能夠提高配送效率，有利于電力企業的物流發展，指導現實的選址及配送問題。