多品種的牛奶收運(yùn)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)

汪挺松　魯羅蘭

摘 要 牛奶收運(yùn)問(wèn)題是一個(gè)特殊的車(chē)輛路徑問(wèn)題。這篇文章以車(chē)輛路徑問(wèn)題的基本解決方法為基礎(chǔ)，結(jié)合牛奶收運(yùn)問(wèn)題的特點(diǎn)，建立了兩個(gè)混合整數(shù)規(guī)劃模型，第一個(gè)是以使用的車(chē)輛數(shù)最少為目標(biāo)的牧場(chǎng)分配模型。另一個(gè)是以收運(yùn)的總時(shí)間最短為目標(biāo)的路徑優(yōu)化模型，主要通過(guò)節(jié)約里程算法求解。最后，這篇文章以一家乳制品企業(yè)為例，通過(guò)上述模型及算法成功實(shí)現(xiàn)了對(duì)該企業(yè)的牛奶收運(yùn)網(wǎng)絡(luò)的優(yōu)化。

關(guān)鍵詞 物流 車(chē)輛路徑 牛奶收運(yùn) 節(jié)約里程法

中圖分類(lèi)號(hào)：F224；F323.7 文獻(xiàn)標(biāo)識(shí)碼：A

對(duì)于很多生產(chǎn)性企業(yè)，原材料的采購(gòu)是至關(guān)重要的，原材料采購(gòu)過(guò)程中的運(yùn)輸成本占據(jù)了原材料采購(gòu)成本的絕大部分，特別是采購(gòu)點(diǎn)偏遠(yuǎn)而且相對(duì)分散的情況下。采購(gòu)牛奶的總成本包括兩個(gè)方面：一方面是牛奶運(yùn)輸?shù)某杀荆硪环矫娴呐Ｄ滩少?gòu)的價(jià)格。在總成本上，乳制品企業(yè)基本上沒(méi)有可降低的空間，因此，各個(gè)乳制品廠家都設(shè)法降低運(yùn)輸成本，因?yàn)槊拷档鸵粏挝坏倪\(yùn)輸成本，他們就能提高一單位的收購(gòu)價(jià)格，從而吸引更多的牧民，進(jìn)而得到更多的奶源。反過(guò)來(lái)，更多奶源可以形成牛奶運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效益，在一定程度上又可以降低物流成本。

然而，在新鮮農(nóng)產(chǎn)品的采購(gòu)中，為了保持農(nóng)產(chǎn)品的鮮度和各項(xiàng)指標(biāo)符合要求，除了運(yùn)輸成本外，還必須要考慮農(nóng)產(chǎn)品的冷藏成本和預(yù)處理的成本等，這使得新鮮農(nóng)產(chǎn)品的采購(gòu)為題比其他原材料的采購(gòu)問(wèn)題更為復(fù)雜。

站在乳制品企業(yè)的角度來(lái)講，研究牛奶收運(yùn)問(wèn)題能夠幫助降低企業(yè)的采購(gòu)成本，從而能適當(dāng)提高牛奶的收購(gòu)價(jià)格，從而可以吸引更多牧場(chǎng)為其提供優(yōu)質(zhì)奶源。另一方面，站在牧場(chǎng)的角度，即需求者的角度，由于牛奶是需要冷藏的，牛奶收運(yùn)問(wèn)題的研究可以使牧場(chǎng)的牛奶能夠高效率的在約定的時(shí)間內(nèi)被收走，這能大大降低牧場(chǎng)的庫(kù)存成本，此外，通過(guò)降低物流成本，乳制品企業(yè)能夠給牧場(chǎng)提供更高的收購(gòu)價(jià)格，這意味著牧場(chǎng)可以獲得更高的收益。因此進(jìn)行牛奶收運(yùn)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)即可以降低乳制品企業(yè)的成本，也可以使牧場(chǎng)獲得更高的采購(gòu)價(jià)格，因此不論對(duì)企業(yè)來(lái)說(shuō)還是對(duì)牧場(chǎng)來(lái)說(shuō)，這篇文章的研究都是十分有意義的。這篇文章的創(chuàng)新之處在于：1、這篇文章研究的是不同品種的牛奶收運(yùn)問(wèn)題，相對(duì)于以往的同種類(lèi)品種的牛奶收運(yùn)問(wèn)題研究，更具有實(shí)際應(yīng)用價(jià)值；2、這篇文章的模型實(shí)現(xiàn)了兩個(gè)目標(biāo)，一是車(chē)輛數(shù)最少，二是收運(yùn)成本最低。

