詹長書，李正嬌

（東北林業(yè)大學(xué) 交通學(xué)院，黑龍江 哈爾濱 150040）

基于改進蟻群算法的鮮活農(nóng)產(chǎn)品配送路徑優(yōu)化

詹長書，李正嬌

（東北林業(yè)大學(xué) 交通學(xué)院，黑龍江 哈爾濱 150040）

根據(jù)鮮活農(nóng)產(chǎn)品“易腐”等自身特點、客戶的消費特點以及目前鮮活農(nóng)產(chǎn)品配送中存在的問題，基于VRP理論，構(gòu)建物流配送路徑優(yōu)化模型，應(yīng)用改進的蟻群算法對模型進行求解，滿足顧客對時間、質(zhì)量的要求，降低配送成本，提高顧客滿意度。

最大最小蟻群算法；鮮活農(nóng)產(chǎn)品；配送；路徑優(yōu)化

1 引言

遺傳算法對模型進行優(yōu)化求解。本文采用改進的蟻群算法求解配送優(yōu)化模型，獲得最優(yōu)解。

目前，我國農(nóng)產(chǎn)品存在流通損耗嚴重，配送成本高等問題。為了提高服務(wù)水平，降低運費成本和損失成本，在新鮮農(nóng)產(chǎn)品配送系統(tǒng)中，需要采取更有效的配送策略，實現(xiàn)低成本、高效率的物流配送。

國內(nèi)針對鮮活農(nóng)產(chǎn)品配送的研究有很多，如楊磊[1]、李雅萍[2]等構(gòu)建了鮮活農(nóng)產(chǎn)品配送優(yōu)化模型，分別應(yīng)用遺傳算法等對其進行求解，通過算例對構(gòu)建的模型進行驗證。向敏[3]、莊景明[4]分別構(gòu)建了電子商務(wù)下和鮮活農(nóng)產(chǎn)品回收路線的配送優(yōu)化模型，應(yīng)用遺傳算法與改進的

2 模型構(gòu)建

2.1 模型描述與假設(shè)

鮮活農(nóng)產(chǎn)品的配送過程為：由鮮活農(nóng)產(chǎn)品的加工配送中心根據(jù)各用戶的需求量進行配送。為降低成本實現(xiàn)利益最大化，對配送中心作如下假設(shè)：

（1）每個客戶地理位置和需求量已知；

（2）每條配送路徑上各客戶的貨物需求量之和在車輛最大載重量范圍內(nèi)；

（3）每個客戶僅由一輛配送車輛服務(wù)，且配送量不超過車載量限制；

（4）貨物必須在客戶指定時間窗內(nèi)送到；

（5）配送中心農(nóng)產(chǎn)品儲存充足，可以滿足客戶的需要；

（6）車輛配送速度已知；

（7）僅考慮時間因素對品質(zhì)的影響。

2.2 符號定義

對各相關(guān)參數(shù)變量用數(shù)學(xué)符號進行如下定義：

V0：配送中心；

m：擁有車輛數(shù)；

dij：從需求節(jié)點i到需求節(jié)點 j距離；

vij：從需求節(jié)點i到需求節(jié)點 j行駛速度；

τij=：配送車輛從需求節(jié)點i行駛到需求節(jié)點 j所花的時間；

wik：車輛k到節(jié)點i時處理配送任務(wù)所需要時間；

qi：需求點i的需求量；

si：節(jié)點i處貨物到達所允許的最早開始時間；

ei：節(jié)點i處貨物到達所允許的最遲開始時間；

cij：從需求節(jié)點i到需求節(jié)點 j的運輸成本；

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

Dave和Shiue[5-6]等通過對物品的變質(zhì)速度研究，指出具有隨機生命周期的易腐物品的變質(zhì)速率常用指數(shù)形式表示。鮮活農(nóng)產(chǎn)品變質(zhì)函數(shù) Q(t)=Q0?K?e-βt中 Q0為其完好時的質(zhì)量，K為變質(zhì)常數(shù)，β為敏感系數(shù)，若 β的取值小，說明鮮活農(nóng)產(chǎn)品對時間敏感度相對大，t為運輸時的時間。在本文中，用新鮮農(nóng)產(chǎn)品的指數(shù)變質(zhì)函數(shù)描述其質(zhì)量隨時間和溫度的變化。

2.4 模型構(gòu)建

首先建立以下變量：

則鮮活農(nóng)產(chǎn)品配送路線優(yōu)化問題的數(shù)學(xué)模型為：

式（1）為目標函數(shù)，由兩項組成，第一項為運輸成本，第二項為損耗成本。式（2）指配送車輛數(shù)小于配送中心車輛總數(shù)。式（3）指車輛配送完成任務(wù)后返回配送中心。式（4）與式（5）指每個客戶僅被一輛車服務(wù)。式（6）指客戶所需貨物需求量之和小于車的載重量。式（7）指配送車輛運輸與等待之和小于時間約束。式（8）指在規(guī)定時間窗內(nèi)進行配送。式（9）指考慮變質(zhì)情況下應(yīng)從配送中心發(fā)出的配送量。

3 改進遺傳算法設(shè)計

應(yīng)用改進后的最大最小螞蟻算法（MMAS）對建立的配送模型進行求解。MMAS是德國學(xué)者Stutzle[7]等提出的方案，其算法步驟如下。

