姜 婷
(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)化搜索方程,以期更好求解物流配送中心選址問題.
研究人員通常在幾個簡化的假設(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)的配送中心是唯一的.
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)修改,如采用新的鄰域生成方法.
群智能算法的探索和開發(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).
基本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所示.
變鄰域人工蜂群(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
為了驗證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)良好,相比其他算法在性能上有一定程度的提升.
為了避免物流配送中心問題求解陷入早熟,提高收斂速度,平衡優(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ī)模的問題求解,是否具備解決其他問題的可移植性,這是未來的研究方向.