1文獻(xiàn)評(píng)述

這篇文章主要是對(duì)牛奶收運(yùn)網(wǎng)絡(luò)優(yōu)化。牛奶收運(yùn)路徑優(yōu)化問(wèn)題其實(shí)是一個(gè)特殊的車(chē)輛路徑問(wèn)題（VRP），但也有自身的特點(diǎn)：

（1）收運(yùn)的牛奶包含不同的種類(lèi)，由于牛奶自身的特性，不同種類(lèi)的牛奶不能被放到一起，因此運(yùn)輸牛奶的車(chē)輛也與普通的貨車(chē)不同，一般使用罐車(chē)來(lái)運(yùn)輸牛奶，而且罐車(chē)內(nèi)部被分為幾個(gè)部分，每個(gè)部分都有各自的容量限制，并且每個(gè)部分只能用來(lái)裝運(yùn)一種類(lèi)型的牛奶，而且裝運(yùn)的牛奶數(shù)量不能超過(guò)這個(gè)部分的容量限制。

（2）傳統(tǒng)的VRP問(wèn)題是一個(gè)貨物配送的問(wèn)題，但是牛奶收運(yùn)問(wèn)題是一個(gè)原材料采購(gòu)問(wèn)題。牛奶收運(yùn)問(wèn)題可以被視為考慮收集的車(chē)輛路線問(wèn)題，其求解方法也可以通過(guò)在求解基本VRP問(wèn)題的基礎(chǔ)上稍加改進(jìn)而得到。

由于VRP問(wèn)題是難NP問(wèn)題，基本上不能用精確算法求解，求解車(chē)輛運(yùn)輸問(wèn)題的主要方法是啟發(fā)式算法，這篇文章求解牛奶收運(yùn)問(wèn)題的方法主要也是啟發(fā)式算法。

1.1國(guó)外研究現(xiàn)狀

1994年，和建立了一個(gè)基于路徑優(yōu)化的啟發(fā)式算法的決策支持系統(tǒng)（DSS）。1997年，在旅行商問(wèn)題的基礎(chǔ)上進(jìn)行擴(kuò)展，為一家位于愛(ài)爾蘭首都的牛奶企業(yè)解決了牛奶收運(yùn)問(wèn)題。1999年，和其它一些學(xué)者通過(guò)使用一個(gè)嚴(yán)謹(jǐn)?shù)倪\(yùn)算程序解決了一個(gè)牛奶罐車(chē)的調(diào)度和排隊(duì)問(wèn)題。2005年，Butler和其它一些學(xué)者將決策支持系統(tǒng)與地理信息系統(tǒng)整合起來(lái)，這使得車(chē)輛調(diào)度程序可以與路徑優(yōu)化程序互動(dòng)。2007年，和研究了羊奶的收運(yùn)問(wèn)題，并且嘗試通過(guò)建立一個(gè)運(yùn)籌學(xué)模型來(lái)解決這一問(wèn)題。Hoff和將牛奶收運(yùn)問(wèn)題試做一個(gè)卡車(chē)拖車(chē)模型，并且編寫(xiě)了一個(gè)運(yùn)算程序來(lái)求解。

1.2國(guó)內(nèi)研究現(xiàn)狀

徐永花、黃立君將改進(jìn)遺傳算法應(yīng)用于牛奶收運(yùn)問(wèn)題，并通過(guò)對(duì)51個(gè)城市進(jìn)行了仿真計(jì)算，取得了較好的優(yōu)化效果。

李雅萍在對(duì)鮮活農(nóng)產(chǎn)品的物流配送路徑的研究中，構(gòu)建了帶時(shí)間窗的鮮活農(nóng)產(chǎn)品冷鏈物流配送的成本模型。

