劉佳 馮震 徐越群 劉麗娜

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

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

引言

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

1 模型構(gòu)建

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

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

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

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

2.1 CS算法簡介

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

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

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

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

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

二次插值法（Quadratic Interpolation）是一種局部搜索能力較強(qiáng)的搜索方法，不需要目標(biāo)函數(shù)的導(dǎo)數(shù)信息，計(jì)算量小?？梢岳枚尾逯捣ǖ膬?yōu)勢對基本的CS算法進(jìn)行改進(jìn)。

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

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

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

式中A和B計(jì)算如下：

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

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

3 實(shí)驗(yàn)仿真與結(jié)果分析

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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