基于改進蜂群算法的模糊需求冷鏈物流車輛路徑優(yōu)化

姜婷

摘要針對基本人工蜂群算法容易早熟收斂等問題，提出了3種鄰域生成策略，并對當前解進行局部搜索和進化。仿真試驗表明，該算法在求解相關(guān)問題上具有有效性，對求解用戶模糊需求下的冷鮮品冷鏈物流車輛路徑優(yōu)化問題具有一定的參考價值。

關(guān)鍵詞改進蜂群算法；模糊需求；鄰域生成策略；冷鏈物流車輛路徑優(yōu)化

中圖分類號TS391文獻標識碼A文章編號0517-6611（2017）21-0213-03

Optimization of Coldchain Logistics Vehicle Routing with Fuzzy Demand by an Improved Artificial Bee Colony Algorithm

JIANG Ting

（Department of Information Engineering， Anhui Economic Management College， Hefei， Anhui 230059）

AbstractAiming at the premature convergence problem of the basic artificial bee colony algorithm， 3 neighborhood generation strategies were proposed， and the local search and evolution of the solution were carried out. Simulation test results showed that the proposed algorithm was effective in solving related problems， and had a certain reference value for solving the coldchain logistics vehicle routings optimization problem of cold and fresh goods under the fuzzy demand of users.

Key wordsImproved bee colony algorithm；Fuzzy demand；Neighborhood generating strategy；Coldchain logistics vehicle routings optimization

隨著我國居民生活水平的提高，人們對冷鮮品的需求不斷增大。冷鮮品對運輸和儲存環(huán)境的要求較為嚴格，容易腐壞變質(zhì)，物流費用占冷鮮品總成本的比例較高。因此，如何提高冷鏈運輸效率具有較高的研究價值，冷鏈車輛路徑優(yōu)化是其中一個關(guān)鍵的研究領(lǐng)域。該問題是一個NP（非確定多項式）難題，很多學(xué)者采用啟發(fā)式算法進行求解并取得較好效果。韓印等[1] 采用綜合節(jié)約算法求解了考慮道路狀況的冷鏈路徑優(yōu)化問題。潘東靜[2] 采用遺傳算法對需求模糊下的農(nóng)產(chǎn)品冷鏈車輛路徑進行了優(yōu)化。曹倩等[3]改進了遺傳算法，在選擇操作前根據(jù)非劣解水平進行排序，并利用擁擠程度對同級的不同個體進行排序。陳夢等[4] 在冷鏈物流路徑優(yōu)化模型中加入制冷成本和貨損成本，采用遺傳算法進行了優(yōu)化和求解。白燾等[5] 基于人工蜂群算法求解了冷鏈物流配送車輛路徑。王淑云等[6] 將K-means聚類算法、蟻群算法和隨機動態(tài)規(guī)劃算法相結(jié)合，構(gòu)建并求解了具有配送時限要求的冷鏈品多溫共配路徑優(yōu)化模型。王咪等[7] 將2-Opt算法與免疫遺傳算法相結(jié)合，求解了考慮道路顛簸影響的冷鏈物流配送車輛路徑。

人工蜂群（Artificial bee colony，ABC）算法由Karaboga[8]提出。該算法魯棒性強、不需要梯度信息，比較容易編碼及實現(xiàn)，在求解優(yōu)化問題方面具有較好的效果[9-11]。在求解冷鏈物流車輛路徑時，用戶的需求往往呈現(xiàn)出一定的模糊隨機性，在一個可能的范圍內(nèi)浮動，因此可以采用三角模糊數(shù)表示。筆者針對冷鏈物流的特點，對離散蜂群算法進行了鄰域設(shè)計，求解了帶時間窗的用戶需求模糊條件下的冷鏈物流車輛路徑問題。

1帶時間窗的模糊需求冷鏈物流車輛路徑數(shù)據(jù)模型

1.1問題描述

冷鮮品車輛路徑問題可描述為：現(xiàn)有1個配送中心，K輛冷藏車，每輛車最大載重為Q；n個客戶，每個客戶的配送需求用三角模糊數(shù)描述為di（d1i，d2i，d3i），i=1，2，…，n。求解如何安排車輛行駛路線，能使總成本最低，客戶滿意度最高。

1.2模型建立

1.2.1參數(shù)說明。

為方便描述模型，對相關(guān)參數(shù)做以下說明：

Cij為客戶i的直線距離（i≠j）；

P為冷鮮品單位價格；

F為單位距離的行駛費用；

[ai，bi]為客戶i要求服務(wù)的時間窗；

tki為車輛k到達客戶點i的時間；

θ1為在ai之前到達客戶點等待的單位時間成本；

