基于粒子群算法的農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究

楊 瑋， 李國棟, 張 倩

(陜西科技大學 機電工程學院， 陜西 西安 710021)

0 引言

冷鏈物流是指在冷藏環(huán)境下保證食品質(zhì)量，減少食品損耗，以冷凍工藝學為基礎(chǔ)、以制冷技術(shù)為手段，進行冷藏類食品的物流過程.物流過程包括采摘、分級預冷、包裝加工、配送、批發(fā)零售.冷鏈物流是低溫食品和超低溫水產(chǎn)品供應鏈中的一個重要組成部分，將預冷技術(shù)、物流信息技術(shù)融合，把冷鏈物流配送、倉儲理貨、分裝與加工和車輛調(diào)度等物流各功能環(huán)節(jié)，按照客戶物流系統(tǒng)需求，實現(xiàn)客戶冷鏈物流服務資源信息量的最大化[1，2].

目前，國內(nèi)外關(guān)于生鮮農(nóng)產(chǎn)品物流的研究較少，主要集中于以下三方面內(nèi)容：一方面是從宏觀的角度對國內(nèi)冷鏈物流現(xiàn)狀進行分析并提出發(fā)展策略；第二方面是對冷鏈物流配套設(shè)施設(shè)備提出更高水平的要求；第三方面是對生鮮農(nóng)產(chǎn)品的安全監(jiān)控及質(zhì)量評估.

在國內(nèi)，黃利偉分析了我國農(nóng)產(chǎn)品冷鏈物流的現(xiàn)狀和存在的主要問題，提出制約我國農(nóng)產(chǎn)品冷鏈物流發(fā)展的主要因素，總結(jié)出適合我國農(nóng)產(chǎn)品冷鏈物流發(fā)展的對策[3].王嵐介紹了食品冷鏈的概念，研究了中國食品冷鏈發(fā)展的問題，并深入分析了問題的原因[4].蘇秀謹從物流規(guī)劃的主要組成部分，即物流服務水平、運輸系統(tǒng)、倉儲與倉庫選址、庫存與供應，分別具體論述在規(guī)劃冷鏈物流時的方法和獨特之處[5].胡軍珠分析了北京某蔬菜加工企業(yè)的冷鏈運輸流程現(xiàn)狀和問題，借鑒北京奧運蔬菜冷鏈運輸流程，采用六西格瑪方法的DMAIC模型優(yōu)化其冷鏈運輸流程，并提出相應對策[6].在國外，Rohit Joshi提出了一個基于Delphi-AHP-TOPSIS的冷鏈性能評價的基準框架，該框架可以協(xié)助經(jīng)理了解目前冷鏈的優(yōu)點和缺點，從當前公司的運作條件和策略方面改善冷鏈的缺點，該框架也便于決策者更好理解冷鏈性能決策因素的復雜關(guān)系[7].R. Montanari通過比較歐拉法和拉格朗日法, 提出了一個確定最優(yōu)冷鏈管理系統(tǒng)的模型，該模型可以找出最適當?shù)墓芾斫鉀Q方案，以達到物流成本最小化的目標[8].

從上述資料看出，很多專家學者從不同的角度對目前生鮮農(nóng)產(chǎn)品物流存在的問題進行了研究，但這些理論研究中，大部分只是從宏觀方面提出冷鏈物流優(yōu)化策略，且一些規(guī)劃方法即理論研究成果的可操作性不強，涉及計算的規(guī)劃方法較少，結(jié)果也往往不盡如人意.

本文選用了算法簡單、易實現(xiàn)，執(zhí)行速度快的粒子群算法解決農(nóng)產(chǎn)品冷鏈物流配送路線優(yōu)化問題，在迭代過程中對部分粒子重新初始化，以保證粒子的多樣性，避免結(jié)果陷入局部最優(yōu).通過實例驗證了該算法在解決線路優(yōu)化問題時具有時間短、算法收斂快、迭代次數(shù)少的優(yōu)越性.

1 我國農(nóng)產(chǎn)品冷鏈物流存在的問題

