姜 婷

(1.合肥工業(yè)大學(xué)管理學(xué)院，安徽 合肥 230009；2.中共安徽省委黨校(安徽行政學(xué)院)，安徽 合肥 230022)

物流配送中心選址問(wèn)題屬于NP-hard問(wèn)題，國(guó)內(nèi)外學(xué)者嘗試了多種方法進(jìn)行求解，其中群智能優(yōu)化算法因采用啟發(fā)式求近似最優(yōu)解的思路，在求解規(guī)模較大的配送中心選址問(wèn)題中具有一定的優(yōu)勢(shì).例如，蟻群(Ant Colony，AC)算法[1]、微粒群(Particle Swarm Optimization，PSO)算法[2]、遺傳算法(Genetic Algorithm，GA)[3]等傳統(tǒng)群智能算法和一些新型智能優(yōu)化算法[4-13]廣泛應(yīng)用于求解配送中心選址問(wèn)題，獲得了較好的仿真實(shí)驗(yàn)結(jié)果.新型智能優(yōu)化算法中的人工蜂群(Artificial Bee Colony，ABC)算法[13]，是Karboga受蜜蜂的覓食行為啟發(fā)于2005年提出的，該算法起初是用來(lái)解決連續(xù)空間的多維數(shù)值計(jì)算問(wèn)題，后來(lái)被拓展到離散和組合優(yōu)化領(lǐng)域.仿真實(shí)驗(yàn)結(jié)果表明[14]，ABC算法的性能優(yōu)于差分(Differential Evolution，DE)算法、GA和PSO算法等著名進(jìn)化算法，可以有效地解決多模態(tài)和多維優(yōu)化問(wèn)題.

群智能優(yōu)化算法在處理組合優(yōu)化問(wèn)題上具有尋優(yōu)速度快、算法可移植性好等優(yōu)點(diǎn)，但同時(shí)也存在一些亟需解決的普遍性問(wèn)題，如避免早熟收斂與提高尋優(yōu)速度難以平衡，探索和開(kāi)發(fā)能力存在矛盾等.而且，實(shí)際問(wèn)題多種多樣，很難找到一個(gè)通用優(yōu)化算法，不對(duì)其作任何改進(jìn)就能解決所有問(wèn)題.因此，筆者擬對(duì)ABC算法進(jìn)行改進(jìn)，引入變鄰域搜索并優(yōu)化搜索方程，以期更好求解物流配送中心選址問(wèn)題.

1 配送中心選址問(wèn)題求解描述

研究人員通常在幾個(gè)簡(jiǎn)化的假設(shè)下描述配送中心選址問(wèn)題.本研究的配送中心選址問(wèn)題基于以下假設(shè)：(1)配送中心服務(wù)的需求總量不能超過(guò)配送中心的容量限制；(2)每個(gè)需求點(diǎn)只由1個(gè)配送中心提供服務(wù)；(3)物流網(wǎng)絡(luò)的總費(fèi)用由基礎(chǔ)設(shè)施建設(shè)的固定費(fèi)用和運(yùn)輸費(fèi)用構(gòu)成，其中運(yùn)輸費(fèi)用取決于運(yùn)輸距離.在這些假設(shè)的基礎(chǔ)上，筆者設(shè)計(jì)了如下數(shù)學(xué)模型：

(1)

(2)

(3)

(4)

