汽车零部件循环取货路线模型及求解方法研究

陈 翔，段澄莹，乔 睿

（长安大学汽车学院，陕西西安 710064）

作者简介：陈 翔（1991－），男，长安大学汽车学院硕士研究生，载运工具运用工程专业。

段澄莹（1991－），女，长安大学汽车学院硕士研究生，交通运输规划与管理专业。

乔 睿（1990－），男，长安大学汽车学院硕士研究生，载运工具运用工程专业。

摘 要：以汽车零部件物流为研究对象，针对汽车零部件运输环节所采用的循环取货问题展开研究。在给出了实际取货问题抽象描述的基础上，考虑供应商及主机厂时间窗构建了汽车零部件循环取货VRPTW（vehicle routing problems with time windows）模型，并提出具体的蚁群算法对模型进行求解。最后以东风日产武汉主机厂实施循环取货为例对模型及算法进行验证，得到了满意的车辆巡回路线。

关键词：汽车零部件物流；循环取货；车辆巡回路线；蚁群算法

Abstract：The dissertation will take the auto parts logistics as foothold and focus on the problem of Milk－run which is adopt－ed by auto parts transportation．On the basic of abstract description of the practical problem，according to the time windows of the supplier and main engine plants，this paper establishes the vehicle routing problems with time windows of auto parts logistics．And the mathematical model is solved by ant colony algorithm．Finally，this dissertation takes the example of Dongfeng Nissan and verifies the model and algorithm．Therefore，a satisfying route of vehicle is obtained successfully．

Key words：auto parts logistics；Milk－run；route of vehicle；ant colony algorithm

1 引 言

截至去年，我国汽车产量已连续五年保持世界第一，汽车产业的飞速发展提供给国内汽车制造业前所未有的良好机遇，但也向汽车物流提出了严峻的挑战。据统计显示，欧美汽车制造企业的物流成本占销售额的比例为8％左右；日本汽车厂商这一比例最高仅5％；而在中国却在15％以上［1］。为改善汽车物流成本现状，愈来愈多企业与专家学者将目光转向汽车零部件物流中的运输环节，通过解决国内汽车物流最棘手的零部件运输问题以实现成本的显著减少。

循环取货（Milk－run）是一种源自于英国北部牧场为了解决零散牛奶运输问题而发明的一种运输方式。基于汽车零部件供应多而散的分布特点，这种模式逐渐被专家学者们借鉴并应用到供应商对主机厂的零部件的配送中来，通过对具体目标的建模与求解来获得取货车辆的最优巡回取货路线。国内外关于此领域研究中较有代表性的有：J．Solomon针对带时间窗约束的车辆路线问题，提出的优化算法成功解决带100个客户节点的VRP问题［2］；M．Jafari等人提出了一种鲁棒优化模型［3］；王磊提出了一种基于2－opt以及C－W节约算法的两阶段Milk－run路径模型［4］。

2 汽车零部件循环取货VRPTW模型

2．1 问题描述及模型假设

循环取货VRPTW问题可以表述为：巡回车辆从主机厂出发依次对多个供应商进行集货，要求对每一个供应商有且仅有一辆车对其进行服务并且所有车辆必须在供应商许可时间窗内完成对该供应商的集货任务。车辆必须在主机厂时间窗内完成集货任务并将零部件配送至主机厂。这是典型的带时间窗约束的车辆路径问题，即VRPTW。模型假设有如下规定：

（1）车辆型号与零部件均无差异；

（2）对各个供应商处的集货服务时间必须在供应商时间窗口内完成；

（3）对各个供应商的集货量不得超过巡回车辆的最大容载量；

（4）所有车辆由主机厂出发巡回，巡回结束最终回到主机厂；

（5）车辆出发时间与返回时间必须在主机厂时间窗口之内；

（6）每个供应商有且仅有一台车辆进行单次巡回；

（7）主机厂与各供应商的位置已知；

（8）巡回车辆的最大容载量已知；

（9）主机厂与各供应商的时间窗要求已知；

（10）供应商之间的距离已知；

（11）各供应商处集货量已知。

模型求解目标为总费用最短的行驶路径，由于车辆行驶速度与费用一致，所以该目标可以认为是求巡回总路线长度最短问题。

2．2 符号定义及说明

模型中的主要参数定义如下：n为汽车零部件供应商的个数；m为进行循环取货的巡回车辆数量；V＝｛i，j｜i，j＝0，1，2，．．．，n｝为主机厂与供应商集合（其中i＝0表示主机厂）；K＝｛1，2，．．．，m｝为巡回车辆集合；S为供应商的任意子集；S为集合S中所含供应商个数；qi为供应商i的集货量；Q为车辆的最大容载量。

