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

汪挺松　魯羅蘭

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

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

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

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

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

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

1文獻(xiàn)評述

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1變量定義

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

（2）j代表牛奶種類，J代表牛奶種類的集合，j∈J；

（3）s，s'代表牧場，S代表牧場的集合s，s'；

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

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

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

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

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

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

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

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

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

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

（14）設(shè)s0代表倉庫

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

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

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

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

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

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

2.2牧場分配模型

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

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

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

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

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

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

3算例驗(yàn)證

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

3.1問題描述

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

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

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

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

4結(jié)論與展望

這篇文章在對牛奶收運(yùn)問題的研究中還存在很多不足之處。例如在路徑優(yōu)化模型中，假定牛奶收運(yùn)的準(zhǔn)備時(shí)間是一定的，但是對于不同類型不同噸位的牛奶，其準(zhǔn)備時(shí)間肯定存在差別；此外，這篇文章選定的實(shí)例涉及到的奶站不多，僅為十個(gè)，因此這篇文章設(shè)計(jì)的算法是否適合求解大型的牛奶收運(yù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)輸車輛路徑優(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] 劉青松.校車路徑問題元啟發(fā)算法設(shè)計(jì)與GIS集成[D].河南大學(xué)碩士學(xué)位論文，2013.