時(shí)間窗約束下的生鮮產(chǎn)品物流配送路徑優(yōu)化研究

楊 婷,周建國(guó)

(湖南科技大學(xué),湖南 湘潭 411201)

時(shí)間窗約束下的生鮮產(chǎn)品物流配送路徑優(yōu)化研究

楊 婷,周建國(guó)

(湖南科技大學(xué),湖南 湘潭 411201)

傳統(tǒng)的“重生產(chǎn),輕流通”的思想已經(jīng)不能滿足當(dāng)前人們對(duì)于農(nóng)產(chǎn)品的要求。選擇最優(yōu)的物流配送路徑,對(duì)降低流通成本、促進(jìn)農(nóng)產(chǎn)品流通等具有重大意義。文章通過(guò)構(gòu)建客戶滿意度函數(shù)和物流成本函數(shù)對(duì)時(shí)間窗條件下的生鮮產(chǎn)品配送路徑進(jìn)行優(yōu)化,設(shè)計(jì)仿真實(shí)驗(yàn)、采用單親遺傳算法來(lái)求解該問(wèn)題。實(shí)例證明該優(yōu)化后模型能更好地解決農(nóng)產(chǎn)品流通過(guò)程中的問(wèn)題,能為農(nóng)產(chǎn)品物流配送路線研究提供借鑒意義。

農(nóng)產(chǎn)品物流；時(shí)間窗；客戶滿意度；遺傳算法；VRP

1 引 言

隨著生活水平的提高,國(guó)民對(duì)農(nóng)產(chǎn)品流通環(huán)節(jié)的重視程度也隨之上升。當(dāng)前國(guó)內(nèi)農(nóng)產(chǎn)品存在著流通成本過(guò)高、客戶滿意度低等問(wèn)題。生鮮領(lǐng)域在農(nóng)產(chǎn)品中占據(jù)很大比重,同樣存在這些問(wèn)題,已經(jīng)成為制約生鮮產(chǎn)品流通的重要因素。本文探討生鮮產(chǎn)品流通中的現(xiàn)實(shí)問(wèn)題,通過(guò)優(yōu)化后得到最優(yōu)的配送路徑,以最低的成本、客戶最滿意的服務(wù)完成產(chǎn)品的配送。

路徑優(yōu)化問(wèn)題(VRP)屬于組合優(yōu)化問(wèn)題,對(duì)于這種問(wèn)題很難精確求解。[1]目前解決這類問(wèn)題大多數(shù)依靠啟發(fā)式算法,例如,遺傳算法、蟻群算法、粒子群算法、模擬退火算法等。國(guó)外學(xué)者最先開始研究生鮮物流配送問(wèn)題。Solomon將時(shí)間窗與VRP問(wèn)題結(jié)合,為研究生鮮物流配送路徑提供借鑒意義；Brito等研究了在不確定時(shí)空情況下的冷凍食品VRP問(wèn)題,并通過(guò)軟方法求解。王紅玲等人以配送時(shí)間最短,成本最低為優(yōu)化目標(biāo)采用改進(jìn)粒子群算法求解該問(wèn)題；向敏[2]等人在電子商務(wù)環(huán)境下規(guī)劃生鮮產(chǎn)品配送的網(wǎng)絡(luò)體系,設(shè)計(jì)配送路徑,減少物流成本。

基于以上文獻(xiàn),各國(guó)學(xué)者對(duì)時(shí)間窗約束下的生鮮VRP問(wèn)題的研究取得了許多成果,但把時(shí)間窗約束下客戶滿意度作為首要約束條件的研究較少。當(dāng)前社會(huì)客戶已經(jīng)成為企業(yè)生存發(fā)展的戰(zhàn)略性資源,企業(yè)在任何情況下都不能忽視客戶的感受。出于這種考慮,眾多企業(yè)越發(fā)重視客戶滿意度。本文將生鮮產(chǎn)品配送過(guò)程中的成本函數(shù)和顧客滿意函數(shù)相結(jié)合,通過(guò)案例證明能為研究生鮮產(chǎn)品物流路線問(wèn)題提供借鑒意義。

2 生鮮產(chǎn)品物流路徑優(yōu)化模型

2.1 模型描述

