基于人工蜂群算法的鮮活農產品冷鏈物流配送路徑優化

蔡浩原　潘郁

摘要：鮮活農產品易變質的特性決定了其配送過程的困難性，針對這一難題，擬構建鮮活農產品的變質函數和配送時間的懲罰函數，并依此建立帶有時間窗的鮮活農產品冷鏈物流路徑優化模型。通過人工蜂群算法（ABC）對模型進行求解，以自然數編碼的方式生成食物源，并討論食物源的更新公式和適應度函數，研究具體的求解步驟和判斷標準。利用數值算例驗證了所建模型的合理性，結果表明，人工蜂群算法對此類問題具有有效性和可行性。

關鍵詞：鮮活農產品；冷鏈物流；路徑優化；人工蜂群算法

中圖分類號： F252文獻標志碼： A

文章編號：1002-1302（2017）15-0318-04

隨著科技的發展和收入的增加，人們對生活質量提出了更高的要求。鮮活農產品與人們的生活息息相關，人們對它的需求也隨著生活水平的提高呈現多樣化和個性化的發展趨勢。鮮活農產品主要包括新鮮的蔬菜、水果、水產品、禽類和肉類等5類產品。雖然我國是一個農業大國，但是物流配送體系的發展卻跟不上需求，且已經成為農產品市場發展的阻礙。目前，我國農產品物流體系不成熟、物流配送設施不完善以及物流人才缺乏等一系列的缺陷都是亟須加強和改善的地方，否則人們的需求便不能夠得到滿足。對于鮮活農產品這一類特殊的產品，因它們具有易腐變質的特性，需要冷鏈物流進行配送來保證其新鮮度。冷鏈物流指新鮮冷凍類食品從生產到被消費前每個流通環節都必須在一定低溫環境下進行保存，從而保證食品新鮮度或降低食品變質和損耗程度。鮮活農產品的嚴格時間限制、高儲藏成本和高服務質量等要求，給冷鏈物流商提出了很高的配送要求。因此，如何科學地規劃配送路線、合理制定配送方案，以保證鮮活農產品的配送效率、食品的新鮮程度和低損耗率，提高服務質量水平，對于冷鏈物流商非常重要，也是鮮活農產品發展道路上亟須解決的難題。

車輛路徑問題（vehicle routing problem，簡稱VRP）是指物流配送中心向一定數量的對于貨物需求不同的需求點供貨，在滿足需求點配送要求的基礎上，進行合理的路線規劃，最終達到運輸路程最短、運輸成本最低等目的。由于對該問題的研究具有很強的現實意義，因此一直是國內外學者研究的熱點。VRP的概念最早由Dantzig等提出[1]；考慮到現實中對于車輛路徑問題總是有一定配送時間要求，所以Solomon等首先將時間約束條件加入到車輛路徑問題的研究中[2]。啟發式算法對于解決車輛路徑問題具有很強的優越性，隨著多種算法的產生，對啟發式算法的研究也逐步豐富起來。Brito等將時間窗和模糊約束加入到近距離開放式的車輛路徑問題中，并通過混合蟻群算法進行了求解[3]；de Armas等考慮了現實中動態豐富的多目標的車輛路徑問題，使用了1種變領域搜索策略的啟發式算法解決該問題[4]；Küüko[KG-*5]g[DD（-1*2][HT6]ˇ[DD）]lu等利用了基于禁忌搜索和模擬退火算法的混合算法，解決帶有回程和時間窗的車輛路徑問題[5]；陳志新等使用混合粒子群算法來解決物流配送路徑優化問題[6]；鄔開俊等改進了差分進化算法，結合貪心算法來解決具有非確定性多項式（non-deterministic polynomial，簡稱NP）難的VRP[7]；隨著科技環境的變化，對于車輛路徑研究的背景也在隨之轉變，向敏等研究了在電子商務環境下鮮活農產品物流配送路徑的優化問題[8]。

雖然國內外學者對于車輛路徑問題的研究很多，但是將車輛路徑和冷鏈物流結合進行研究的卻不多，將鮮活農產品作為配送物品的研究就更少。本研究考慮了鮮活農產品運輸過程的損耗，加入時間窗的約束，并依此建立合理的鮮活農產品冷鏈物流配送模型，目的是使鮮活農產品冷鏈物流的配送成本最小化，力求使所建立的模型符合實際情形，從而為實際鮮活農產品的配送路線選擇提供有力的參考。

1鮮活農產品冷鏈物流配送路徑優化數學模型

1.1問題描述

