布谷鳥搜索算法在超市配送中心選址問題中的應用

劉佳 馮震 徐越群 劉麗娜

摘 要：以節省企業各項運營成本和最小投資費用為目標，建立了連鎖超市配送中心選址問題的數學模型。為解決優化選址問題，對基本的布谷鳥搜索算法（Cuckoo Search，CS）進行了研究，鑒于CS算法局部搜索能力差、進化后期收斂速度慢等缺陷，考慮到二次插值法是一種局部搜索能力較強的搜索方法，提出了一種基于二次插值法的布谷鳥搜索算法（QI_CS）。仿真實驗結果表明，提出的QI_CS算法不但降低了計算的復雜度，大幅提高了算法的收斂能力和求解精度，更優化了選址模型，而且為解決物流選址問題提供了新的有效途徑。

關鍵詞：布谷鳥搜索算法；二次插值法；配送中心；選址

引言

文章以連鎖超市物流配送中心選址模型為研究對象，以構建行之有效的最優選址方法為研究目標，考慮運輸成本、管理成本、建設成本等約束條件的基礎上，建立物流配送中心選址問題的綠色數學模型。為了提高求解該數學模型算法的收斂速度和求解精度，獲得最佳選址方案，借鑒智能仿生算法——布谷鳥搜索算法對初值、參數選擇不敏感、魯棒性強、參數少、易實現等諸多優點，將該算法用于求解連鎖超市物流配送中心綠色選址模型，并采用二次插值法對基本的布谷鳥搜索算法的局部搜索能力進行改進。整合后的新算法求解的選址方案將改善配送中心的服務方式，提高服務質量和服務效率，降低服務成本等，從而影響企業的利潤和市場競爭力，實現經濟的可持續發展。

1 模型構建

本模型要研究的問題是：在模型中設置幾個配送中心，確定配送中心應選在哪里，供貨點如何向現有的備選配送中心送貨，每個配送中心配送哪些需求點（超市）等。物流配送中心的選址問題屬于最小費用問題，即求解運輸費用、運營費用、固定建設費用等之和為最小的優化問題。

首先，為建立模型做以下假設：備選點為離散的點，貨源點、備選點和需求點都是已知，需求點的需求量為己知；從貨源到配送中心和從配送中心到需求點的距離及單位運價為己知；所有的貨物都經由配送中心到需求點；每個需求點由一個配送中心配送貨物；貨源點的生產能力能滿足用戶需求；所配送產品或者商品能一次運輸完成；物運輸成本費用是運輸數量和運輸距離等的函數，與運輸數量呈正比例關系；新的配送中心位置只在符合一定條件的地點范圍內考慮。

配送中心選址模型的建立主要考慮四個方面的費用：一是配送中心的建設費用；二是從供貨點到配送中心的運輸費用；三是從配送中心到需求點（各個超市）的運輸費用；第四是貨物在配送中心的流轉和管理費用之和。

2 基于二次插值法的CS算法

2.1 CS算法簡介

為了模擬布谷鳥尋窩的方式，需要設定以下三個理想的狀態[4]：

（1）布谷鳥一次只產一個卵，并隨機選擇鳥窩位置來孵化它；（2）在隨機選擇的一組鳥窩中，最好的鳥窩將會被保留到下一代；（3）可利用的鳥窩數量n是固定的，一個鳥窩的主人能發現一個外來鳥蛋的概率pa∈[0，1]。為方便起見，最后這個假設可以近似理解為被新巢替換（新的隨機解決方案） 的概率為pa。在算法中，每個巢里的一個布谷鳥蛋代表一個解決方案，以及一個布谷鳥蛋代表了一種新的解決方案。目的是利用新的以及潛在的更好的解決方案，來取代一個在巢里的不那么好的解決方案。

在這三個理想狀態的基礎上，布谷鳥尋窩的路徑和位置更新公式如下：

式中Xit表示第i個鳥窩在第t代的鳥窩位置，？茌為點對點乘法；？墜表示步長的控制量；L（？姿）為Levy隨機搜索路徑，并且L～u=t-？姿，（1<？姿？燮3）。通過位置更新后，用隨機數r∈[0，1]與pa對比，若r>pa，則對Xit+1進行隨機改變，反之不變。最后保留測試值較好的一組鳥窩位置Yit+1，此時仍記為Xit+1。

2.2 基于二次插值法的CS算法

二次插值法（Quadratic Interpolation）是一種局部搜索能力較強的搜索方法，不需要目標函數的導數信息，計算量小。可以利用二次插值法的優勢對基本的CS算法進行改進。

針對多維問題的優化解，可以把二次插值法應用于求解空間中的每

一個維度。假設存在給定的三個點 ，

分別計算這三點的適應度值或者函數值得到fa、fb、fc，并且，其中最小的是fb。對每個維度分別使用二次插值法，則可得到下面的結果。假設近似極小值點是：

式中A和B計算如下：

在算法的每一次迭代中，xa為當代鳥窩個體當前位置，xb為當代的最優鳥窩個體位置、xc為當代的最差鳥窩個體位置，并且xa？埸{xb，xc}，xb的適應度值最小。

文章以后將基于二次插值的布谷鳥搜索算法簡稱為QI_CS算法。

3 實驗仿真與結果分析

利用文章提出的QI_CS算法對文獻[4]中的數據進行驗證，提供數據如下：某超市有兩個貨源供應點K1和K2，現有連鎖超市即需求點A1、A2、A3、…、A8，共8個，有6個物流配送中心地址可供選擇，分別為P1、P2、…、P6，其他數據參可看相關文獻。

4 結束語

文章提出了一種改進的布谷鳥搜索算法-QI_CS算法，用于求解物流配送中心選址模型，新算法針對基本CS算法的不足，將二次插值法引入到布谷鳥搜索算法中，增強了算法本身的局部搜索能力，充分利用了更多局部區域的優化信息，從而得到了精度更高的全局最優解，克服了傳統CS的不足。

參考文獻

[1]申慧，丁北，宋治飛.基于免疫優化算法的選址問題研究[J].才智，2013（20）：274.

[2]王凡，賀興時，王燕，等.基于CS算法的Markov模型及收斂性分析[J].計算機工程，2012，38（11）：180-182.

[3]李煜，馬良.新型元啟發式布谷鳥搜索算法[J].系統工程，2012，30（8）：64-68.

[4]武建娜，崔志華，劉靜.基于二次插值法的社會情感優化算法[J].計算機應用，2011，31（9）：2522-2525.

[5]隋崴崴，宋現允，付蕾.物流配送中心選址數學模型和算法問題研究[J].物流技術，2013，32（6）：158-159.