蜂群算法在冷鏈物流配送車路徑規劃中的應用

摘要：車輛路徑規劃問題是冷鏈物流配送環節的關鍵，而易腐農產品會隨運輸時間的推移而腐爛變質或者影響其使用價值。利用解蜂群算法采蜜行為的基本原理及其算法流程，根據配送中心與客戶的需求以及運輸過程存在各方面約束條件的情況下建立模型并初步考慮到農產品的腐敗成本。最終分析并設計了一種基于人工蜂群算法的冷鏈物流配送車輛路徑優化方法，并應用實例及軟件仿真對算法進行了驗證，且證明了該算法的有效性。

關鍵詞：冷鏈物流；蜂群算法；路徑優化；腐敗成本；有效性

中圖分類號：TP301.6 文獻標識碼：A 文章編號：0439-8114（2016）22-5958-04

DOI：10.14088/j.cnki.issn0439-8114.2016.22.057

Application of Colony Algorithm in Vehicle Routing Planing of Cold-chain Logistics

BAI Tao，LI Ming，YAN Liang-tao

（School of Mechanical Electrical Engineering， Nanchang University， Nanchang 330031， China）

Abstract：Vehicle routing planing is the key step of cold-chain logistics， however， perishable agricultural products will be bad and affect its use value with the transport time. Based on the basic principle of colony algorithm with honey behavior and algorithm of process， then the model was establish and preliminary given the cost of corruption based on distribution center with the needs of customers and various aspects of constraint condition in the process of transportation. Final analysis and design an algorithm based on artificial colony of cold-chain logistics distribution vehicle routing optimization method， then through software simulation of algorithm to wake the validation and prove its validity.

Key words： cold-chain logistics； colony algorithm； routing planing； cost of corruption； validity

隨著中國經濟的發展，生活水平不斷提高，為保證冷凍食品的質量，冷鏈物流快速發展。有效的配送卻成了冷鏈物流的關鍵環節，因為農產品受自然條件的影響較大，容易腐壞，所以要求配送車輛效率的提升，實現資源的優化配置，減少農產品的損失。本研究設計實現了一種基于人工蜂群算法的冷鏈物流配送車輛路徑優化算法，蜂群具有勞動分工和協作機制，蜜蜂按照勞動分工采用不同的搜索策略或模式，并且可以互相共同完成尋優工作，且全局尋優能力強[1]。基于采蜜行為的蜂群算法能利用蜜蜂之間尋優的正反饋機制，有效加快了全局尋優的過程，同時發現蜂群算法在搜索過程中能自組織進行角色變換，具有很強的自組織、自適應以及魯棒性強等特點。基于蜂群采蜜行為算法對冷鏈物流配送車輛路徑規劃實現了智能化，使物流配送服務的質量，提高了物流配送的合理性和高效性、提高了服務資源利用率、降低了物流服務成本，最終保證了冷凍食品的質量與安全。

1 人工蜂群算法

1.1 蜜蜂采蜜行為生物學機理

蜂群算法是一種群智能優化算法，是通過對自然界中蜜蜂采蜜的行為進行的模擬算法。蜜蜂能在苛刻和復雜的環境中進行高收益率的采蜜，并且能夠自發進行角色互換，隨著環境的改變而變換自己的采蜜方式最終快速地找到優質的蜜源。Karaboga等[2，3]通過對蜜蜂采食行為的研究給出了人工蜂算法模型，模型由3個基本要素組成：蜜源、雇傭蜂、非雇傭蜂。

蜜源：蜜蜂的搜索目標，離蜂巢的距離遠近、花蜜的豐富程度、獲取花粉的難易程度等由多方面因素評價其質量，蜜源的質量與收益度成正比。

雇傭蜂：也被稱為引領蜂，其數量與蜜源的數量相對應，自身還儲存蜜源的相關信息。回到蜂巢中時會通過搖擺舞的形式按一定的概率與其他蜜蜂分享自身攜帶食物源的信息。

非雇傭蜂：非雇傭蜂有兩種，分別是跟隨蜂與偵察蜂。主要目的是開采蜜源和發掘新的蜜源，跟隨蜂按一定的概率從引領蜂那獲取蜜源的信息。

