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

詹長(zhǎng)書，李正嬌

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

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

詹長(zhǎng)書，李正嬌

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

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

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

1 引言

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

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

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

2 模型構(gòu)建

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

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

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

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

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

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

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

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

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

2.2 符號(hào)定義

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

V0：配送中心；

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

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

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

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

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

qi：需求點(diǎn)i的需求量；

si：節(jié)點(diǎn)i處貨物到達(dá)所允許的最早開始時(shí)間；

ei：節(jié)點(diǎn)i處貨物到達(dá)所允許的最遲開始時(shí)間；

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

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

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

2.4 模型構(gòu)建

首先建立以下變量：

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

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

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

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

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

Step2：根據(jù)車輛載重量和時(shí)間窗的限制，確定螞蟻下一步可選擇的轉(zhuǎn)移點(diǎ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；如果是空集，則所有需求點(diǎn)均被配送到貨，則記錄螞蟻個(gè)數(shù)k←m。

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

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

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

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

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

4 算例驗(yàn)證

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

應(yīng)用MATLAB軟件進(jìn)行求解，運(yùn)行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)化解的變化趨勢(shì)如圖2所示，變化趨勢(shì)由波動(dòng)較大逐漸趨向平緩趨向最優(yōu)解。在運(yùn)行20次后發(fā)現(xiàn)所得解的最差與最優(yōu)結(jié)果相差較小，證明改進(jìn)的蟻群算法是有效的。

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

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

圖1 各車輛配送路線

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

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

5 結(jié)論

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

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

[2]李雅萍.鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J].價(jià)值工程,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)品收購(gòu)路線優(yōu)化研究[J].韶關(guān)學(xué)院學(xué)報(bào),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

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