模型的目標(biāo)是在N個(gè)需求點(diǎn)中選出M個(gè)配送中心，使得整個(gè)物流網(wǎng)絡(luò)的總費(fèi)用最低.(1)式中：U為物流網(wǎng)絡(luò)的總費(fèi)用；Fi為在需求點(diǎn)i建設(shè)配送中心的固定費(fèi)用；決策變量hi∈{0,1}，取1表示需求點(diǎn)i被選為配送中心，取0表示沒(méi)有被選中；決策變量zij∈{0,1}，表示需求點(diǎn)i與配送中心j的服務(wù)關(guān)系，取1表示存在服務(wù)，取0表示沒(méi)有服務(wù)；Wi為需求點(diǎn)i的需求量；dij為需求點(diǎn)i與配送中心j之間的距離；Tj為配送中心j的最大容量.約束條件(2)表示被選為配送中心的總數(shù)為p；約束條件(3)表示被服務(wù)需求點(diǎn)的需求總量不能超過(guò)對(duì)應(yīng)配送中心的容量限制；約束條件(4)表示任意需求點(diǎn)對(duì)應(yīng)的配送中心是唯一的.

2 基本人工蜂群算法

ABC算法有3個(gè)基本組成部分，即食物源、雇傭蜂和非雇傭蜂(包括跟隨蜂和偵察蜂).食物源代表問(wèn)題的可行解，解的質(zhì)量由問(wèn)題的適應(yīng)度來(lái)表示，解的優(yōu)化通過(guò)蜜蜂的搜索行為完成.搜索行為即為ABC算法的過(guò)程，其基本框架可簡(jiǎn)單描述為以下幾個(gè)階段：

過(guò)程1算法初始化階段

過(guò)程2REPEAT

雇傭蜂階段

跟隨蜂階段

偵察蜂階段

存儲(chǔ)最優(yōu)解

UNTIL(達(dá)到最大迭代次數(shù)或其他終止條件)

設(shè)在D維空間中，有N只蜜蜂組成的蜂群.初始化階段，通過(guò)偵察蜂初始化食物源(解決方案)的種群，并設(shè)置控制參數(shù)；雇傭蜂階段，在初始解的鄰域范圍搜索新解并比較新舊解的適應(yīng)度，采用貪婪法進(jìn)行選擇；跟隨蜂階段，根據(jù)解的適應(yīng)度，按照公式

(5)

概率地選擇是否跟隨，并在鄰域中搜索新解，同樣采用貪婪法進(jìn)行比較和選擇.(5)式中fi為第i只蜜蜂的適應(yīng)值.

(6)

2014年，Karaboga等[15]對(duì)ABC算法的優(yōu)化及應(yīng)用進(jìn)行了全面梳理和系統(tǒng)總結(jié)，分析了算法存在的缺點(diǎn)并提出了未來(lái)可能的發(fā)展思路.他指出，ABC算法可以作為一個(gè)進(jìn)化框架，將不同的傳統(tǒng)或現(xiàn)代啟發(fā)式算法組件集成于其中.為了提高ABC算法的收斂性，Karaboga建議圍繞不同問(wèn)題對(duì)原始結(jié)構(gòu)進(jìn)行相應(yīng)修改，如采用新的鄰域生成方法.

3 基于改進(jìn)鄰域搜索方法的ABC算法

3.1 全局最優(yōu)引導(dǎo)

群智能算法的探索和開(kāi)發(fā)能力的平衡是各種優(yōu)化算法的核心問(wèn)題之一.一般來(lái)說(shuō)，過(guò)度探索會(huì)導(dǎo)致算法收斂緩慢，而過(guò)度開(kāi)發(fā)會(huì)抑制多樣性并導(dǎo)致過(guò)早收斂，因此探索和開(kāi)發(fā)能力達(dá)到適當(dāng)平衡對(duì)有效解決問(wèn)題非常重要.Zhu等[16]分析了ABC算法的搜索方程，認(rèn)為該算法的探索能力較強(qiáng)，開(kāi)發(fā)能力較弱，導(dǎo)致算法收斂性能較差.受PSO算法的啟發(fā)，Zhu等提出了新的搜索方程.在此基礎(chǔ)上，高衛(wèi)峰等[17]結(jié)合DE算法，提出如下受全局最優(yōu)解引導(dǎo)的搜索方程：

(7)