剛開始，所有蜜蜂都可以看做是偵察蜂，然后根據以往的經驗決定其搜索方式。經過一系列搜索后，如果偵察蜂找到某個蜜源，偵察蜂就開始進行采集花蜜利用自身的儲存功能標記食物源的信息。同時，偵察蜂將成為雇傭蜂（引領蜂）。蜜蜂采完蜜后將蜂蜜放在蜂巢然后將有以下幾種選擇。

1）如果蜜源收益度低，放棄蜜源再次成為偵查蜂或者跟隨蜂。

2）如果蜜源收益度仍然很好，引領蜂通過跳搖擺舞招募更多的蜜蜂采集蜜源，接著繼續去蜜源采蜜。

3）如果蜜源收益度一般，繼續在之前偵查蜜源采蜜并且不進行招募活動。

1.2 ABC算法簡介

ABC算法是一個迭代尋優算法，初始時隨機生成N個蜜源（問題的可行解）{X1，X2，X3…XN}是一個D維向量，一個采蜜蜂對應一個蜜源。

采蜜階段，每只雇傭蜂在每一個蜜源的領域內生成一個新的蜜源，并且評估兩者的花蜜數量（適應度），保留適應度高的蜜源，蜜源的更新公式為：

vij=xij+rand（xij-xkj） （1）

其中，k∈{1，2，…N}，j∈{1，2，…D}；rand是0到1之間的一個隨機數，控制一個蜜源的領域生成范圍。

跟隨階段，當所有的雇傭蜂完成這個過程后，它們與跟隨蜂共享蜜源的信息。每個跟隨蜂按照一定的概率選擇一個蜜源。

引領蜂招募跟隨蜂概率為：

Pi=fi/■fi （2）

式中，fi是第i個解的適應度，適應度越高的蜜源被選擇的概率越大。

若食物源經過若干次搜索后，沒有得要最優解，那么認為這個解陷入僵局放棄此解，該食物源將被引領蜂放棄，自己的角色將轉化成偵察蜂。然后隨機產生一個新的解代替淘汰解，這樣算法能夠跳出局部最優解，加快算法的收斂速度。

xji=xjmin+rand（0，1）（xjmax-xjmin） （3）

其中，k∈{1，2，…N}，j∈{1，2，…D}，xmax、xmin為個體的最大最小值。

為了更好理解該算法，現將蜜蜂采蜜行為與算法的對應關系如表1所示。

2 蜂群算法在路徑優化上的應用

2.1 數學模型

隨著時間的推移，農產品容易腐爛變質，農產品冷鏈物流的配送，除了要滿足客戶對于貨物送達的基本要求，還應當盡量滿足客戶對于配送時間的要求，從而對農產品的新鮮度有一定的保障[4]。因此，本研究選取了更為接近實際情況的車輛路徑問題（Vehicle Routing Problem，VRP）進行研究。

VRP模型是物流配送優化中的關鍵問題[5]。冷鏈物流配送問題可以描述為，在約束條件下，設計從一個配送中心出發，到多個已知客戶位置的多條最優送貨路徑回路，即要設計多條總體配送成本（車輛管理費用+運輸成本+運輸中產品產生的腐敗成本）最小的路線且滿足：

1）每個城市或者客戶只被一輛車訪問一次[6]；

2）所有車輛從起點出發最終回到起點；

3）滿足一些約束條件。

通常的約束包括：每輛車的載重量限制、到達客戶的時間限制（具體表現在農產品的腐敗成本上與時間有關，耽擱時間越長農產品價值越低，成本越高），這里假定所有車輛都一樣且有相同的載重量。

其基本模型如圖1所示，實線代表載貨運輸，虛線代表空車行駛，圓圈代表各個客戶[7]。

記G=（V，E）為賦權圖，V={1，2，3……，n}為頂點集，代表所有的客戶位置及配送中心；E為邊集，代表各個頂點的距離為lij（lij>0，lii=0；i，j∈V），每一輛車的載重量為M，各個客戶需求量為mi（i∈V），并且定義變量如下：

yki1，客戶i的需求由車輛k完成0，其他 （4）