θ2為在bi之后到達客戶點單位時間的罰金成本；

φ1為運輸過程中的貨損比例。

φ2為開啟車門導(dǎo)致的貨損比例。

yik=1，客戶i由車輛k配送0，其他

xijk=1，車輛k從i訪問j0，其他

1.2.2構(gòu)建模型。

模型構(gòu)建要求在滿足客戶需求、時間窗、車輛載重等條件下，求出物流總成本最低時的車輛行駛路徑?？偝杀景ㄟ\輸成本、貨損成本和違反時間窗的懲罰成本。

（1）運輸成本。

為簡化計算，運輸成本由車輛行駛里程決定，記作cy，計算公式如下：

cy=Kk=1ni=0nj=0Fcijxijk（1）

ni=0d3iyik≤Q，k（2）

Kk=1yik=1，i（3）

ni=1xijk=yjk，j，k（4）

i，j∈Sxijk≤|S|-1，S∈{1，2，…，L}，k（5）

其中，公式（1）為總運輸成本；公式（2）保證客戶最大需求量不得超過車輛載重能力；公式（3）、（4）保證每一個客戶只能被1輛車訪問1次；公式（5）用于消除子回路。

（2）貨損成本。

與普通商品不同，冷鮮品在運輸過程中會有一定程度的貨損可能，貨損成本由此產(chǎn)生。貨損成本包括運輸時間累積產(chǎn)生的損耗及打開車門造成的損耗。貨損成本記為CS，計算公式如下：

cs=PKk=1ni=1yik（φ1cij+φ2di）（6）

（3）違反時間窗的懲罰成本。

違反時間窗的服務(wù)會造成懲罰成本。采用軟時間窗，來計算懲罰成本。當在指定配送時間[ai，bi]到達時，無懲罰成本；當配送時間早于ai，或者晚于bi，都要進行一定程度的懲罰。懲罰成本記為Cf，每個點的計算公式如下：

cfi=θ1i（ai-tki），tkiθ2i（tki-bi），tki>bi（7）

Cf=ni=1cfi（8）

（4）建立目標函數(shù)。根據(jù)上述不同成本的分析，建立目標函數(shù)如下：

MINC=Cy+Cs+Cf（9）

2人工蜂群算法及其改進

2.1基本人工蜂群算法

人工蜂群算法的設(shè)計思想模仿了蜜蜂的采蜜行為，蜜源代表優(yōu)化問題的可行解，通過蜂群的搜索行為進行優(yōu)化。蜂群中蜜蜂比例和分工情況如下：采蜜蜂占蜂群的50%，與蜜源數(shù)目相等，在其初始位置的鄰域范圍搜索新蜜源；觀察蜂也占蜂群的50%，根據(jù)采蜜蜂所在蜜源質(zhì)量決定是否跟隨，并在鄰域范圍搜索新蜜源；偵察蜂由采蜜蜂轉(zhuǎn)化而來，如果蜜源質(zhì)量經(jīng)過limit次開采后還沒有提高，則該蜜源被放棄，采蜜蜂轉(zhuǎn)為偵察蜂，在全局范圍內(nèi)搜索新的蜜源。

觀察蜂根據(jù)蜜源質(zhì)量進行選擇的概率公式為：

Pi=fiNi=1fi（10）

其中，fi為蜜源i的適應(yīng)度，N為蜜源的個數(shù)。觀察蜂根據(jù)蜜源適應(yīng)度以概率Pi選擇蜜源。采蜜蜂和觀察蜂搜索新蜜源的方式是相同的，在鄰域內(nèi)搜索并比較新舊蜜源適應(yīng)度，采用貪婪機制進行更新，即如果新位置的蜜源優(yōu)于原位置的蜜源，則替換之，否則保留原來位置的蜜源。已知原蜜源位置xij，產(chǎn)生新蜜源位置vij的公式為：

vij=xij+ij（xij-xkj）（11）

2.2鄰域生成策略

在求解復(fù)雜問題時，人工蜂群算法容易出現(xiàn)搜索能力不足、早熟收斂等缺點。針對人工蜂群的不足，在引領(lǐng)蜂、跟隨蜂的局部搜索階段采用3種鄰域，生成指定數(shù)量的新解序列，所指的位置均為隨機生成。鄰域策略描述如下：

①交換鄰域生成策略（SWAP）。隨機選擇原始解的2個位置的數(shù)據(jù)，并進行互換；

②前插鄰域生成策略（INSERT）。隨機選擇原始解的1個位置數(shù)據(jù)，將其取出并插入到隨機位置；

③倒轉(zhuǎn)鄰域生成策略（INVERSE）。在原始解隨機選擇一段數(shù)據(jù)，將其中的所有數(shù)據(jù)進行逆序排列。

