多品种的牛奶收运网络优化设计

汪挺松　鲁罗兰

摘 要 牛奶收运问题是一个特殊的车辆路径问题。这篇文章以车辆路径问题的基本解决方法为基础，结合牛奶收运问题的特点，建立了两个混合整数规划模型，第一个是以使用的车辆数最少为目标的牧场分配模型。另一个是以收运的总时间最短为目标的路径优化模型，主要通过节约里程算法求解。最后，这篇文章以一家乳制品企业为例，通过上述模型及算法成功实现了对该企业的牛奶收运网络的优化。

关键词 物流 车辆路径 牛奶收运 节约里程法

中图分类号：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.