蜂群算法在冷鏈物流配送車路徑規(guī)劃中的應(yīng)用

白燾++李鳴++嚴(yán)良濤

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

關(guān)鍵詞：冷鏈物流；蜂群算法；路徑優(yōu)化；腐敗成本；有效性

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：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

隨著中國經(jīng)濟的發(fā)展，生活水平不斷提高，為保證冷凍食品的質(zhì)量，冷鏈物流快速發(fā)展。有效的配送卻成了冷鏈物流的關(guān)鍵環(huán)節(jié)，因為農(nóng)產(chǎn)品受自然條件的影響較大，容易腐壞，所以要求配送車輛效率的提升，實現(xiàn)資源的優(yōu)化配置，減少農(nóng)產(chǎn)品的損失。本研究設(shè)計實現(xiàn)了一種基于人工蜂群算法的冷鏈物流配送車輛路徑優(yōu)化算法，蜂群具有勞動分工和協(xié)作機制，蜜蜂按照勞動分工采用不同的搜索策略或模式，并且可以互相共同完成尋優(yōu)工作，且全局尋優(yōu)能力強[1]?；诓擅坌袨榈姆淙核惴芾妹鄯渲g尋優(yōu)的正反饋機制，有效加快了全局尋優(yōu)的過程，同時發(fā)現(xiàn)蜂群算法在搜索過程中能自組織進(jìn)行角色變換，具有很強的自組織、自適應(yīng)以及魯棒性強等特點?；诜淙翰擅坌袨樗惴▽滏溛锪髋渌蛙囕v路徑規(guī)劃實現(xiàn)了智能化，使物流配送服務(wù)的質(zhì)量，提高了物流配送的合理性和高效性、提高了服務(wù)資源利用率、降低了物流服務(wù)成本，最終保證了冷凍食品的質(zhì)量與安全。

1 人工蜂群算法

1.1 蜜蜂采蜜行為生物學(xué)機理

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

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

雇傭蜂：也被稱為引領(lǐng)蜂，其數(shù)量與蜜源的數(shù)量相對應(yīng)，自身還儲存蜜源的相關(guān)信息?；氐椒涑仓袝r會通過搖擺舞的形式按一定的概率與其他蜜蜂分享自身攜帶食物源的信息。

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

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

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

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

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

1.2 ABC算法簡介

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

采蜜階段，每只雇傭蜂在每一個蜜源的領(lǐng)域內(nèi)生成一個新的蜜源，并且評估兩者的花蜜數(shù)量（適應(yīng)度），保留適應(yīng)度高的蜜源，蜜源的更新公式為：

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

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

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

引領(lǐng)蜂招募跟隨蜂概率為：

Pi=fi/■fi （2）

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

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

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

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

為了更好理解該算法，現(xiàn)將蜜蜂采蜜行為與算法的對應(yīng)關(guān)系如表1所示。

2 蜂群算法在路徑優(yōu)化上的應(yīng)用

2.1 數(shù)學(xué)模型

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

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

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

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

3）滿足一些約束條件。

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

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

記G=（V，E）為賦權(quán)圖，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(luò)點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的頂點個數(shù)。

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

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

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

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

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

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

將上式帶入微分方程得：

Wi（0）=dieti？茲 （10）

則產(chǎn)品運輸?shù)娇蛻鬷后的腐敗量為

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

易腐農(nóng)產(chǎn)品的單價為c，則產(chǎn)品運到客戶i的腐敗成本為

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

則目標(biāo)函數(shù)如下：MinU=A*（maxk）+P（t）+h*（■■■1ijxijk） （13）

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

P（t）表示產(chǎn)品的腐敗成本，與時間有關(guān)系。

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

2.2 路徑優(yōu)化算法設(shè)計與實現(xiàn)

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

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

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

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

④開始算法的迭代過程，重復(fù)執(zhí)行步驟⑤～步驟⑧。

⑤遍歷所有的解，在解的鄰域內(nèi)尋找新解，保留原解和新解中適應(yīng)度值更高的解。

⑥根據(jù)所有解的適應(yīng)度值來計算各個解被選擇的概率值。

⑦當(dāng)達(dá)到局部最大次數(shù)時，解沒有被更新，則將該解丟棄，重新生成一個解來代替且記錄目前為止的最優(yōu)解。

⑧判斷是否已經(jīng)達(dá)到全局最大循環(huán)次數(shù)，到達(dá)則算法結(jié)束，否則轉(zhuǎn)到步驟⑦中記錄的解即為全局最優(yōu)解。

算法流程圖如圖2所示。

3 實例求解與分析

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

4 小結(jié)

利用蜂群算法，以物流成本為最終目標(biāo)，對車輛路徑進(jìn)行了優(yōu)化，在冷鏈物流配送系統(tǒng)中，實現(xiàn)了資源的優(yōu)化配置，農(nóng)產(chǎn)品的保鮮度得到了保障，提高了經(jīng)濟效益。通過仿真表明，用該算法解決車輛路徑問題是有效可行的。

參考文獻(xiàn)：

[1] 張超群，鄭建國，王 祥.蜂群算法研究綜述[J].計算機應(yīng)用研究，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] 李明澤.蜂群算法研究綜述.城市農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[D].遼寧大連：大連海事大學(xué)，2013.

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

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

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

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

[9] 張英偉.基于人工蜂群算法的城市物流配送服務(wù)車輛調(diào)度問題研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2014.

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

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

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

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

[14] 楊 進(jìn)，馬 良.蜂群優(yōu)化算法在帶軟時間的車輛路徑問題中的應(yīng)用[J].預(yù)測，2010，29：85-86.

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

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

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

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

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

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