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

劉佳 馮震 徐越群 劉麗娜

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

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

引言

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

1 模型構(gòu)建

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

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

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

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

2.1 CS算法簡介

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

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

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

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

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

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

針對多維問題的優(yōu)化解，可以把二次插值法應(yīng)用于求解空間中的每

一個維度。假設(shè)存在給定的三個點 ，

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

式中A和B計算如下：

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

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

3 實驗仿真與結(jié)果分析

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

4 結(jié)束語

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

參考文獻

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

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

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

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

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