與發(fā)達國家相比，我國農(nóng)產(chǎn)品冷鏈物流整體水平偏低，農(nóng)產(chǎn)量流通過程中損耗較高，物流成本居高不下，尤其是在發(fā)展相對滯后的西部地區(qū)，農(nóng)產(chǎn)品物流基礎(chǔ)設(shè)施相對落后，流通效率低下，倉儲、交通運輸條件落后，缺乏先進的信息網(wǎng)絡(luò)平臺，致使農(nóng)產(chǎn)品在流通過程損耗嚴重[9].我國冷鏈物流技術(shù)落后，導致鮮活農(nóng)產(chǎn)品在運輸過程中出現(xiàn)腐變、串味等問題，無法保證鮮活農(nóng)產(chǎn)品在運輸中的“安全”和“綠色”問題.同時，我國缺乏冷鏈物流的專業(yè)人才，制約了我國冷鏈物流快速發(fā)展[10].

陜西是個農(nóng)業(yè)大省，農(nóng)產(chǎn)品占有重要地位，冷鏈物流的重要性就顯示出來.陜西省農(nóng)產(chǎn)品冷鏈物流配送也受到人們的關(guān)注.陜西省農(nóng)產(chǎn)品大多是才用普通卡車運輸，由于農(nóng)產(chǎn)品的冷藏運輸效率低，在流通過程中損耗高，整個物流費用占到易腐保鮮食品成本的70 % .所以如何高效率合理的配送成為我們研究的重點.高效率合理的配送是冷鏈物流系統(tǒng)順利運行的保證，合理安排配送線路，對配送速度、成本、效益有著重大影響.正確合理地安排車輛的配送線路，可以節(jié)約運輸時間，增加車輛利用率，從而降低運輸成本，提高企業(yè)經(jīng)濟效益與客戶服務水平，使企業(yè)達到科學化的物流管理, 提高企業(yè)的競爭力.

2 冷鏈物流配送路徑優(yōu)化模型

物流配送路徑優(yōu)化問題可以描述為：配送中心有多輛汽車，每輛汽車從配送中心出發(fā)，給多個需求點送貨，已知需求點的位置和需求量，每輛汽車的載重量，以汽車行駛總路徑最短為優(yōu)化目標，優(yōu)化汽車的路線.

設(shè)配送中心有載重量為Qk(k=1,2,…,k)的K輛汽車向L個需求點送貨，已知需求點的需求量qi(i=1,2,…,L)和運距dij，限制一輛車一次配送的距離不超過Dk，d0j(i,j=1,2,…,L)表示配送中心到需求點的距離，再設(shè)nk為第k輛汽車配送的客戶數(shù)(nk=0表示未使用第k輛汽車)，用集合Rk表示第k條路徑，令rk0表示配送中心，rki表示需求點rki在路徑k中的順序為i，則可建立如下物流配送路徑優(yōu)化問題的數(shù)學模型：

(1)

s.t.

(2)

(3)

0≤nk≤L

(4)

(5)

Rk={rki|rki∈{1,2,…,L},i=1,2,…,nk}

(6)

Rk1∩Rk2=φ?k1≠k2

(7)

(8)

上述模型中：

(1)式為該模型的目標函數(shù)，以配送線路最短為優(yōu)化目標；(2)式為每輛車的能力約束；(3)式為限制車輛配送的最大行駛距離；(4)式為限制每條路徑上的需求點數(shù)；(5)式表明每個需求點都被服務；(6)式表示路徑的需求點的組成；(7)式限制每個需求點僅被服務一次；(8)式表示當nk≥1時，取sign(nk)=1，當nk<1時，取sign(nk)=0.

3 粒子群優(yōu)化算法

本文采用粒子群優(yōu)化算法(Particle Swarm Optimizer，PSO)進行尋優(yōu).粒子群優(yōu)化算法最早是由Kennedy和Eberhart于1995年提出的[7,8]，其核心思想是對生物社會性行為的模擬，這種算法的優(yōu)點是實現(xiàn)容易、精度高、收斂快，并且在解決實際問題中具有優(yōu)越性.