李宮韜在對(duì)物流配送系統(tǒng)的研究中，實(shí)現(xiàn)了基于GIS地理空間數(shù)據(jù)和運(yùn)輸線路的自動(dòng)規(guī)劃。

劉青松在對(duì)校車(chē)路徑問(wèn)題的研究中，通過(guò)設(shè)計(jì)元啟發(fā)算法進(jìn)行路徑優(yōu)化，并將優(yōu)化算法集成在GIS中，為校車(chē)路徑規(guī)劃提供了軟件工具。

2模型建立及算法實(shí)現(xiàn)

這篇文章建立了兩個(gè)優(yōu)化模型，一個(gè)模型是牧場(chǎng)分配模型，第二個(gè)模型是路徑優(yōu)化模型。

2.1變量定義

（1）設(shè)i為罐車(chē)，I代表罐車(chē)隊(duì)，i∈I；

（2）j代表牛奶種類(lèi)，J代表牛奶種類(lèi)的集合，j∈J；

（3）s，s'代表牧場(chǎng)，S代表牧場(chǎng)的集合s，s'；

（4）k代表罐車(chē)的一個(gè)部分，ki代表罐車(chē)i的幾個(gè)間隔的集合k∈K；

（5）Qjs代表牧場(chǎng)s擁有牛奶j的數(shù)量；

（6）cik代表罐車(chē)i的第k部分的容量

（7）yikjs代表牧場(chǎng)s的類(lèi)型j的牛奶裝運(yùn)在罐車(chē)i的k部分的數(shù)量；如果yikjs>0，代表罐車(chē)i必須裝運(yùn)一定量的牧場(chǎng)s的j類(lèi)型牛奶。

（8）設(shè)0-1變量

（9）設(shè)0-1變量

（10）設(shè)0-1變量

（11）設(shè)0-1變量

（12）設(shè)R*代表由牧場(chǎng)分配模型確定的車(chē)輛數(shù)

（13）設(shè)Si代表罐車(chē)i服務(wù)的牧場(chǎng)的集合，i∈I，i=1，2，…，R*，

（14）設(shè)s0代表倉(cāng)庫(kù)

（15）設(shè)succ（s）代表在牧場(chǎng)s之前被服務(wù)的牧場(chǎng)的集合

（16）設(shè)pred（s）代表在牧場(chǎng)s之后被服務(wù)的牧場(chǎng)的集合

（17）設(shè)dss'代表牧場(chǎng)s于s'間的距離

（18）設(shè)v代表罐車(chē)的速度

（19）設(shè)ts代表牧場(chǎng)s的準(zhǔn)備時(shí)間

（20）設(shè)T代表罐車(chē)司機(jī)每天的最長(zhǎng)工作時(shí)間

2.2牧場(chǎng)分配模型

牧場(chǎng)分配模型的總目標(biāo)是使投入的車(chē)輛數(shù)最少，整體模型如下：

2.3路徑優(yōu)化模型

路徑優(yōu)化模型的目標(biāo)是使牛奶收運(yùn)總時(shí)間最短，整體的模型如下：

2.4算法實(shí)現(xiàn)

這篇文章將問(wèn)題分為兩個(gè)階段進(jìn)行求解，第一階段模型主要用matlab求解。在第二階段解決路徑優(yōu)化模型，這篇文章主要通過(guò)節(jié)約里程法得到每輛罐車(chē)的最優(yōu)路徑。

節(jié)約里程法是一種用來(lái)解決運(yùn)輸車(chē)輛數(shù)與配送路徑不確定的問(wèn)題的一種啟發(fā)式算法。節(jié)約里程法的基本思想是通過(guò)合并兩個(gè)不同的回路為一個(gè)回路，從而減少配送距離，提高車(chē)輛的裝載率。

3算例驗(yàn)證

這篇文章以中國(guó)的某乳制品企業(yè)的一個(gè)奶源基地為例，使用對(duì)第一階段的模型進(jìn)行了求解，并通過(guò)節(jié)約里程法求解第二階段的路徑優(yōu)化模型。

3.1問(wèn)題描述

