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

姜婷

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

關鍵詞改進蜂群算法；模糊需求；鄰域生成策略；冷鏈物流車輛路徑優化

中圖分類號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

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

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

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

1.1問題描述

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

1.2模型建立

1.2.1參數說明。

為方便描述模型，對相關參數做以下說明：

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

P為冷鮮品單位價格；

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

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

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

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

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

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

φ2為開啟車門導致的貨損比例。

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

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

1.2.2構建模型。

模型構建要求在滿足客戶需求、時間窗、車輛載重等條件下，求出物流總成本最低時的車輛行駛路徑。總成本包括運輸成本、貨損成本和違反時間窗的懲罰成本。

（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）貨損成本。

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

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

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

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

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

Cf=ni=1cfi（8）

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

MINC=Cy+Cs+Cf（9）

2人工蜂群算法及其改進

2.1基本人工蜂群算法

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

觀察蜂根據蜜源質量進行選擇的概率公式為：

Pi=fiNi=1fi（10）

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

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

2.2鄰域生成策略

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

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

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

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

3算法設計

3.1問題編碼及初始化

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

3.2算法流程

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

②引領蜂采用“2.2”部分設計的鄰域生成策略產生隨機產生指定數量的新解，采用貪婪算法更新，并將原始解替換為適應度最高的解；

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

④記錄每次迭代產生的局部最優解；

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

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

⑦判斷是否滿足終止條件，如果滿足則輸出最優解，算法結束，否則轉步驟③。

4算例驗證及結果分析

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

5結語

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

參考文獻

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

[2] 潘東靜.具有模糊需求的農產品冷鏈物流車輛配送路徑優化研究[J].安徽農業科學，2015，43（5）：334-335，370.

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

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

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

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

[7] 王咪，楊孔雨.基于2-Opt免疫遺傳算法的冷鏈配送路徑優化問題研究[J].物流技術，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.