多品種的牛奶收運網絡優化設計

汪挺松　魯羅蘭

摘 要 牛奶收運問題是一個特殊的車輛路徑問題。這篇文章以車輛路徑問題的基本解決方法為基礎，結合牛奶收運問題的特點，建立了兩個混合整數規劃模型，第一個是以使用的車輛數最少為目標的牧場分配模型。另一個是以收運的總時間最短為目標的路徑優化模型，主要通過節約里程算法求解。最后，這篇文章以一家乳制品企業為例，通過上述模型及算法成功實現了對該企業的牛奶收運網絡的優化。

關鍵詞 物流 車輛路徑 牛奶收運 節約里程法

中圖分類號：F224；F323.7 文獻標識碼：A

對于很多生產性企業，原材料的采購是至關重要的，原材料采購過程中的運輸成本占據了原材料采購成本的絕大部分，特別是采購點偏遠而且相對分散的情況下。采購牛奶的總成本包括兩個方面：一方面是牛奶運輸的成本，另一方面的牛奶采購的價格。在總成本上，乳制品企業基本上沒有可降低的空間，因此，各個乳制品廠家都設法降低運輸成本，因為每降低一單位的運輸成本，他們就能提高一單位的收購價格，從而吸引更多的牧民，進而得到更多的奶源。反過來，更多奶源可以形成牛奶運輸的規模經濟效益，在一定程度上又可以降低物流成本。

然而，在新鮮農產品的采購中，為了保持農產品的鮮度和各項指標符合要求，除了運輸成本外，還必須要考慮農產品的冷藏成本和預處理的成本等，這使得新鮮農產品的采購為題比其他原材料的采購問題更為復雜。

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

1文獻評述

這篇文章主要是對牛奶收運網絡優化。牛奶收運路徑優化問題其實是一個特殊的車輛路徑問題（VRP），但也有自身的特點：

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

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

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

1.1國外研究現狀

1994年，和建立了一個基于路徑優化的啟發式算法的決策支持系統（DSS）。1997年，在旅行商問題的基礎上進行擴展，為一家位于愛爾蘭首都的牛奶企業解決了牛奶收運問題。1999年，和其它一些學者通過使用一個嚴謹的運算程序解決了一個牛奶罐車的調度和排隊問題。2005年，Butler和其它一些學者將決策支持系統與地理信息系統整合起來，這使得車輛調度程序可以與路徑優化程序互動。2007年，和研究了羊奶的收運問題，并且嘗試通過建立一個運籌學模型來解決這一問題。Hoff和將牛奶收運問題試做一個卡車拖車模型，并且編寫了一個運算程序來求解。

1.2國內研究現狀

徐永花、黃立君將改進遺傳算法應用于牛奶收運問題，并通過對51個城市進行了仿真計算，取得了較好的優化效果。

李雅萍在對鮮活農產品的物流配送路徑的研究中，構建了帶時間窗的鮮活農產品冷鏈物流配送的成本模型。

李宮韜在對物流配送系統的研究中，實現了基于GIS地理空間數據和運輸線路的自動規劃。

劉青松在對校車路徑問題的研究中，通過設計元啟發算法進行路徑優化，并將優化算法集成在GIS中，為校車路徑規劃提供了軟件工具。

2模型建立及算法實現

這篇文章建立了兩個優化模型，一個模型是牧場分配模型，第二個模型是路徑優化模型。

2.1變量定義

（1）設i為罐車，I代表罐車隊，i∈I；

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

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

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

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

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

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

（8）設0-1變量

（9）設0-1變量

（10）設0-1變量

（11）設0-1變量

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

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

（14）設s0代表倉庫

（15）設succ（s）代表在牧場s之前被服務的牧場的集合

（16）設pred（s）代表在牧場s之后被服務的牧場的集合

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

（18）設v代表罐車的速度

（19）設ts代表牧場s的準備時間

（20）設T代表罐車司機每天的最長工作時間

2.2牧場分配模型

牧場分配模型的總目標是使投入的車輛數最少，整體模型如下：

2.3路徑優化模型

路徑優化模型的目標是使牛奶收運總時間最短，整體的模型如下：

2.4算法實現

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

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

3算例驗證

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

3.1問題描述

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

3.2牧場分配模型的優化結果

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

利用上述算法對上述區域的牛奶收運網絡進行優化，優化結果為：一共需要三輛罐車對這十個奶站的牛奶進行收運，通過節約里程法為該乳制品企業節約了934km的運輸路程。

4結論與展望

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

參考文獻

[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].東北農業大學學報，2008.39（11）：111-115.

[8] 李雅萍.鮮活農產品冷鏈物流配送路徑優化研究[D].Value Engineering，2013（31）：25-28.

[9] 李宮韜.基于GIS的物流配送系統的設計與實現[D].北京郵電大學碩士學位論文，2012.

[10] 劉青松.校車路徑問題元啟發算法設計與GIS集成[D].河南大學碩士學位論文，2013.