xijk1，車輛k從i點行駛到j點0，其他 （5）

約束條件為：

■yki=1，i∈V （6）

式6保證每一個客戶只被訪問一次

■xijk=ykj，i∈V，？坌k■xijk=yki，i∈V，？坌k■■xijk≤|S|-1，S？哿V （7）

其中，xijk，yki≤（0，1）；i，j∈V，？坌k，|S|為集合S中所含圖G的頂點個數。

式7保證車輛能夠回到起點形成回路，且路徑連接條數必小于等于頂點數減一。

腐敗成本P（t）的計算。由于不考慮農產品在配送中心的腐敗損失，以出發時完好的物品量Wi（0）為計算腐敗成本的標準量，由于腐敗速率恒定，有腐敗微分方程[8]：

■=-？茲Wi（t） （8）

其中，Wi（t）為運往客戶i的路途中t時刻完好的產品量，？茲為腐敗速率系數，不考慮其他因素，恒定不變。

假設ti為配送中心到達客戶i所需要的時間，a為運輸速度的倒數，li為配送中心到客戶i的距離，di為客戶i的需求量，則有：

ti=ali；Wi（t）=di （9）

將上式帶入微分方程得：

Wi（0）=dieti？茲 （10）

則產品運輸到客戶i后的腐敗量為

Wi（0）-Wi（t）=di（eti？茲-1） （11）

易腐農產品的單價為c，則產品運到客戶i的腐敗成本為

P（t）=c*di（eti？茲-1） （12）

則目標函數如下：MinU=A*（maxk）+P（t）+h*（■■■1ijxijk） （13）

A*（maxk）表示車輛的管理費用，A表示每一輛車的管理費用。

P（t）表示產品的腐敗成本，與時間有關系。

h*（■■■1ijxijk）表示運輸費用，h表示單位長度路程費用。

2.2 路徑優化算法設計與實現

首先對食物源（客戶）采取實數編碼，可以用自然數I∈{1，2，…N}表示客戶，0代表物流配送中心，路徑的表示方法則更為簡單，例如0-1-2-3-0，表示車輛從配送中心出發，經過客戶1、客戶2、客戶3，最終回到配送中心。然而有時候車輛較多無法區分時，則用負數表示物流車輛，k∈{-1，-2，…-M}，則路徑（-1）-1-2-3-（-2）-3-4-（-2），表示第一輛車從配送中心出發，經過客戶1、客戶2、客戶3，最終回到配送中心；第2輛車經過客戶3、客戶4回到配送中心，表示兩個車輛的回路。初始解的生成將車輛序號插入到客戶編號序列里面，生成初始解。主要步驟描述如下。

①對算法中需要的參數設定。算法中主要的參數：種群大小NP，雇傭蜂數En，跟隨蜂數On，偵察蜂數Sn，局部最大搜索次數Limit，迭代次數Cycle，解的D（維度），客戶數（N）、車輛數（K），其中，D=N+K[9]。

②初始化蜂群數量。隨機生成N個預行駛路線（即客戶車輛的編號序列），構成預行駛路線的方法為：隨機選擇一輛車，將其編號插入到序列的第一位，從這一位開始向后逐一判斷車輛的載重是否能夠滿足后面客戶的需求，直到不能滿足時再從剩下的車輛中隨機選擇一輛車，將其編號插入到該位置。

③根據車輛的載重量客戶的時間限制及一些約束條件，確定生成的解是否滿足條件，當生成的解不滿足約束時重新生成新的解，并根據設計的目標函數Min U對各解的適應度值進行計算，然后存儲這些信息。

④開始算法的迭代過程，重復執行步驟⑤～步驟⑧。

⑤遍歷所有的解，在解的鄰域內尋找新解，保留原解和新解中適應度值更高的解。

⑥根據所有解的適應度值來計算各個解被選擇的概率值。

⑦當達到局部最大次數時，解沒有被更新，則將該解丟棄，重新生成一個解來代替且記錄目前為止的最優解。

⑧判斷是否已經達到全局最大循環次數，到達則算法結束，否則轉到步驟⑦中記錄的解即為全局最優解。