3算法設(shè)計

3.1問題編碼及初始化

采用自然數(shù)的編碼方式，0表示配送中心，1～n表示客戶。每輛車從配送中心出發(fā)，最后返回配送中心，所以每輛車的運送路線以0作為開始和結(jié)束。采用PFIH方法構(gòu)造初始解。

3.2算法流程

①對蜂群進行初始化并設(shè)置相關(guān)算法參數(shù)，主要包括蜂群規(guī)模、最大迭代次數(shù)和鄰域列表長度等；

②引領(lǐng)蜂采用“2.2”部分設(shè)計的鄰域生成策略產(chǎn)生隨機產(chǎn)生指定數(shù)量的新解，采用貪婪算法更新，并將原始解替換為適應(yīng)度最高的解；

③采用公式（10）計算跟隨蜂選擇蜜源的概率，接著跟隨蜂采用與步驟②相同的方式替換原解；

④記錄每次迭代產(chǎn)生的局部最優(yōu)解；

⑤計算解的更新情況，如果達到limit次仍未改變，則丟棄之，并由偵察蜂在全局范圍內(nèi)搜索新解；

⑥將此次迭代局部最優(yōu)解與目前的全局最優(yōu)解進行比較，如果適應(yīng)度高則取代之，否則保留；

⑦判斷是否滿足終止條件，如果滿足則輸出最優(yōu)解，算法結(jié)束，否則轉(zhuǎn)步驟③。

4算例驗證及結(jié)果分析

為驗證文中算法的有效性，設(shè)計1個測試用例，有1個配送中心和2輛冷鏈車輛，客戶數(shù)為8，車輛最大載重為8。配送中心、客戶點之間的距離，各客戶點的時間窗和需求如表1～2所示，采用Matlab R2013a編程并進行測試。試驗參數(shù)設(shè)置如下：種群規(guī)模設(shè)置為80，最大迭代次數(shù)為60，鄰域列表長度為6，算法運行10次。

5結(jié)語

筆者分析了冷鮮品物流的車輛配送路徑問題的數(shù)據(jù)模型，提出了一種改進的離散人工蜂群算法進行求解。為避免基本人工蜂群求解優(yōu)化問題的不足，設(shè)計了新的鄰域生成策略進行局部搜索，通過實例驗證了該算法的有效性和穩(wěn)定性，對于求解用戶模糊需求下的冷鮮品冷鏈物流車輛路徑優(yōu)化問題具有一定的參考價值。

參考文獻

[1] 韓印，師攀.基于道路狀況的冷鏈物流配送路徑優(yōu)化[J].物流科技，2015，38（6）：90-93.

[2] 潘東靜.具有模糊需求的農(nóng)產(chǎn)品冷鏈物流車輛配送路徑優(yōu)化研究[J].安徽農(nóng)業(yè)科學(xué)，2015，43（5）：334-335，370.

[3] 曹倩，邵舉平，孫延安.基于改進遺傳算法的生鮮農(nóng)產(chǎn)品多目標配送路徑優(yōu)化[J].工業(yè)工程，2015，18（1）：71-76.

[4] 陳夢，曾陽，唐驛，等.食品冷鏈物流配送路徑優(yōu)化問題研究[J].物流工程與管理，2015，37（1）：145-147.

[5] 白燾，李鳴，嚴良濤.蜂群算法在冷鏈物流配送車路徑規(guī)劃中的應(yīng)用[J].湖北農(nóng)業(yè)科學(xué)，2016，55（22）：5958-5962.

[6] 王淑云，孫虹.隨機需求下冷鏈品多溫共配路徑優(yōu)化研究[J].工業(yè)工程與管理，2016，21（2）：49-58.

[7] 王咪，楊孔雨.基于2-Opt免疫遺傳算法的冷鏈配送路徑優(yōu)化問題研究[J].物流技術(shù)，2016，35（7）：72-76.

[8] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri：Eroiyes University，Engineering Faculty，Computer Engineering Department，2005.

[9] SINGH A.An artificial bee colony algorithm for the leafconstrained minimum spanning tree problem[J].Applied soft computing，2009，9（2）：625-631.

[10] PAN Q K，TASGETIREN M F，SUGANTHAN P N，et al.A discrete artificial bee colony algorithm for the lotstreaming flow shop scheduling problem[J].Information sciences，2010，181（12）：2455-2468.

[11] XU C F，DUAN H B.Artificial bee colony（ABC）optimized edge potential function（EPF）approach to target recognition for lowaltitude aircraft[J].Pattern recognition letters，2010，31（13）：1759-1772.