優(yōu)化組合問(wèn)題的求解通常初期需要具備較強(qiáng)的探索能力，循環(huán)后期需要具備較強(qiáng)的開(kāi)發(fā)能力，而基本ABC算法在雇傭蜂和跟隨蜂階段采用同樣的鄰域搜索方程，是不能較好地滿足這一要求的.為了解決這個(gè)問(wèn)題，筆者設(shè)計(jì)出新的鄰域生成方法：雇傭蜂階段以當(dāng)前解引導(dǎo)，即采用(6)式產(chǎn)生鄰域；跟隨蜂階段以全局最優(yōu)解引導(dǎo)，即采用(7)式產(chǎn)生鄰域.本研究采用與文獻(xiàn)[6]相同的編碼形式，鄰域操作算子有以下3個(gè)：

(1)鄰域算子N1.在原始解的編碼中隨機(jī)選擇2個(gè)不同的位置進(jìn)行互換.

(2)鄰域算子N2.在原始解的編碼中隨機(jī)選擇1個(gè)位置，將此位置的編碼移動(dòng)到新的隨機(jī)位置.

(3)鄰域算子N3.在原始解的編碼中隨機(jī)選擇2個(gè)位置，將這2個(gè)位置之間的所有編碼進(jìn)行翻轉(zhuǎn).

3.2 變鄰域搜索

基本ABC算法的鄰域搜索方程采用隨機(jī)策略，使得算法的局部搜索能力較差.變鄰域搜索(Variable Neighborhood Search，VNS)通過(guò)系統(tǒng)地改變鄰域結(jié)構(gòu)，可以增強(qiáng)局部搜索能力，在求解復(fù)雜的大規(guī)模組合優(yōu)化問(wèn)題中表現(xiàn)良好[18-20].

3.2.1局部搜索階段 局部搜索階段采用可變鄰域下降(Variable Neighborhood Descent，VND)算法框架，通過(guò)順序使用鄰域算子Nk(k=1,2,3)來(lái)改進(jìn)當(dāng)前的解決方案.當(dāng)不可能有更多的改進(jìn)時(shí)，VND算法停止.為了縮短該階段操作的運(yùn)行時(shí)間，筆者將采用一種去重計(jì)算方法，即僅計(jì)算編碼改變部分的費(fèi)用而不重新計(jì)算新編碼對(duì)應(yīng)的總費(fèi)用.

圖1 抖動(dòng)策略Fig. 1 Shaking Strategy

3.2.2抖動(dòng)階段 局部搜索階段之后進(jìn)入抖動(dòng)階段.傳統(tǒng)的抖動(dòng)階段采用的鄰域算子與局部搜索階段相似，導(dǎo)致改變的程度較小，容易陷入局部最優(yōu)，造成早熟收斂.為了避免這一問(wèn)題，筆者通過(guò)在抖動(dòng)階段采用“分塊—打亂—重組”模式來(lái)增加解的改變程度，即先將原始解的編碼隨機(jī)切割成n塊連續(xù)的片段，再按塊打亂順序后重新組合在一起.以編碼“347508126”為例，先將它分為4塊，再打亂、重組，過(guò)程如圖1所示.

3.3 求解配送中心選址問(wèn)題的變鄰域人工蜂群算法

變鄰域人工蜂群(Variable Neighborhood Artificial Bee Colony，VNABC)算法求解配送中心選址問(wèn)題的主要步驟如下：

Step1初始化蜂群.包括蜂群規(guī)模、最大迭代次數(shù)(Cmax)和無(wú)改進(jìn)次數(shù)限制(l)等.

Step2評(píng)估每只蜜蜂對(duì)應(yīng)解的適應(yīng)度.

Step3雇傭蜂根據(jù)鄰域搜索方程(6)，按照VNS進(jìn)行局域搜索和抖動(dòng)操作產(chǎn)生新解，然后進(jìn)行貪婪選擇.