算法流程圖如圖2所示。

3 實例求解與分析

一個配送中心，配送物流車總數為2，客戶數為8，車輛的載重為8 t。客戶與配送中心的距離及客戶與客戶之間的距離且各個客戶的需求量如表2所示。假設車輛的行駛速度一定，交通狀況良好，運輸時間與運輸路程當然也就成正比關系，腐敗成本與時間成正相關，即車輛行駛總路程與腐敗成本成正相關關系。參數設置種群規模為60，迭代次數為50（與文獻[10-12]的設置相同）。經過10次運算，得到的計算結果見表3。從表3中可以看出，10次運行得到的結果在第4次得到了最優解101.25 km，其對應配送路徑為0→4→1→6→0；0→7→2→8→5→3→0。結果表明，ABC算法有較好的優化能力，適合解決VRP問題，可以方便有效地求得問題的最優解或近似最優解[13-20]。

4 小結

利用蜂群算法，以物流成本為最終目標，對車輛路徑進行了優化，在冷鏈物流配送系統中，實現了資源的優化配置，農產品的保鮮度得到了保障，提高了經濟效益。通過仿真表明，用該算法解決車輛路徑問題是有效可行的。

參考文獻：

[1] 張超群，鄭建國，王 祥.蜂群算法研究綜述[J].計算機應用研究，2011，28（9）：3201-3204.

[2] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R]. Kayseri：Erciyes University，2005.

[3] KARABOGA D，BASTURK B.A powerful and efficient algorithm for numerical function optimization： Artificial bee colony（ABC） algorithm[J].Journal of Global Optimization，2007，39（3）：459-471.

[4] 李明澤.蜂群算法研究綜述.城市農產品冷鏈物流配送路徑優化研究[D].遼寧大連：大連海事大學，2013.

[5] 崔雪麗，馬 良，范炳全.車輛路徑問題（VRP）的螞蟻搜索算法[J].系統工程學報，2004，19（4）：418-422.

[6] 楊 進，馬 良.蜂群優化算法在車輛路徑問題中的應用[J].計算機工程與應用，2010，46（5）：214-216.

[7] 李 芳，羅清明，葉春明.JIT方式在冷鏈物流配送中的應用研究[J].工業技術經濟，2007，26（1）：99-101.

[8] 李 磊，張彥玲.易腐農產品配送中心選址問題[J].江南大學學報，2013，12（6）：732-738.

[9] 張英偉.基于人工蜂群算法的城市物流配送服務車輛調度問題研究[D].哈爾濱：哈爾濱工業大學，2014.

[10] 趙燕偉，吳 斌，蔣 麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計算機集成制造系統，2004，10（3）：303-306.

[11] 姜昌華，戴樹貴，胡幼華.求解車輛路徑問題的混合遺傳算法[J].計算機集成制造系統，2007，13（10）：2047-2052.

[12] 肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進微粒群優化算法[J].計算機集成制造系統，2005，11（4）：557-581.

[13] 陳阿慧，李艷娟，郭繼峰.人工蜂群算法綜述[J].智能計算機與應用，2014，4（6）：20-24.

[14] 楊 進，馬 良.蜂群優化算法在帶軟時間的車輛路徑問題中的應用[J].預測，2010，29：85-86.

[15] 王連穩，蔡延光.基于蜂群算法的隨機需求車輛路徑優化問題研究[J].科研發展，2013（6）：85-87.

[16] 王志剛，夏慧明.求解車輛路徑問題的人工蜂群算法[J].計算機工程與科學，2014，36（6）：1088-1093.

[17] 張麗萍，柴躍廷.車輛路徑問題的改進遺傳算法[J].計算機集成制造系統，2002，8（6）：451-454.

[18] 王曉博，李一軍.多車場多車型裝卸混合車輛路徑問題研究[J].控制與決策，2009，24（12）：1769-1774.

[19] 秦全德，程 適，李 麗，等.人工蜂群算法研究綜述[J].智能系統學報，2014，9（2）：377-385.

[20] 段風華.帶軟時間窗約束的開放式車輛路徑問題及其應用[D]. 長沙：中南大學，2009.