模型中的变量定义如下：dij为供应商（主机厂）i至j的距离；tij为巡回车辆从i至j的行驶时间；ssi为车辆对供应商i服务的开始时间；sfi为车辆对供应商i服务的终止时间；si＝sfi－ssi为供应商i的服务时间；sli为供应商i的时间窗下限；fli为供应商i的时间窗上限。

决策变量说明：xijk为车辆巡回路径决策变量，若供应商i与j由车辆k服务为1否则为0；yki为车辆巡回服务决策变量，若供应商i由车辆k服务为1否则为0。

2．3 目标函数及约束条件

目标函数（1）表明模型以最短路径即车辆运输最小费用成本为目标；约束（2）为巡回车辆载货容量限制；约束（3）保证每辆巡回货车对每个供应商只访问一次；约束（4）保证巡回路径顺畅；约束（5）、（6）、（7）保证所有车辆从主机厂出发并最终返回主机厂；约束（8）为防子回路约束，保证整个巡回形成可行回路；约束（9）为同一巡回路线上相邻两个供应商取货并存的条件；约束（10）为供应商时间窗约束。约束（11）保证每个巡回都在主机厂的时间窗限制范围内进行。

3 模型求解方法

由于所构建模型属于VRPTW范畴，该问题属于NP－hard问题，使用精确算法很难在可接受的时间内求得全局最优解，故寻求启发式算法在可接受的时间内求得问题的满意解成为研究的重点［5］。

蚁群算法（Ant colony algorithm，AC）相对于其他算法而言，其已被证明在解决TSP、资源分配问题的经典优化问题时，有很好的效果，故选择使用蚁群算法作为解决循环取货问题的启发式算法支持。

3．1 算法主要符号定义及说明

算法参数：m为蚂蚁个数；α为信息启发式因子；β为期望启发式因子；ρ为信息素挥发系数；Q为信息素浓度常数；V＝｛i，j｜i，j＝0，1，…，n｝为节点集合。

算法变量：ηij为期望启发函数；dij为节点i与j间的距离；τij为边弧 ，（i ）j的轨迹信息素浓度；（）t为时刻t蚂蚁k在边弧 ，（i ）j上留下的单位长度轨迹信息素数量；（）t为时刻t蚂蚁k的转移概率；tabuk为记录蚂蚁k路径的禁忌表。

3．2 求解算法模型及说明

3．2．1 蚂蚁转移规则

在蚁群算法中，蚂蚁主要是根据路线上的信息素浓度来决定其转移的方向，在进行路径搜索的过程中，蚂蚁通过路径上的启发式信息以及信息素的浓度来计算其转移下一节点的概率（）t。本文采用自适应随机比率作为蚁群选择路线访问的规则，即蚂蚁k按照如下规则选择下一个访问节点 ，（r ）u［6］：

其中，q＜q0为控制算法多样性判别，q取值范围为 ［0 ，1］内的随机数，q0⊂ ［0，1 ］为原定常数；Jk（）i表示待选节点集合，即Jk（）i＝｛V－tabu｝k。α为信息启发式因子，表示每次迭代蚂蚁在路线上留下轨迹的相对重要性，反映了蚂蚁在运动过程中所积累信息素在整体运动时所起的作用，其值越大，则蚂蚁越倾向于选择其他蚂蚁经过的路线，蚂蚁间的协作性越强；β为期望启发式因子，反映了蚂蚁对启发式信息的重视程度，其值越大，蚂蚁则越容易陷入局部最优的状况。ηij（）t为启发式函数，由于设计目标考虑车辆巡回路线最短，故其表达如下：

对于蚂蚁k而言，dij越小则ηij（）t越大，从而（）t的值就越大。

3．2．2 信息素更新规则

由于信息素不断增多的过程中会对原来留下的信息素进行覆盖淹没，同时路径上的信息素随着时间再不断的挥发稀释。故需要在每一次迭代中对蚂蚁留下的信息素进行更新。由此，t＝n时刻在路径 ，（i ）j上的信息素按照如下规则进行更新：

式中，ρ为信息素挥发系数，则1－ρ表示信息素的残留因子，为了防止信息素的无限积累，通常ρ的取值范围为ρ⊂［0，1］；Δτij（t）指单次迭代中所有蚂蚁在所进行的搜索中留在其行进线路，（i ）j上的信息素增加量，初始时刻，τij（）0＝0；（）t则表示第k只蚂蚁进行单次迭代搜索中留在其行进线路 ，（i ）j上的信息量。对于（）t，按照Ant－Cycle模型规则进行取值［7］：

3．2．3 算法参数确定

在蚁群算法中，蚂蚁数量m、信息启发式因子α、期望启发式因子β以及信息素挥发系数ρ都是直接同算法的收敛性相关的重要参数，它们的取值对于算法在求解问题过程中的效率对于蚁群的收敛速度以及全局搜索能力都起着决定性的作用。