Step4跟隨蜂根據(jù)(5)式計(jì)算選擇蜜源的概率，接著根據(jù)搜索方程(7)，按照VNS進(jìn)行局域搜索和抖動(dòng)操作產(chǎn)生新解，然后進(jìn)行貪婪選擇.

Step5評(píng)估并記錄全局最優(yōu)解.

Step6記錄解未改進(jìn)次數(shù)t，若t>l則偵察蜂隨機(jī)產(chǎn)生新解.

Step7判斷是否滿足尋優(yōu)結(jié)束條件，若滿足則輸出最優(yōu)解，算法結(jié)束；若不滿足則轉(zhuǎn)step 3.

VNABC算法流程如圖2所示.

圖2 變鄰域人工蜂群算法流程Fig. 2 Flow Chart of Variable Neighborhood Artificial Bee Colony Algorithm

4 仿真實(shí)驗(yàn)

為了驗(yàn)證VNABC算法的有效性，筆者利用Matlab R2018a軟件進(jìn)行了2組對(duì)比實(shí)驗(yàn)：一是利用VNABC算法、GA、基本PSO算法、混合PSO算法[2]、基本ABC算法[4]、改進(jìn)ABC算法[5]等對(duì)算例分別進(jìn)行仿真求解；二是將VNABC算法與基本ABC算法進(jìn)行比較.實(shí)驗(yàn)采用文獻(xiàn)[3]中的算例，從12個(gè)需求點(diǎn)中選擇3個(gè)配送中心，使得總費(fèi)用最小.已知每個(gè)配送中心的容量均為13個(gè)單位，各需求點(diǎn)的建設(shè)費(fèi)用和需求量見(jiàn)表1.為了簡(jiǎn)化計(jì)算，表1中的數(shù)據(jù)已經(jīng)過(guò)規(guī)范化處理，無(wú)實(shí)際計(jì)量單位.

表1 各需求點(diǎn)的建設(shè)費(fèi)用和需求量

(1)仿真實(shí)驗(yàn)1：VNABC算法與GA、基本PSO算法、混合PSO算法、基本ABC算法、改進(jìn)ABC算法等進(jìn)行比較.

設(shè)置種群規(guī)模為80，最大迭代次數(shù)為2 000，無(wú)改進(jìn)次數(shù)限制次數(shù)為50.所有算法在相同的基本參數(shù)設(shè)置下各自運(yùn)行20次，仿真結(jié)果見(jiàn)表2，VNABC算法的最優(yōu)解結(jié)果見(jiàn)表3.

表2 各算法仿真結(jié)果對(duì)比

表3 VNABC算法的最優(yōu)解

結(jié)合表2和表3可知，VNABC算法運(yùn)行20次均得到已知最優(yōu)解，物流網(wǎng)絡(luò)為最小費(fèi)用161個(gè)單位，此時(shí)可選擇需求點(diǎn)1，4，8號(hào)作為配送中心(不是唯一最優(yōu)解).由此可見(jiàn)，VNABC算法相比其他算法在穩(wěn)定性和收斂速度方面都具有一定優(yōu)勢(shì).

采用基本ABC算法、改進(jìn)ABC算法和VNABC算法得到的最優(yōu)解迭代次數(shù)的對(duì)比結(jié)果如圖3所示.

圖3 3種ABC算法得到最優(yōu)解迭代次數(shù)的比較Fig. 3 Comparison of Iteration Times of Optimal Solution Obtained Through Three ABC Algorithms

由圖4可見(jiàn)，VNABC算法的迭代次數(shù)相比其他2種ABC算法的明顯要小，且算法穩(wěn)定性更強(qiáng).這說(shuō)明，該算法能較好地平衡探索與開(kāi)發(fā)能力，尋優(yōu)速度更快.

(2)仿真實(shí)驗(yàn)2：VNABC算法與基本ABC算法進(jìn)行比較.