3.1 粒子群算法原理

粒子群算法是一種基于群體智能的隨機尋優(yōu)算法，它模擬鳥群的覓食行為，將問題的搜索空間類比于鳥類的飛行空間，將每只鳥抽象為一個無質(zhì)量無體積的粒子，用以表征問題的一個候選解，優(yōu)化所需用尋找的最優(yōu)解則等同于要尋找的食物.PSO算法為每個粒子制定了類似鳥類運動的行為規(guī)則，使得整個粒子群的運動與鳥類覓食的特性類似，進而用來求解復雜的優(yōu)化問題.該算法把每個優(yōu)化問題的解都看成是搜索空間中的一只鳥.所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitness value)以及決定他們飛行方向和距離的速度，粒子們追隨當前的最優(yōu)粒子在解空間中搜索.PSO算法尋優(yōu)搜索的過程，每只鳥(粒子，Particle)在自己最優(yōu)位置的基礎(chǔ)上通過追蹤有限個處于當前最優(yōu)位置的鄰居，一步步地向食物目標位置靠近.

在粒子群算法中，由n個粒子組成的種群X=(X1,X2,…,Xn)在D維空間中以一定的速度Vi=(Vi1,Vi2,…,ViD)T飛行，粒子飛過的每個位置Xi=(xi1,xi2,…,xiD)T都對于一個解，粒子飛行的過程就是搜索的過程.每個粒子在飛行時，根據(jù)自己飛過的歷史最優(yōu)點Pi=(Pi1,Pi2,…,PiD)T和群體鄰域內(nèi)所有粒子飛過的歷史最優(yōu)點Pg=(Pg1,Pg2,…,PgD)T更新自己的位置和速度.常用的速度和位置更新公式如下：

(9)

(10)

其中，c1，c2為加速因子，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長,c2調(diào)節(jié)粒子向全局最好位置飛行的步長;r1，r2為[0，1]之間的隨機數(shù).w為慣性系數(shù)，一般取(0,1)之間的隨機數(shù)；每一維的速度都被限制在最大速度vmax(vmax>0)內(nèi)，當vk=-vmax,vk>vmax時，vk=vmax;當vk<-vmax時，vk=-vmax.

3.2 算法流程

粒子群優(yōu)化算法流程如下：

Step1:隨機初始化粒子位置和速度；

Step2:計算每個粒子的適應度值；

Step3:根據(jù)公式(11)、(12)更新當前個體最優(yōu)和群體最優(yōu)；

(11)

(12)

Step4:根據(jù)公式(9)、(10)更新各粒子位置和速度；

Step5:如達到終止條件，算法結(jié)束；否則，轉(zhuǎn)向Step2.

粒子群優(yōu)化算法的流程圖如圖1所示.

圖1 粒子群優(yōu)化算法流程圖

4 實例分析

4.1 問題描述

本文以陜西某果業(yè)有限公司為例對冷鏈物流配送路徑進行優(yōu)化研究.該公司主要是給超市和農(nóng)產(chǎn)品批發(fā)市場供應蘋果.該公司有4輛車進行配送，每輛車限載量皆為q=4.0 t，用這4輛車來完成西安市內(nèi)17家超市的配送任務.配送中心與各需求點之間、各需求點相互之間的距離及各需求點的需求量見表1.

4.2 冷鏈物流配送路徑優(yōu)化問題的粒子群優(yōu)化算法

(1)編碼初始化.本文使用整數(shù)編碼， 17個蘋果需求點，用4輛車來進行配送，用從1到17的整數(shù)排列來表示粒子的狀態(tài)X(x1，x2，…,xi)，隨機生成初始種群；之后解碼為1～20的20個隨機數(shù)，因為有4輛車來配送，插入3個數(shù)將17個需求點分成4組，由4輛車分別給這4組需求點進行送貨.編程的重點是要在每個粒子中插入三個數(shù)表示配送中心.

