蔡浩原　潘郁

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

關(guān)鍵詞：鮮活農(nóng)產(chǎn)品；冷鏈物流；路徑優(yōu)化；人工蜂群算法

中圖分類號： F252文獻(xiàn)標(biāo)志碼： A

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

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

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

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

1鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化數(shù)學(xué)模型

1.1問題描述

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

1.2鮮活農(nóng)產(chǎn)品變質(zhì)函數(shù)

對于鮮活易腐食品變質(zhì)的函數(shù)，學(xué)者們很早便做了研究，結(jié)果表明，其函數(shù)形式過于復(fù)雜，不適合在實(shí)際應(yīng)用中使用。因此，一般采用形式相對簡單的指數(shù)函數(shù)作為鮮活食品的變質(zhì)函數(shù)。變質(zhì)往往與食品所在環(huán)境的溫度以及所經(jīng)歷的時間長短有關(guān)，變質(zhì)函數(shù)所要表現(xiàn)的就是兩者與食品質(zhì)量之間的關(guān)系。考慮到鮮活農(nóng)產(chǎn)品是通過冷鏈物流運(yùn)輸?shù)?，其溫度相對穩(wěn)定，因此構(gòu)建如下變質(zhì)函數(shù)：

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

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

1.3時間懲罰函數(shù)

為了更加貼合實(shí)際，在建立鮮活農(nóng)產(chǎn)品冷鏈物流配送模型時，將時間窗加入到模型中進(jìn)行考慮。時間窗分為軟時間窗和硬時間窗，本模型中采用硬時間窗，即在需求點(diǎn)期望時間內(nèi)送達(dá)，那么時間懲罰函數(shù)為0；超過期望時間區(qū)間，通過懲罰函數(shù)來增加成本。時間懲罰函數(shù)如下：

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

式中：Gj表示在需求點(diǎn)j的時間懲罰費(fèi)用；M表示時間懲罰的系數(shù)；[ETdj，LTdj]表示需求點(diǎn)j的期望送達(dá)時間區(qū)間；tj表示到達(dá)需求點(diǎn)j的實(shí)際時間。tj的公式如下：

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

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

1.4模型建立

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

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

模型將鮮活農(nóng)產(chǎn)品冷鏈物流配送的成本作為目標(biāo)函數(shù)，成本主要由3個部分組成，分別是配送的運(yùn)輸成本、時間懲罰費(fèi)用以及鮮活農(nóng)產(chǎn)品的損失價(jià)值，具體如下：

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

2人工蜂群算法（ABC）

2.1基本原理

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

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

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

2.2求解路徑優(yōu)化的人工蜂群算法

2.2.1構(gòu)造食物源編碼

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

2.2.2生成候選食物源

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

好地對冷鏈物流配送路徑進(jìn)行優(yōu)化，為現(xiàn)實(shí)中的決策提供有力的支持。

4結(jié)論

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

參考文獻(xiàn)：

[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]陳志新，陳方玉，胡貴彥，等. 基于混合粒子群算法的配送車輛復(fù)雜路徑優(yōu)化[J]. 物流技術(shù)，2014，33（7）：176-178.

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

[8]向敏，袁嘉彬，于潔. 電子商務(wù)環(huán)境下鮮活農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究[J]. 科技管理研究，2015（18）：166-171.

[9]朱金鳳，萇道方，林丹萍. 基于成本約束的冷鏈物流配送網(wǎng)絡(luò)規(guī)劃[J]. 江蘇農(nóng)業(yè)科學(xué)，2015，43（11）：572-575.

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