国内外众多学者对于这些参数的选择与设计都进行了相应的研究，基于本文设计研究问题的规模，同时考虑采用的是Ant－Cycle模型，引用对于eil51．TSP算例研究的参数选择实验结果，当求解问题的规模与蚂蚁数量成1．5∶1；α＝1时所得到的最优解表现最佳且差值最小；β＝3时求解效果最好；ρ＝0．5为最佳设置算法收敛速度和收敛性都较好［8］。

图1 蚁群算法求解步骤

3．3 算法步骤

根据蚁群算法的一般求解过程，图1给出了应用蚁群算法求解问题的流程步骤，具体而言，将其划分为以下13个步骤进行求解：

（1）初始化参数；（2）将顶点j放入禁忌表，当迭代次小于最大迭代次数，继续下一次迭代；（4）更新循环次数，Nc＝Nc＋1；（5）放置蚂蚁；（6）对于蚂蚁k，根据转移概率、车辆容量以及时间窗约束选择下一个城市j；（7）将蚂蚁k从i移动至j，并将j置于当前蚂蚁k的禁忌表Tabuk中；（8）当所有顶点都放入Tabuk中后，计算目标函数值，并将当前最优解 Shortest＿Route放入禁忌表中；（9）for k＝1∶m，开始更新信息素；（10）对各边，（i ）j计算Δτij＝Δτij＋，增加单位信息素；（11）对各边 ，（i ）j计算τij＝1－（ ）ρ·τij＋，更新轨迹信息素浓度；（12）若N≤NC＿max，返回（3）；（13）输出当前最优解。

4 MATLAB实例求解

在该部分，将应用第1节中所构建的循环取货VRPTW模型及第2节中所设计的蚁群算法结合实际案例运用MATLAB编程进行求解。本次案例来源于东风日产武汉生产基地2004年实施循环取货的信息，其中包括1个主机厂及24个分布于主机厂8km以外的零部件供应商，30台载货量为200单位的零部件送货车辆，供应商坐标、集货量及时间窗要求均有具体数据。根据参数设置要求，结合本案例实际情况，运算参数设置如表1所示：

表1 运算参数设置

运行5次，得到循环取货的巡回车辆路线结果如下所示：

图2 第一次运算结果

图4 第三次运算结果

图3 第二次运算结果

图5 第四次运算结果

从5次运算结果来看，在满足载运车辆的容量限制以及零部件供应商及主机厂的时间窗条件下，东风日产武汉主机厂在零部件配送实施循环取货时需要进行4个巡回路线，现将运算结果整理如表2所示：

表2 运算结果分析

通过表2的分析可以看出，所设计的模型及求解方法顺利完成循环巡回路线的安排并取得了较好的结果。其中，最优路线为表中第5次运算得到的结果（图6），其代表的最佳巡回路线总长为386．2684km。5次运算的平均偏差为3．2650％，最差也仅仅在4．9607％，在实际操作所允许的偏差范围内。

图6 第五次运算结果

5 总 结

本文研究了带时间窗的汽车零部件循环取货车辆巡回路线问题。基于车辆运输成本最小的优化目标，构建了该问题的VRPTW模型。模型以一定的服务对象硬时间窗及车辆固定容量的条件下，最小化运输费用。为了求解提出的循环取货车辆巡回路线问题，构建了一个基于蚁群算法的启发式算法。

采用MATLAB进行实例验证，通过实验结果可以看出所构建模型能够成功的解决汽车零部件循环取货车辆路线的安排，同时所提出的算法在求解模型的过程中表现出了令人满意的准确性和稳定性。在今后的研究过程中，将会更多的考虑拓展模型的适用范围，通过在模型约束及目标函数上的深入研究，使得模型能够更加符合实际情况。同时对于大规模案例的研究也有待在后续工作中不断完善。

参考文献

［1］ 计志英，陆海平．我国汽车物流业的发展现状、问题及调整思路［J］．上海汽车，2005（11）：14－17．

［2］ Desrochers，M，Desrosiers，J，Solomon，M．A new optimizationalgorithm for the vehicle routing problem with time windows［J］．Operations Research，1992（40）：342－367．

［3］ M．Jafari－Eskandari，S．J．Sadjadi，M．S．Jabalameli．etc．A robust optimization approach for the Milk Run problem （An auto industry Supply Chain Case Study）．［D］．Tehran，Iran：Iran University of Science and Technology：1076－1081．

［4］ 王磊．引入TPL的汽车制造企业物流优化研究［D］．西安：长安大学，2005．

［5］ 刘云忠．车辆路径问题的模型及算法研究综述［J］．管理工程学，2005：116－138．

［6］ 秦玲．蚁群算法的改进与应用［D］．扬州：扬州大学硕士学位论文，2011．

［7］ Dorigo．M．，Gambardella．M．．Ant colonies for traveling salesman problem［J］．Bio Syst－em．1997：49－67．

［8］ 马良．蚂蚁算法在组合优化中的应用［J］．管理科学学报，2010（4）：88－102．