(2)適應度及約束條件計算.用PSO算法優(yōu)化客戶排序時，按照客戶的排列順序分配車輛，在每條線路的內(nèi)部，用最鄰近法優(yōu)化線路.根據(jù)式(1)計算粒子的目標函數(shù)Z，粒子的適應度為目標函數(shù)Fitness=Z；計算約束條件每輛車的限載量為4噸.

(3)初始化局部最優(yōu)和全局最優(yōu).當前各粒子的位置適應度是初始化局部最優(yōu)pbest，所有局部最優(yōu)中適應度值最優(yōu)的適應度值是全局最優(yōu)值gbest，對應的粒子為最優(yōu)解.

(4)位置、速度按照公式(9)、(10)更新.

(5)循環(huán)終止.當循環(huán)到最大迭代次數(shù)時循環(huán)結(jié)束(或找到全局最優(yōu)值停止循環(huán))輸出最優(yōu)路徑和適應度值.否則，繼續(xù)更新位置和速度繼續(xù)迭代.

表1 配送中心與需求點之間的

4.3 實例結(jié)果分析

根據(jù)上述實例的特點，作者利用計算機設(shè)計了粒子群算法的參數(shù)，通過matlab的運行隨機求解10次，得到計算結(jié)果見表2.

表2 冷鏈物流配送路徑優(yōu)化問題的粒子群算法計算結(jié)果

從表2中的數(shù)據(jù)可以看出，第6次得到了該問題的最優(yōu)解186.9 km，其對應的配送路徑方案為：路徑1：0-15-14-5-9-0；路徑2：0-13-12-11-16-0；路徑3：0-2-17-4-1-0；路徑4：0-3-8-7-10-6-0.由此可見，對于冷鏈物流配送路徑優(yōu)化問題，運用粒子群優(yōu)化算法可以方便有效的求得最優(yōu)解.

5 結(jié)論

在農(nóng)產(chǎn)品配送系統(tǒng)中，合理的選擇物流配送路徑是提高服務質(zhì)量、降低配送成本、提高經(jīng)濟效益的重要手段.本文在建立了冷鏈物流配送路徑優(yōu)化模型的基礎(chǔ)上，通過對配送路徑優(yōu)化問題的分析，構(gòu)建了求解冷鏈物流配送路徑問題的粒子群優(yōu)化算法，通過實例進行試驗計算，結(jié)果表明運用粒子群優(yōu)化算法可以求得最優(yōu)解.

[1] 吳稼樂，陳 堅，朱富強.低溫物流基本構(gòu)架和關(guān)鍵技術(shù)的探討[J].制冷,2004，23(2)：29-33.

[2] 王 楊，顧英男.我國農(nóng)產(chǎn)品冷鏈物流的研究[J].物流工程與管理,2010,32(9):4-6.

[3] 黃利偉.我國農(nóng)產(chǎn)品冷鏈物流發(fā)展的問題與對策研究[D].北京：中國農(nóng)業(yè)科學院，2007.

[4] Wanglan.A research on related questions of Chinese food cold chain development[J].International Conference on Management of Commerce and Government,2008,(8):18-21.

[5] 蘇秀謹.食品冷鏈的物流規(guī)劃研究[D].北京：國際經(jīng)濟貿(mào)易學院，2005.

[6] 胡軍珠.北京Y公司蔬菜冷鏈運輸流程優(yōu)化研究[D].北京：北京交通大學，2009.

[7] Rohit Joshi.A Delphi-AHP-TOPSIS based benchmarking framework for performance improvement of a cold chain[J].Expert Systems with Applications,2011，(38):10 170-10 182.

[8] R.Montanari.Cold chain tracking:a managerial perspective[J].Trends in Food Science & Technology,2008,(19):425-431.

[9] 張春穎.我國西部特色農(nóng)產(chǎn)品冷鏈物流的發(fā)展現(xiàn)狀與策略研究[J].物流科技，2010,34(10):50-54.

[10] 吳 敏.我國農(nóng)產(chǎn)品冷鏈物流體系建設(shè)的出路探討[J].商品儲運與養(yǎng)護，2008,30(7):13-16.