魏 宇，陈希琼，张琳琳
作者简介：魏 宇（1990－），女，长安大学汽车学院硕士研究生，载运工具运用工程。
陈希琼（1990－），女，长安大学汽车学院博士研究生，载运工具运用工程。
张琳琳（1990－），女，长安大学汽车学院硕士研究生，交通运输规划与管理。
摘 要：在设计循环取货路径时，针对我国汽车零部件物流运输过程中的成本构成特点，考虑使用不同等级公路时的燃油费和道路使用费，并基于由该两种背反的费用构成的运输成本进行不同等级公路的路径选择，建立带混合时间窗的循环取货模型。用LINGO验证模型的正确性，设计改进的节约算法，采用C语言编写程序求解模型。最后，用一个零部件物流的算例对所提出的模型进行验证，同时证明改进的节约算法可有效求解此类问题。
关键词：零部件物流；车辆路径优化；循环取货；C－W算法；混合时间窗
Abstract：On designing the milk－run routing，we considered the fuel charges and roads using charges for the characteristics of the cost construction in the process of auto parts transportation in China．This paper established a milk－run model with hybrid time windows，in which we choose different level’s highway routes based on the transportation cost consisting of the two paradoxical fees．To solve this model，firstly，the model’s validity was indicated with LINGO．Then an improved C－W algorithm was designed and programmed with C language．Finally，a numerical example of parts logistics was used to evalu－ate the proposed model，which also proved the improved C－W algorithm can solve this kind of problem efficiently．
Key words：Parts logistics；Vehicle routing optimizing；Milk－run routing；C－W algorithm；Hybrid time windows
1 引言
随着物流成本压力的上升，汽车制造企业力求在各个环节降低物流成本，其中零部件供应物流是最复杂且成本较高的环节。目前，国内越来越多的汽车企业采取国外先进的供应方式——循环取货（Milk Run）方式来代替传统的供应商直接送货方式。其基本运作模式是汽车从配送中心出发，按照预先设定好的路线依次到零部件供应商处取货，同时返还空料箱，最后返回出发地。不同于供应商直接送货，该模式能有效降低物流成本，提高零部件供应的准时性，降低库存成本，但该模式对取货时间、货物量、取货路线、信息管理等方面要求更高。
国外较早开展了对循环取货方式的研究并得以应用。例如丰田公司为实现JIT生产，采用了Milk Run供货模式［1］。Harrison（2001）分析了戴姆勒－克莱斯勒、福特－沃尔沃等汽车公司的供应物流，提出了六种主要的运作模式，其中就包含了整车厂自身从供应商处集货模式和第三方物流为供应商承担运输任务模式［2］。国内方面，徐秋华在2003年撰文介绍了上海通用汽车公司采用Milk Run方式的优点、流程及路线的设计等［3］。汪金莲（2009）基于循环物流的特征，提出并建立循环取货的路径规划模型，定性分析、简化各约束条件，转化为CFR（Common frequency routing problem）问题［4］。
在有关此类问题的大部分文献研究中［5－7］，作者建立的数学模型并未考虑道路使用费、燃油费，然而在国内这两种费用已经成为不可忽视的物流成本。公路等级不同，道路使用费、燃油费均有所不同。高速公路使用费高但路程短、路况好，因而燃油费相对较低，而普通公路正好相反。如何在确定循环取货路线的基础上考虑二者之间的平衡问题是本文研究的重点。
2 问题描述
循环取货顺利实施最关键的环节是线路的设计，该问题属于车辆路径问题（Vehicle Routing Problem，VRP）：在一个系统中存在若干供应商（顾客）和配送中心，中心将合理安排车辆和时间，按照一定路线服务供应商，从而达到成本最低、配送时间最短等目标。原理如图1所示。
图1 VRP示意图
本文研究的循环取货路径优化问题属于单车场，单一车型带混合时间窗约束的非满载的车辆路径问题。该模型基于以下假设条件：
（1）零部件供应商供货量已知；
（2）配送中心和供应商的地理位置已知；
（3）车辆为同一车型且容积已知；
（4）每个供应商只被访问一次，每条循环取货路径上的任务由一辆车完成；
（5）车辆从配送中心出发，取货后再返回；
3 数学模型的建立
3．1 符号说明
为建立循环取货车辆路径的数学模型，现定义数学符号：
（1）集合定义
I＝｛i｜i＝1，2，3．．．n｝，i＝0，表示配送中心，i＞0时表示供应商；
K＝｛k｜k＝1，2，3．．．m｝，K表示m条循环取货路径的集合，同时m表示取货车辆的集合；
（2）已知参数
dij：供应商i和j之间的高速公路里程（km）；
V：车辆的最大容积（m3）；
cij：车辆从供应商i到j的运输成本（元）；
vi：车辆在供应商i处的取货体积（m3）；
gi：车辆在供应商i处的取货重量（t）；
G：车辆的空载重量（t）；
e：燃油单价（元／L）；
Q’：载货汽车基本燃油消耗量（升／100km）；
Q’’：载货汽车质量变化附加燃油消耗量（升／t·100km）；
ε：高速公路使用费费率（元／km）；
δ：普通公路使用费费率（元／km）；
H：道路修正系数；
vv1：高速公路平均行驶速度（km／h）；
vv2：普通公路平均行驶速度（km／h）；
θij：i和j之间普通公路与高速公路的转换系数；
si：车辆到达供应商i时的时刻；
tij：车辆从供应商i到j的行驶时间（h）；
Ti：车辆在供应商i处的装卸货物时间（h）；
ETi：供应商i处允许最早接受服务的时刻；
LTi：供应商i处允许最晚接受服务的时刻；
Ni：供应商i处拒绝接受服务的时刻；
Pi：到达供应商i时所产生的的惩罚成本；
α：车辆早于ETi到达i处产生的惩罚成本的系数；
β：车辆晚于LTi到达i处产生的惩罚成本的系数；
M：车辆晚于Ni到达i处产生的惩罚成本的系数。
（4）时间变量与取货车辆惩罚费用变量的关系
本文所讨论的时间约束为混合时间窗约束，时间与惩罚费用的函数［8］如图2所示：
如果配送车辆在时间窗［ETi，LTi］内到达，则不需要付出惩罚成本；如果配送车辆到达供应商i的时间早于ETi或晚于LTi，则配送车辆要付出一定时间的惩罚成本pi；当车辆晚于Ni到达供应商时将付出极大的惩罚成本，而在实际中是不允许的。当求解模型时，M用一个非常大的正数代替。时间惩罚成本为：
pi＝αmax（ETi－si，0）＋βmax（si－LTi，0）＋Mmax（si－Ni，0）（1）
（5）基于燃油费与道路使用费公路等级的选择
传统模型中单位运输费用为一固定值，在本文中，运输成本由道路使用费和燃油费组成，借鉴文献［9］中对燃油费的研究结论，在满足本文的假设条件下加以改进，则供应商之间的运输成本为：
本文将公路按高速公路和普通公路划分。式（2）中
表示高速公路情况下对应的燃油消耗量
表示普通公路情况下的对应值。
3．2 数学模型
根据上述已知参数、决策变量、惩罚费用函数和运输成本函数建立以下数学模型：
目标函数（3）表示总物流费用最小；约束条件（4）表示车辆在路径k上的总取货体积不超过车辆的最大容积；式（5）表示每个供应商只能由一辆车进行取货；式（6）和（7）表示每辆车只能访问供应商一次；式（8）和（9）保证车辆从配送中心出发，取货后又回到配送中心；式（10）表示车辆到达供应商的时刻；式（11）表示车辆的时间惩罚成本；式（12）表示车辆的运输成本；式（13）表示车辆只能选择高速公路或普通公路；式（14）表示0－1变量约束。
3．3 模型的验证
将建立的数学模型用LINGO11．0进行验证，在CPU＠2．30GHz，779MHz，1．94GB内存的计算机上运行，结果如图3（a）、（b）所示，该问题属于整数非线性规划问题，程序运行18分21秒后得到全局最优解。
4 算法设计
4．1 算法分析
如前文所述，循环取货路径问题属于经典的车辆路径问题（VRP），求解VRP的算法分为精确算法和启发式算法。精确算法一般引入了严格的数学方法，因此精确度较高，计算量将成指数性增长［10］，适用于小规模问题。启发式算法［11］是一个基于直观或经验构造的算法，在可接受的花费下给出待解决和最优化问题的每一个实例的可行解。本文旨在解决大规模循环取货路径的优化，因此本文采用启发式算法。
图3 运行结果
启发式算法的种类很多，其中由Clarke和Wright提出的节约法（C－W算法），其特点是最大可能的提高车辆满载率的同时缩短配送里程，比较满足案例的要求，因此本文在求解模型时采用节约法。节约法的主要思想是从节点0出发，到节点1和2取货，任意两点距离由d表示。一种方案是直接取货然后返回，另一种是按某顺序依次到节点取货然后返回。两种方案的行驶里程之差即“节约里程”用ds表示，则
ds＝d01＋d02－d12 （15）
4．2 改进的节约法
本文在模型中加入了公路等级选择约束和时间窗约束，因此针对原算法加以改进。改进的节约法步骤：
步骤一：根据供应商的坐标计算ds（i，j），令
DS＝｛ds（i，j）｜ds（i，j）＞0｝，并将ds（i，j）按降序排列；
步骤二：确定纳入循环取货路线的第一段路程；
步骤三：若DS中所有元素为0，则连接线路起点和终点，输出路线和总费用。否则按顺序考察ds（i，j）对应的路段，若满足下列插入条件之一则转至步骤四，否则转至步骤六：
（1）点i和点j均不在已构路段上；
（2）点i和点j只有其中一点在已构路段的端点；
步骤四：考察点i或点j连入路段后总货物的体积，若小于或等于货车的额定容积，则转至步骤五，否则转至步骤三；
步骤五：计算车辆的累计货物量，比较高速公路和普通公路的费用情况，得出cij和tij，然后计算新路线到达j的时刻sj，计算惩罚成本pj；
步骤六：令路段非端点的节点ds（i，j）为0，转至步骤三。
5 算例分析
5．1 算例数据分析
A公司是国内某著名的汽车制造商，由于零部件供应物流成本随着油价的上升而逐渐增加，同时零部件的运输满载率不到80％，资源没有得到充分利用，因此公司拟引进循环取货方式。主要数据如下所示：
（1）供应商信息
供应商地理坐标，供货量、货物容积，可接受的时间窗、装卸时间，见表1：
表1 供应商数据表
（2）车辆信息、公路信息以及不同等级公路下的油耗信息，如表2、3所示，其中道路修正系数H由路段的级别确定，以高速公路为基准。
表2 模型参数值
表3 油耗值
需要的车辆数为m，式（16）中［］表示取不大于括号内数值的最大整数，∂是对装车复杂性程度的评估系数，这里取值0．9。
5．2 计算结果及分析
根据以上数据，采用上述算法，用C语言进行编程，程序在CPU＠2．30GHz，779MHz， 1．94GB内存的计算机上运行，7．4秒后显示运行结果如表4所示，优化路径示意图如图4所示。
表4 循环取货路径优化结果
图4 优化路径示意图
未实施循环取货前，由15个供应商采用3吨位的卡车直接送货至配送中心，然后空车返回供应商处的物流费用为：
如果没有进行道路等级的选择，车辆全部走高速公路，则物流费用为：3047．46元；车辆全部走普通公路，物流费用为3426．9元。四种取货方式的比较结果如表5所示：
表5 对比结果
由表可知，循环取货模式能够有效的降低物流成本，同时由于设计了公路等级的选择功能，在满足时间窗的前提下尽可能的降低道路使用费和油费，从而降低整条线路的物流费用。表5的数据显示带选择性的循环取货的物流成本是原来直接送货的71．23％，降低了28．77％。本案例只选取了15个供应商，而一般汽车企业的零部件供应商都有几十到上百，因此从整体看，有了公路选择功能的循环取货仍然能有效的降低成本。同时，和公司未实施循环取货前不到80％的满载率相比，三条线路中最低满载率已经达到90％，资源利用率明显提高。可见该算法能够在保持较高的满载率的前提下有效降低物流成本。
6 结语
本文在循环取货路径规划的基础上考虑了油费和道路使用费的平衡，建立了带混合时间窗的数学模型，设计了改进的节约算法求解模型。结果显示，采用循环取货模式可以有效降低物流成本，提高满载率。所以将该方法引入企业的零部件供应中是可行的，但模型中两点之间只模糊提供了两种公路的选择，而在实际中路段的复杂性，各地道路使用费的不同都可能影响最后的优化结果。进一步的研究方向是模型求解的优化。
［1］ Chopra．S，Meindl．P．Supplier Chain Management－Strategies，Planning and Operation［M］．北京：清华大学出版社，2001．
［2］ Harrison．A．Perestroika in automotive inbound［J］．Manufacturing Engineer，2001，80（6）：247－251．
［3］ 徐秋华．Milk－run循环取货方式在上海通用汽车的实践和应用［J］．汽车与配件，2003：21－24．
［4］ 汪金莲．汽车制造厂零部件供应物流循环取货运输路线规划和优化算法的研究［D］．上海：上海交通大学，2009．
［5］ 张文华．基于节约里程法的物流配送路线优化［J］．物流工程与管理，2012，34（3）：143－146．
［6］ 王晓翠．基于供应链的汽车零部件供应物流研究［D］．武汉：武汉理工大学，2012．
［7］ 汪安静．汽车零部件循环取货供应物流及其路径优化研究［D］．芜湖：安徽工程大学，2010．
［8］ 魏静．基于VMI的汽车零部件供应物流循环取货研究［D］．北京：北京交通大学，2012．
［9］ 胡鹤严．基于成本的配送路线优化模型与算法研究［D］．吉林：吉林大学，2012．
［10］Kennedy J，Eberhart R C．Particle Swarm Optimization［C］．International Conference on Neural Networks，1995：42－48．
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
