變鄰域人工蜂群算法求解配送中心選址問題*

姜 婷

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

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

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

1 配送中心選址問題求解描述

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

(1)

(2)

(3)

(4)

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

2 基本人工蜂群算法

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

過程1算法初始化階段

過程2REPEAT

雇傭蜂階段

跟隨蜂階段

偵察蜂階段

存儲最優(yōu)解

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

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

(5)

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

(6)

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

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

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

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

(7)

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

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

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

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

3.2 變鄰域搜索

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

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

圖1 抖動策略Fig. 1 Shaking Strategy

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

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

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

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

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

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

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

Step5評估并記錄全局最優(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 仿真實驗

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

表1 各需求點的建設(shè)費用和需求量

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

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

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

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

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

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

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

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

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

筆者對基本ABC算法的改進(jìn)主要是：(1)基本ABC算法的雇傭蜂和跟隨蜂階段均是在當(dāng)前解附近進(jìn)行局部搜索，而VNABC算法的跟隨蜂階段是在全局最優(yōu)解附近進(jìn)行局部搜索；(2)在基本ABC算法的基礎(chǔ)上設(shè)計了3個鄰域算子，重構(gòu)了新的鄰域，采用變鄰域搜索方法；(3)在局部搜索之后加入抖動環(huán)節(jié)，增強(qiáng)解空間的多樣性.為了驗證改進(jìn)方法的有效性，筆者設(shè)計了4個方案進(jì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，無改進(jìn)次數(shù)限制為50，實驗結(jié)果見表4.

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

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

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

5 結(jié)語

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