筆者對(duì)基本ABC算法的改進(jìn)主要是：(1)基本ABC算法的雇傭蜂和跟隨蜂階段均是在當(dāng)前解附近進(jìn)行局部搜索，而VNABC算法的跟隨蜂階段是在全局最優(yōu)解附近進(jìn)行局部搜索；(2)在基本ABC算法的基礎(chǔ)上設(shè)計(jì)了3個(gè)鄰域算子，重構(gòu)了新的鄰域，采用變鄰域搜索方法；(3)在局部搜索之后加入抖動(dòng)環(huán)節(jié)，增強(qiáng)解空間的多樣性.為了驗(yàn)證改進(jìn)方法的有效性，筆者設(shè)計(jì)了4個(gè)方案進(jìn)行比較實(shí)驗(yàn).方案具體如下：

方案1雇傭蜂在當(dāng)前解附近搜索，跟隨蜂在當(dāng)前解附近搜索.采用基本鄰域結(jié)構(gòu)和局部搜索方法.

方案2雇傭蜂在當(dāng)前解附近搜索，跟隨蜂在全局最優(yōu)解附近搜索.采用基本鄰域結(jié)構(gòu)和局部搜索方法.

方案3雇傭蜂在當(dāng)前解附近搜索，跟隨蜂在全局最優(yōu)解附近搜索.采用3.1節(jié)的鄰域結(jié)構(gòu)和3.2.1節(jié)的局部搜索方法.

方案4采用VNABC算法.

設(shè)置種群規(guī)模為80，最大迭代次數(shù)為200，無(wú)改進(jìn)次數(shù)限制為50，實(shí)驗(yàn)結(jié)果見(jiàn)表4.

表4 VNABC算法與基本ABC算法的比較結(jié)果

比較方案1和方案2可知，采用最優(yōu)解引導(dǎo)可以提升算法的局部搜索能力和開(kāi)發(fā)能力，加快尋優(yōu)速度，但穩(wěn)定性較差，容易早熟收斂；方案3在方案2的基礎(chǔ)上改變了鄰域結(jié)構(gòu)，采用變鄰域搜索方法，尋優(yōu)速度和穩(wěn)定性均有明顯改善；方案4即VNABC算法，相比方案3進(jìn)一步增加了解空間的多樣性，可以有效平衡算法的探索和開(kāi)發(fā)能力，改進(jìn)全局和局部搜索能力.

結(jié)合表 2 和表4可知，VNABC算法的解的質(zhì)量、收斂速度及穩(wěn)定性均表現(xiàn)良好，相比其他算法在性能上有一定程度的提升.

5 結(jié)語(yǔ)

為了避免物流配送中心問(wèn)題求解陷入早熟，提高收斂速度，平衡優(yōu)化算法的探索和開(kāi)發(fā)能力，筆者對(duì)基本ABC算法作了改進(jìn)，設(shè)計(jì)出VNABC算法.首先，將雇傭蜂與跟隨蜂的鄰域搜索方程進(jìn)行區(qū)別化處理，即雇傭蜂采用當(dāng)前解引導(dǎo)，跟隨蜂采用全局最優(yōu)解引導(dǎo)，以加快向最優(yōu)解靠近的速度及提升算法的開(kāi)發(fā)能力；其次，引入變鄰域搜索，在抖動(dòng)階段采用新穎的“分塊—打亂—重組”模式，以增加解的多樣性及提升算法的探索能力；最后，采用3個(gè)鄰域算子，使算法具有較強(qiáng)的擾動(dòng)能力.仿真實(shí)驗(yàn)結(jié)果表明，VNABC算法在有效性、穩(wěn)定性、收斂速度上均有一定的優(yōu)勢(shì)，較好地平衡了探索和開(kāi)發(fā)能力.本研究是將VNABC算法應(yīng)用于配送中心選址問(wèn)題求解，但該算法是否適用于更大規(guī)模的問(wèn)題求解，是否具備解決其他問(wèn)題的可移植性，這是未來(lái)的研究方向.