這篇文章選取了該企業(yè)的一個(gè)奶源區(qū)域進(jìn)行了分析和優(yōu)化。奶源基地共有十個(gè)奶站，每個(gè)奶站的牛奶種類(lèi)都各有不同，該乳制品企業(yè)將牛奶的種類(lèi)分為高質(zhì)量、質(zhì)量良好、質(zhì)量一般、質(zhì)量合格四種。該乳制品企業(yè)擁有罐車(chē)分為三種車(chē)型，分別是6噸、11噸和13噸。6噸的車(chē)有15輛，11噸的車(chē)有10輛，13噸的車(chē)有8輛。所有的牛奶必須在6小時(shí)內(nèi)收運(yùn)完。對(duì)于該乳制品企業(yè)，工作人員在該區(qū)域的牛奶收運(yùn)時(shí)間限制為6小時(shí)，車(chē)速是35千米/小時(shí)。

3.2牧場(chǎng)分配模型的優(yōu)化結(jié)果

第一階段的車(chē)輛分配的運(yùn)算程序得到的最優(yōu)結(jié)果是：共需要三輛罐車(chē)，13噸的一輛、11噸的一輛、8噸的一輛。牧場(chǎng)1、牧場(chǎng)6、牧場(chǎng)3、牧場(chǎng)7被分配給了13噸的罐車(chē)；牧場(chǎng)5、牧場(chǎng)9、牧場(chǎng)8被分配給了8噸的罐車(chē)；牧場(chǎng)4、牧場(chǎng)2、牧場(chǎng)10被分配給了11噸的罐車(chē)。

利用上述算法對(duì)上述區(qū)域的牛奶收運(yùn)網(wǎng)絡(luò)進(jìn)行優(yōu)化，優(yōu)化結(jié)果為：一共需要三輛罐車(chē)對(duì)這十個(gè)奶站的牛奶進(jìn)行收運(yùn)，通過(guò)節(jié)約里程法為該乳制品企業(yè)節(jié)約了934km的運(yùn)輸路程。

4結(jié)論與展望

這篇文章在對(duì)牛奶收運(yùn)問(wèn)題的研究中還存在很多不足之處。例如在路徑優(yōu)化模型中，假定牛奶收運(yùn)的準(zhǔn)備時(shí)間是一定的，但是對(duì)于不同類(lèi)型不同噸位的牛奶，其準(zhǔn)備時(shí)間肯定存在差別；此外，這篇文章選定的實(shí)例涉及到的奶站不多，僅為十個(gè)，因此這篇文章設(shè)計(jì)的算法是否適合求解大型的牛奶收運(yùn)問(wèn)題尚待驗(yàn)證。

參考文獻(xiàn)

[1] Sankaran.J.K，R.R.Ubgade.Routing tankers for dairy milk

Pick up. Interfaces，1994.24（5）：59-66.

[2] Butler.M，P. Herlihy，P.B.Keenan.Integrating information technology and operational research in the management of milk collection[J].Food Engrg，2005.70（3）：341-349.

[3] Basnet.C，L.R.Foulds，J.M.Wilson.An exact algorithm for a milk tanker scheduling and sequencing problem.Ann.Oper.Res，1999（86）：559-568.

[4] Butler.M， P.Herlihy， P.B.Keenan.Integrating information technology and operational research in the management of milk collection[J].Food Engrg，2005.70（3） 341-349.

[5] Claassen G D H， Hendriks T H B. An application of Special Ordered Sets to a periodic milk collection problem[J]. European Journal of Operational Research， 2007， 180（2）：754-769.

[6] Hoff.A，A.L？kketangen.A tabu search approach for milk collection in western Norway using trucks and trailers.Proc.Sixth Triennial Sympos.Transportation Anal：Phuket Island， Thailand.2007.

[7] 徐永花，黃立君.改進(jìn)遺傳算法在牛奶運(yùn)輸車(chē)輛路徑優(yōu)化中的應(yīng)用[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào)，2008.39（11）：111-115.

[8] 李雅萍.鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[D].Value Engineering，2013（31）：25-28.

[9] 李宮韜.基于GIS的物流配送系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].北京郵電大學(xué)碩士學(xué)位論文，2012.

[10] 劉青松.校車(chē)路徑問(wèn)題元啟發(fā)算法設(shè)計(jì)與GIS集成[D].河南大學(xué)碩士學(xué)位論文，2013.