Step1：變量初始值設(shè)置。初始時刻Δτij=0。每條路徑上的信息素值為τij=1，迭代次數(shù)nc←0,k←1，車輛行駛時間T_solu=0。車輛剩余載重Q_net=Q，尚未滿足需求的需求點集合V_net={V1,V2,…,Vn}為較大正數(shù)。

Step2：根據(jù)車輛載重量和時間窗的限制，確定螞蟻下一步可選擇的轉(zhuǎn)移點的結(jié)合V_allowd。判斷V_allowd是否為空集，如果V_allowd是空集，置 k←k+1，T_solu=0，Q_net=Q ，V_allowd=V_net。

Step4：判斷V_net是否為空集，如果不是轉(zhuǎn)向步驟Step2；如果是空集，則所有需求點均被配送到貨，則記錄螞蟻個數(shù)k←m。

Step5：對各邊(i,j)進行信息素的更新：

本次螞蟻在路徑搜索中求得全局最優(yōu)解長度：L(gb)=0.1≤ρ≤0.9。

Step6：對信息素上限與下限進行判定與調(diào)整：

Step7：對各邊(i,j) ：設(shè)置 Δ τij←0；nc←nc+1。如果有改善，記錄下當前所求得的解。

Step8：if???nc＜ N C（預(yù)定的迭代次數(shù)），重新迭代，否則跳出。

4 算例驗證

某鮮活農(nóng)產(chǎn)品配送中心向其覆蓋范圍內(nèi)的12個超市進行配送，配送車輛的最大載重量為8t，行駛速度為50km/h。配送中心與12個超市的地理信息見表1，12個超市的需求量—時間窗—處理時間見表2，假設(shè)該鮮活農(nóng)產(chǎn)品隨時間的變質(zhì)函數(shù)為：Qt=Q0?e-t/200。

應(yīng)用MATLAB軟件進行求解，運行20次的結(jié)果分別為：2 168.1，2 147.5，2 156.0，2 142.1，2 143.2，2 142.1，2 146.5，2 142.1，2 142.1，2 159.7，2 142.1，2 142.1，2 142.1，2 143.2，2 120.5，2 160.7，2 142.1，2 142.3。所得的最優(yōu)解為2 120.5。

車輛次序及載重量見表3，具體配送路線圖如圖1所示。算例最優(yōu)化解的變化趨勢如圖2所示，變化趨勢由波動較大逐漸趨向平緩趨向最優(yōu)解。在運行20次后發(fā)現(xiàn)所得解的最差與最優(yōu)結(jié)果相差較小，證明改進的蟻群算法是有效的。

表1 配送節(jié)點位置信息

表2 各客戶的業(yè)務(wù)需求

圖1 各車輛配送路線

圖2 最優(yōu)解趨勢圖

表3 優(yōu)化結(jié)果分析

5 結(jié)論

利用改進后的MMAS算法求解，將鮮活農(nóng)產(chǎn)品的“易腐”特性與時間因素結(jié)合起來構(gòu)建鮮活農(nóng)產(chǎn)品配送路徑優(yōu)化模型。通過實例驗證建立的鮮活農(nóng)產(chǎn)品配送路徑優(yōu)化模型和算法是可行的。本文的研究對于鮮活農(nóng)產(chǎn)品企業(yè)進行車輛調(diào)度的安排有著較強的實用價值。

[1]楊磊,袁喜玲,張智勇.基于顧客滿意度的鮮活農(nóng)產(chǎn)品配送優(yōu)化研究[J].物流技術(shù),2014,(19):137-141.

[2]李雅萍.鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J].價值工程,2013,(31):25-27.

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

[4]莊景明.基于遺傳算法的鮮活農(nóng)產(chǎn)品收購路線優(yōu)化研究[J].韶關(guān)學(xué)院學(xué)報,2012,33(8):24-28.

[5]Dave U,Pandya B.Inventory Returns and Special Sales in a lot-size System with Constant Rate of Deterioration[J].European Journal of Operational Research,1985,(19):305-312.

[6]Shiue Y C.An Inventory Model for Perishable Items in a lotsize System with Quantity Discounts[J].European Journal of Operational Research,1990,(45):260-264.

[7]T.Stützle,H H Hoos.Max-Min Ant System[J].Future Generation Computer Systems,2000,(16):889-914.

Optimization of Fresh Farm Produce Distribution Route Based on Improved Ant Algorithm

Zhan Changshu,LiZhengjiao
(School of Communication,Northeast Forestry University,Harbin 150040,China)

In this paper,in view of the characteristics of fresh farm produce,such as being perishable,the property of consumer behavior and the existing problems in the distribution of fresh farm produce at current stage,we built the corresponding logistics distribution route optimization model based on the VRP theory and solved it using the improved ant algorithm so as to meet the consumer's requirement for time and quality,lower distribution cost and improve customer satisfaction.

max&min ant algorithm;fresh farm produce;distribution;route optimization

F224.0;F762;F252.14

A

1005-152X(2017)09-0089-03

10.3969/j.issn.1005-152X.2017.09.020

2017-08-07

詹長書（1970-），男，東北林業(yè)大學(xué)副教授，研究生導(dǎo)師，研究方向：物流系統(tǒng)規(guī)劃與設(shè)計；李正嬌（1993-），女，東北林業(yè)大學(xué)交通學(xué)院物流工程碩士。