現(xiàn)假定某區(qū)域內(nèi)的一農(nóng)產(chǎn)品企業(yè)計(jì)劃從配送中心向L超市配送生鮮產(chǎn)品,每個(gè)超市之間有一定距離,配送中心之間也有一定距離。每個(gè)超市只有在規(guī)定的時(shí)間窗(Eti,Lti)內(nèi),才可以進(jìn)行相應(yīng)的服務(wù),車輛提前到達(dá)需要支付等待費(fèi)用,延遲到達(dá)則需要支付大量的延遲費(fèi)用。每個(gè)超市只由一個(gè)車輛負(fù)責(zé)配送,由k輛車負(fù)責(zé)配送。要在此區(qū)域內(nèi)確定合適的配送路線,使之配送成本最少,所獲得客戶滿意度最大。

2.2 顧客滿意度函數(shù)

2.3 模型建立

根據(jù)上述要求,模型以物流總成本最小為目標(biāo),將顧客滿意度作為首要約束條件。總成本包括運(yùn)輸費(fèi)用、等待費(fèi)用及延遲費(fèi)用。則最終的總成本模型如下：

S.t：

(1)

(2)

(3)

(4)

(5)

dij：超市之間的距離；i,j:超市的編號(hào)；H:單位路程運(yùn)費(fèi)率；Mi:各個(gè)超市的需求量；C:等待費(fèi)用；S:等待時(shí)間；q:延遲費(fèi)用；Q:每輛汽車的最大運(yùn)載量。

若xijk表示車輛k經(jīng)過(guò)超市i,j,則xijk=1,反之則為0。若yik表示車輛k為顧客i服務(wù),則yik=1,反之則為0。

式(1)表示確保平均客戶滿意度在90%以上；式(2)表示一條路線上汽車所載的貨物重量不超過(guò)汽車載重量；式(3)～式(5)表示每一個(gè)超市只由一輛車運(yùn)輸。

3 時(shí)間窗VRP下遺傳算法的描述

由于遺傳算法(Genetic Algorithm,GA)[4]本身的局限性,如過(guò)早“收斂”“早熟”等現(xiàn)象,所以本文借助一種改進(jìn)的遺傳算法進(jìn)行該VRP問(wèn)題的求解-單親遺傳算法(PGA)。[5]

3.1 關(guān)于遺傳算法(GA)與單親遺傳算法(PGA)的比較

(一)遺傳算法(GA)在解決VRP問(wèn)題時(shí),主要通過(guò)交叉算子實(shí)現(xiàn)整個(gè)種群的演變。但在使用序數(shù)編碼時(shí)候,個(gè)別問(wèn)題不能進(jìn)行交叉操作,交叉操作會(huì)使產(chǎn)生的新染色體對(duì)應(yīng)的解不在原問(wèn)題的解集中。[6]PGA取消了傳統(tǒng)遺傳算法的交叉操作,代之以僅在一條染色體上進(jìn)行基因重組等遺傳算子,即PGA采用單親遺傳的方式,簡(jiǎn)化了遺傳操作,提高了尋優(yōu)速度。

(二)GA中主要有選擇、交叉、變異等種群進(jìn)化算子。PGA的種群進(jìn)化方式主要借助于選擇算子,基因重組算子(包括基因換位、基因倒位、基因移位等改變基因順序算子)和基因突變算子等,PGA中的基因重組實(shí)現(xiàn)了GA的交叉和變異功能。PGA的選擇算子與GA的選擇算子無(wú)異。

3.2 編碼方案

為了克服二進(jìn)制編碼解決VRP問(wèn)題的先天性不足,本文采用序數(shù)編碼,0表示配送中心,1,2,3…表示客戶,隨機(jī)產(chǎn)生一組數(shù)表示初始種群。具體編碼思路如下：

(1)從左向右累計(jì)客戶的需求量,一旦累計(jì)需求量超過(guò)貨車的載重量就停止計(jì)數(shù),設(shè)經(jīng)過(guò)n次累計(jì)之后累積量超過(guò)貨車的載重,則記錄此時(shí)的斷點(diǎn)一為n-1,累積量清零。

(2)從排列的第n位開始繼續(xù)重復(fù)第一步,假設(shè)再次累計(jì)量超過(guò)貨車載重量時(shí),此時(shí)的累計(jì)次數(shù)為m,記錄此時(shí)的斷點(diǎn)為n+m-1,累積量清零。

(3)重復(fù)以上步驟直至排列的最后一位,生成斷點(diǎn)矩陣。

(4)依據(jù)斷點(diǎn)矩陣,在排列對(duì)應(yīng)位置后面加上0,同時(shí)在排列首末位加上0,染色體生成完成。

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)[7](ft)用于表示當(dāng)前種群中的個(gè)體對(duì)于待優(yōu)化問(wèn)題的優(yōu)良性,一般根據(jù)目標(biāo)函數(shù)確定。本文選取(ft)=1/(Zmin+V.q)。V為一個(gè)很大的正整數(shù),表示懲罰系數(shù),q為延遲費(fèi)用。