鮮活農產品物流配送模型是由1個鮮活農產品配送中心向多個其覆蓋范圍內的配送點使用低溫配送車進行貨物配送的模型。假定配送中心的貨量充足，每個需求點的需求量、位置以及時間窗約束都是已知的；配送中心配送車輛數量固定，型號相同，并且每個配送車輛的容量確定。為對建立的模型進行簡化，需要考慮以下幾個約束條件：配送車所載貨物的質量或體積不得超過核定容量或載質量；貨物在時間窗之外的時間送達，會受到對應時間懲罰函數的懲罰；配送車輛以固定的速度進行貨物配送；每個需求點的貨物需求只能由1輛車單次完成；路徑優化的目標是使得配送成本最小化。

1.2鮮活農產品變質函數

對于鮮活易腐食品變質的函數，學者們很早便做了研究，結果表明，其函數形式過于復雜，不適合在實際應用中使用。因此，一般采用形式相對簡單的指數函數作為鮮活食品的變質函數。變質往往與食品所在環境的溫度以及所經歷的時間長短有關，變質函數所要表現的就是兩者與食品質量之間的關系。考慮到鮮活農產品是通過冷鏈物流運輸的，其溫度相對穩定，因此構建如下變質函數：

[JZ（]Q（t）=Qo·K·e-βt。[JZ）][JY]（1）

式中：Qo為鮮活農產品的初始質量；t為鮮活農產品運輸所需要的時間；K為鮮活農產品隨溫度而變質的速度常數，本研究假定進行冷鏈物流配送是恒溫環境，定為常數項1；β為鮮活農產品對于時間的敏感系數，若農產品對時間較為敏感，β的取值相對較小，反之β的取值較大。

1.3時間懲罰函數

為了更加貼合實際，在建立鮮活農產品冷鏈物流配送模型時，將時間窗加入到模型中進行考慮。時間窗分為軟時間窗和硬時間窗，本模型中采用硬時間窗，即在需求點期望時間內送達，那么時間懲罰函數為0；超過期望時間區間，通過懲罰函數來增加成本。時間懲罰函數如下：