4實(shí)例及仿真

結(jié)合實(shí)際研究課題,在一個(gè)區(qū)域內(nèi)隨機(jī)散布1個(gè)配送中心和12個(gè)超市(詳見(jiàn)表1)。配送采用單一的貨車運(yùn)輸。實(shí)驗(yàn)中采取以下參數(shù)：

汽車裝載量為5.5噸,平均車速60km/h,車輛等待費(fèi)用為每小時(shí)20元,延遲費(fèi)用q=100元。每天最早出發(fā)時(shí)間為6：00。單位路程運(yùn)費(fèi)率H=25,等待費(fèi)用C=20。懲罰系數(shù)V=500。選擇概率pc取0.15,單親遺傳算法的最大基因換位次數(shù)為6。初始種群個(gè)數(shù)為20。現(xiàn)要求確定總成本最少、客戶最滿意的配送方案。

表1 各超市的需求量,服務(wù)時(shí)間,時(shí)間窗

根據(jù)上述改進(jìn)的遺傳算法寫出C語(yǔ)言程序,在Matlab 2015程序下對(duì)該模型進(jìn)行1000次迭代。仿真得出4條最優(yōu)的配送路徑(見(jiàn)表2)分別為：路徑一：0-6-1-7-0；路徑二：0-4-10-3-0；路徑三：0-12-5-9-11-0；路徑四：0-2-8-0。最終系統(tǒng)總成本為19214,客戶滿意度為93%。與全局最優(yōu)解較接近。圖1表示的模型總成本隨迭代次數(shù)的尋優(yōu)過(guò)程,圖中可以看出遺傳算法搜索結(jié)果較快,隨著進(jìn)化進(jìn)行,種群內(nèi)優(yōu)良個(gè)體逐漸增多,總成本從開始的22000多迅速趨近于全局最優(yōu)解,并在300代左右開始收斂。說(shuō)明了算法具有很好的尋優(yōu)能力。

最佳運(yùn)輸費(fèi)用隨迭代次數(shù)的進(jìn)化過(guò)程

路徑一超市編號(hào)6170到達(dá)時(shí)刻(h)84382932881096630路徑二超市編號(hào)41030到達(dá)時(shí)刻(h)83691989221236760

續(xù) 表

5 結(jié) 論

本文對(duì)生鮮產(chǎn)品VRP問(wèn)題進(jìn)行了研究,建立了配送總成本模型。基于此類模型求解的復(fù)雜性,本文在傳統(tǒng)的遺傳算法基礎(chǔ)上引入單親遺傳算法概念,來(lái)尋求配送路徑的最佳方案。文中實(shí)例分析表明,本文提出的時(shí)間窗約束下的生鮮產(chǎn)品配送路徑和客戶滿意度之間的最大平衡,能夠滿足一定階段下的農(nóng)產(chǎn)品企業(yè)和客戶的現(xiàn)實(shí)需求,降低了成本,提高了配送效率,并且使得客戶滿意度得到最大滿足。對(duì)于相關(guān)企業(yè)來(lái)說(shuō),本文的研究可以為企業(yè)帶來(lái)無(wú)形的價(jià)值——企業(yè)自身形象和企業(yè)的經(jīng)濟(jì)效益,進(jìn)而增強(qiáng)企業(yè)的競(jìng)爭(zhēng)力。

[1]羅勇,陳治亞.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化[J].系統(tǒng)工程,2012(8).

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

[3]鄧麗君.基于客戶滿意度的物流配送車輛調(diào)度優(yōu)化模型與算法研究[D].北京：北京交通大學(xué),2012.

[4]J.H.Holland.Adaptation in Natural and Artificial System[M].Cambridge:Mit Press,1975.

[5]李茂軍,朱陶業(yè),童調(diào)生.單親遺傳算法與傳統(tǒng)遺傳算法比較研究[J].系統(tǒng)工程,2001,19(1).

[6]梁承姬,黃濤,徐德洪,等.改進(jìn)遺傳算法求解帶模糊時(shí)間窗冷鏈配送問(wèn)題[J].廣西大學(xué)學(xué)報(bào),2016,41(3).

[7]雷英杰,張善文.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社,2014.

10.13939/j.cnki.zgsc.2016.49.023