[JZ（]Gj=[JB（{][HL（2]M（ETdj-tj）（0

式中：Gj表示在需求點j的時間懲罰費用；M表示時間懲罰的系數；[ETdj，LTdj]表示需求點j的期望送達時間區間；tj表示到達需求點j的實際時間。tj的公式如下：

[JZ]tj=∑[DD（]ni=0[DD）]∑[DD（]mk=1[DD）]xijk（ti+tij+si）。

式中：k表示配送中心車輛的號碼；xijk表示車輛號為k的配送車是否能夠從需求點i到需求點j；tij表示從需求點i到需求點j的時間；si表示在需求點i卸貨的時間。

1.4模型建立

在鮮活農產品變質函數和時間懲罰函數的基礎上，建立鮮活農產品冷鏈物流配送模型，設G=（V，E）表示無向連通圖，其中V={vi|i=1，…，N}表示圖的頂點集，v0表示起點，每個頂點vi表示1個需求點，E={（vi，vj）vi，vj∈V，且vi≠vj}為邊集，每條邊（vi，vj）代表2個頂點間有直通道路。對模型中涉及到的變量及含義作如下說明：

m為配送中心所擁有型號相同的配送車輛的數量；n為在城市中需求點的數量，配送中心的編號為0，需求點的編號為1，2，3，…，n；Z為整個配送過程的總成本；dij為需求點i和需求點j之間的距離，i，j=0，1，2，…，n；C0為單位路程運輸成本；Gi為在需求點i的時間懲罰費用；gi為需求點i的需求數量；Q為單位車輛的載貨量；Qi為車輛k在時間tik上滿足需求點i需要從配送中心裝載的貨量；p為單位數量鮮活農產品的損失價值；yik為車輛k是否到達需求點i。Qi=gi/（K·e-βtik）。

模型將鮮活農產品冷鏈物流配送的成本作為目標函數，成本主要由3個部分組成，分別是配送的運輸成本、時間懲罰費用以及鮮活農產品的損失價值，具體如下：

式（4）表示需求點i是否可以到達需求點j；式（5）表示車輛k是否配送到需求點i；式（6）表示每輛車的配送量不能超過其最大裝載量；式（7）表示每個需求點都有1輛車進行配送；式（8）和式（9）表示到達以及離開某個需求點的車輛有且只有1輛。

2人工蜂群算法（ABC）

2.1基本原理

人工蜂群算法是Karaboga在2005年提出的一種新型智能優化算法。在人工蜂群算法中，通過引領蜂、跟隨蜂、偵查蜂3種角色的蜜蜂配合以及角色的轉換來獲得最優的食物源。而食物源的位置對應著優化問題的可能解，蜂群在食物源的收益度代表所優化問題的適應度。

算法開始，會隨機產生有N個解的初始種群，并且每個解Xi（i=1，2，…，N）都是1個D維的向量。隨后，引領蜂記住最優解，在食物源的鄰域進行搜索，初始化后，3種蜜蜂循環搜索，搜索公式如下：

分別為第j維分量的最大值、最小值。

2.2求解路徑優化的人工蜂群算法

2.2.1構造食物源編碼

經典的人工蜂群算法，對于食物源的編碼采用的是實數編碼方式，這在鮮活農產品配送路徑優化問題中顯然是不可行的，配送中心進行配送的需求點是分散的，因此需要對編碼方式重新考慮。本研究對需求點采用自然數的編碼方式，則1條可行的食物源可以表示成（0，r11，r12，…，r1n；0，r21，r22，…，r2u；0，…；0，rm1，rm2，…，rmv）。此食物源表示第1輛車從配送中心出發，到達需求點r11，r12，…，r1n后返回配送中心；第2輛車從配送中心出發，到達需求點r21，r22，…，r2u后返回配送中心；……；第m輛車從配送中心出發，到達需求點rm1，rm2，…，rmv后返回配送中心。如有3輛車和9個需求點，食物源x=023601789045，表示第1輛車從配送中心出發到達需求點2、3、6后返回配送中心，第2輛車從配送中心出發到達需求點1、7、8、9后返回配送中心，第3輛車從配送中心出發到達需求點4、5后返回配送中心。

2.2.2生成候選食物源

由于在人工蜂群中采用了新的食物源編碼方式，因此對候選食物源位置的更新也不能采用式（10）的方式。本研究通過交換鄰域點的方法，隨機地將食物源中的2個鄰域點交換位置來得到候選食物源。以9個需求點和3輛車進行說明，圖1表示交換前和交換后的食物源，可見通過交換第3位和第6位的點，可以得到候選食物源。交換前后食物源的變動不大，因此可以保持變換前食物源的眾多優良特性；與此同時，隨機的位置交換增加了食物源選擇的多樣性，避免陷入局部最優而得不到全局最優解。

好地對冷鏈物流配送路徑進行優化，為現實中的決策提供有力的支持。

4結論

鮮活農產品的易腐特性，使得通過冷鏈物流進行運輸時的路徑選擇變得尤為重要[9-10] 。科學的路線規劃，不僅能夠保證農產品的新鮮度，也能夠在滿足需求點時間要求的基礎上降低運輸成本。本研究對鮮活農產品冷鏈物流配送問題等眾多條件進行了抽象定義，建立數學模型，并根據鮮活農產品易腐的特點，將變質函數加入模型；同時引入了時間窗，讓所研究的模型更加貼合實際且更加具有研究意義；將人工蜂群算法具體到鮮活農產品冷鏈物流配送模型上來，對建立的模型進行求解，并通過仿真試驗證明了人工蜂群算法對鮮活農產品冷鏈物流路徑優化模型具有有效性和可行性，表明人工蜂群算法對于解決此類問題具有很強的現實意義。

參考文獻：

[1]Dantzig G B，Ramser J H. The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[2]Solomon M，Desrosiers J. Time window constrained routing and scheduling problems[J]. Transportation Science，1988，22（1）：1-13.

[3]Brito J，Martínez F J，Moreno J A，et al. An ACO hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints[J]. Applied Soft Computing，2015，32：154-163.

[4]de Armas J，Melián-Batista B. Variable neighborhood search for a dynamic rich vehicle routing problem with time windows[J]. Computers and Industrial Engineering，2015，85：120-131.

[5]Küüko[KG-*5]g[DD（-1*2][HT6]ˇ[DD）]lu I，ztürk N. An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows[J]. Computers and Industrial Engineering，2015，86：60-68.

[6]陳志新，陳方玉，胡貴彥，等. 基于混合粒子群算法的配送車輛復雜路徑優化[J]. 物流技術，2014，33（7）：176-178.

[7]鄔開俊，王鐵君. 基于改進差分進化的車輛路徑優化算法[J]. 計算機工程與應用，2013，49（13）：17-20.

[8]向敏，袁嘉彬，于潔. 電子商務環境下鮮活農產品物流配送路徑優化研究[J]. 科技管理研究，2015（18）：166-171.

[9]朱金鳳，萇道方，林丹萍. 基于成本約束的冷鏈物流配送網絡規劃[J]. 江蘇農業科學，2015，43（11）：572-575.

[10]李康，鄭建國，伍大清. 生鮮農產品冷鏈物流配送干擾管理研究的思考[J]. 江蘇農業科學，2015，43（11）：588-591.endprint