基于3PL的汽车零部件循环取货路径研究

吴瑶

摘要： 对汽车零部件入厂物流循环取货特点分析的基础上，建立了有硬时间窗和容量约束的车辆路径优化模型，并采用改进节约算法对该问题进行求解。通过算例验证，算法能获得满意解，且简明、操作性强。

关键词： 零部件入厂物流；循环取货；改进节约算法

中图分类号：U468 文献标识码：A 文章编号：1006-4311（2014）01-0023-02

0 引言

循环取货（milk-run）模式作为汽车制造企业零部件集货入厂的主要方式，它通常是由第三方物流企业（TPL）根据汽车制造商的生产计划，按事先优化好的路线到指定的多个供应商处取货，然后返回制造厂或区域分拨物流中心（RDC）。这种模式适合汽车零部件多品种、短周期、小批量、多频次、准时性供应的特点，克服了供货批量与频次之间的矛盾。与传统物料供应相比，提高了物料供应的敏捷性和柔韧性。在milk-run中，运输效率取决于车辆派遣和取货的顺序，属于车辆路线问题（VRP）[1]。国外已经把VRP的研究成果应用于milk-run中，国内以上海通用为代表的汽车企业也尝试使用VRP解决milk-run中车辆路线安排[2]。本文针对milk-run模式建立了时间窗和车辆能力约束的VRP模型，并采用改进节约算法进行优化求解。

1 模型建立

在零部件供应商和RDC构成的物流网络中，C{i|1，2，…，n}表示供货点集合，0表示RDC，网络中的所有节点用N=C∪{0}表示。cij为网络中弧（i，j）的权重，表示网络节点间的行驶时间，i，j∈N且i≠j。可支持RDC零部件集货的规格相同容量为Q的车辆m辆，集合为K{k|1，2，…，m}，启用的车辆均从RDC出发，在与供应点约定的硬时间窗[ei，li]范围内到达取货路径上的每个供应点，取货完成后返回RDC。在时间点ei之前，提前到达供应点的取货车辆，因待交付的零部件可能尚未加工完成而无法装载，等待会导致机会损失，因此车辆不可提前到达取货点。在时间点li之后延迟到达的车辆，因错过供应点的装载服务时间，甚至可能会影响汽车制造企业的正常装配计划，因此车辆不可延迟到达供货点。供应点i的单次供货数量为qi（qi？燮Q），装货时间为si，同一供货点只能有一辆车前往取货，车辆到达供货点的时间为τi。在满足车辆能力约束和取货时间窗约束的情况下，建立以所有车辆取货完成总时间最短为目标的VRPTW模型。模型涉及的决策变量xijk表示为

目标函数（1）为所有供货点取货完成车辆总时间最小；约束（2）表示启动车辆数量不超过车辆总数；约束（3）表示从RDC出发的车辆在完成取货任务后必须返回RDC；约束（3）表示每个取货点均有一辆车前往取货；约束（4）为车辆路径连续条件，即到达某供货点的车辆数等于离开该点的车辆数；约束（5）为车辆容量限制，即车辆集货量不超过车辆容量；约束（6）为消除有子回路的路径；约束（7）为车辆到达供应点的时间表达式；约束（8）为车辆到达供应点的时间窗约束；约束（9）、（10）为变量的整数性及非负性限制。

2 改进节约算法

C-W节约算法[3]是一种常用的配送规划近似算法，由Clark和Wright于1964年提出。其基本思想是在为每个客户安排一辆车直接运输的基础上，依据运输距离减小幅度最大的原则，依次将运输中的两个回路合并为一个回路。当车辆达到容量限制后进行下一辆车的优化，最终使所有客户的需求全部满足。传统的节约算法仅考虑运输距离，不考虑客户时间窗和调用车辆数量。

2.1 节约值的计算 此处节约值为运输距离的节约值。配送中心“0”与各供应点i∈C直接相连，构成n条“0→i→0”初始路线，第i条线路的运输费用为Ci=c0i+ci0。当第i，j两条路线合并，即由同一辆车按路线“0→i→j→0”为其服务时，成本为Cij=c0i+cij+cj0，节约值为s（i，j）=ci0+c0j-cij。显然，合并优先级需按节约值从大到小依次排列。

2.3 改进节约算法

Step1：计算供应点对连接后的节约值s（i，j），并把节约值s（i，j）按从大到小排列，构成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：选择集合Sdescend中的第一个元素s1（i，j），检查其对应连接边（i，j）端点i，j是否在初始化路径上，若是，则转Step5，否则转Step3。

Step3：检查点i，j，是否其中一个在已构成的路径上且与RDC相连，另一个在初始化路径上，若是，则转Step5，否则转Step4。

Step4：检查点i，j，是否分别在不同的已构成路径上，且均与RDC相连。若是，则转Step5，否则转Step7。

Step5：若连接点i，j，把点i，j原所在的不同路径合并成一条路径，合并后的路径总取货量q■？燮Q，则转Step6，否则转Step7。

Step7：Sdescend=Sdescend＼s1（i，j），检查Sdescend若为空，则算法结束，否则转Step2。

3 算例分析

负责某汽车制造商入厂物流的第三方物流企业，现已知拥有统一容量为20单位的车辆若干辆，车辆在各供应点的装载时间为0.5，车辆的平均行驶速度为45，承担汽车零部件供应任务的区域供应商位置坐标、供货数量及取货约定时间窗如表1所示。

采用本文所提的改进节约算法，求得最优实验结果如表2所示。

从计算结果可以看出，算法运行结果满足所有约束条件，可作为入厂物流循环取货路径安排的依据，具有一定的实用价值。

4 结论

本文以汽车零部件入厂物流为研究对象，分析了零部件循环取货的特点，建立了基于硬时间窗和车辆容量约束的数学模型，构建了改进节约算法对该问题进行求解，最后通过算例验证了算法的可行性和有效性，为企业规划循环取货车辆路径提供了参考。

参考文献：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]叶雷.循环取料在上海通用汽车零部件入厂物流中的应用研究[D].上海：复旦大学，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]张建勇，郭耀煌，李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学报，2004，6（3）：281-284.endprint

摘要： 对汽车零部件入厂物流循环取货特点分析的基础上，建立了有硬时间窗和容量约束的车辆路径优化模型，并采用改进节约算法对该问题进行求解。通过算例验证，算法能获得满意解，且简明、操作性强。

关键词： 零部件入厂物流；循环取货；改进节约算法

中图分类号：U468 文献标识码：A 文章编号：1006-4311（2014）01-0023-02

0 引言

循环取货（milk-run）模式作为汽车制造企业零部件集货入厂的主要方式，它通常是由第三方物流企业（TPL）根据汽车制造商的生产计划，按事先优化好的路线到指定的多个供应商处取货，然后返回制造厂或区域分拨物流中心（RDC）。这种模式适合汽车零部件多品种、短周期、小批量、多频次、准时性供应的特点，克服了供货批量与频次之间的矛盾。与传统物料供应相比，提高了物料供应的敏捷性和柔韧性。在milk-run中，运输效率取决于车辆派遣和取货的顺序，属于车辆路线问题（VRP）[1]。国外已经把VRP的研究成果应用于milk-run中，国内以上海通用为代表的汽车企业也尝试使用VRP解决milk-run中车辆路线安排[2]。本文针对milk-run模式建立了时间窗和车辆能力约束的VRP模型，并采用改进节约算法进行优化求解。

1 模型建立

在零部件供应商和RDC构成的物流网络中，C{i|1，2，…，n}表示供货点集合，0表示RDC，网络中的所有节点用N=C∪{0}表示。cij为网络中弧（i，j）的权重，表示网络节点间的行驶时间，i，j∈N且i≠j。可支持RDC零部件集货的规格相同容量为Q的车辆m辆，集合为K{k|1，2，…，m}，启用的车辆均从RDC出发，在与供应点约定的硬时间窗[ei，li]范围内到达取货路径上的每个供应点，取货完成后返回RDC。在时间点ei之前，提前到达供应点的取货车辆，因待交付的零部件可能尚未加工完成而无法装载，等待会导致机会损失，因此车辆不可提前到达取货点。在时间点li之后延迟到达的车辆，因错过供应点的装载服务时间，甚至可能会影响汽车制造企业的正常装配计划，因此车辆不可延迟到达供货点。供应点i的单次供货数量为qi（qi？燮Q），装货时间为si，同一供货点只能有一辆车前往取货，车辆到达供货点的时间为τi。在满足车辆能力约束和取货时间窗约束的情况下，建立以所有车辆取货完成总时间最短为目标的VRPTW模型。模型涉及的决策变量xijk表示为

目标函数（1）为所有供货点取货完成车辆总时间最小；约束（2）表示启动车辆数量不超过车辆总数；约束（3）表示从RDC出发的车辆在完成取货任务后必须返回RDC；约束（3）表示每个取货点均有一辆车前往取货；约束（4）为车辆路径连续条件，即到达某供货点的车辆数等于离开该点的车辆数；约束（5）为车辆容量限制，即车辆集货量不超过车辆容量；约束（6）为消除有子回路的路径；约束（7）为车辆到达供应点的时间表达式；约束（8）为车辆到达供应点的时间窗约束；约束（9）、（10）为变量的整数性及非负性限制。

2 改进节约算法

C-W节约算法[3]是一种常用的配送规划近似算法，由Clark和Wright于1964年提出。其基本思想是在为每个客户安排一辆车直接运输的基础上，依据运输距离减小幅度最大的原则，依次将运输中的两个回路合并为一个回路。当车辆达到容量限制后进行下一辆车的优化，最终使所有客户的需求全部满足。传统的节约算法仅考虑运输距离，不考虑客户时间窗和调用车辆数量。

2.1 节约值的计算 此处节约值为运输距离的节约值。配送中心“0”与各供应点i∈C直接相连，构成n条“0→i→0”初始路线，第i条线路的运输费用为Ci=c0i+ci0。当第i，j两条路线合并，即由同一辆车按路线“0→i→j→0”为其服务时，成本为Cij=c0i+cij+cj0，节约值为s（i，j）=ci0+c0j-cij。显然，合并优先级需按节约值从大到小依次排列。

2.3 改进节约算法

Step1：计算供应点对连接后的节约值s（i，j），并把节约值s（i，j）按从大到小排列，构成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：选择集合Sdescend中的第一个元素s1（i，j），检查其对应连接边（i，j）端点i，j是否在初始化路径上，若是，则转Step5，否则转Step3。

Step3：检查点i，j，是否其中一个在已构成的路径上且与RDC相连，另一个在初始化路径上，若是，则转Step5，否则转Step4。

Step4：检查点i，j，是否分别在不同的已构成路径上，且均与RDC相连。若是，则转Step5，否则转Step7。

Step5：若连接点i，j，把点i，j原所在的不同路径合并成一条路径，合并后的路径总取货量q■？燮Q，则转Step6，否则转Step7。

Step7：Sdescend=Sdescend＼s1（i，j），检查Sdescend若为空，则算法结束，否则转Step2。

3 算例分析

负责某汽车制造商入厂物流的第三方物流企业，现已知拥有统一容量为20单位的车辆若干辆，车辆在各供应点的装载时间为0.5，车辆的平均行驶速度为45，承担汽车零部件供应任务的区域供应商位置坐标、供货数量及取货约定时间窗如表1所示。

采用本文所提的改进节约算法，求得最优实验结果如表2所示。

从计算结果可以看出，算法运行结果满足所有约束条件，可作为入厂物流循环取货路径安排的依据，具有一定的实用价值。

4 结论

本文以汽车零部件入厂物流为研究对象，分析了零部件循环取货的特点，建立了基于硬时间窗和车辆容量约束的数学模型，构建了改进节约算法对该问题进行求解，最后通过算例验证了算法的可行性和有效性，为企业规划循环取货车辆路径提供了参考。

参考文献：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]叶雷.循环取料在上海通用汽车零部件入厂物流中的应用研究[D].上海：复旦大学，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]张建勇，郭耀煌，李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学报，2004，6（3）：281-284.endprint

摘要： 对汽车零部件入厂物流循环取货特点分析的基础上，建立了有硬时间窗和容量约束的车辆路径优化模型，并采用改进节约算法对该问题进行求解。通过算例验证，算法能获得满意解，且简明、操作性强。

关键词： 零部件入厂物流；循环取货；改进节约算法

中图分类号：U468 文献标识码：A 文章编号：1006-4311（2014）01-0023-02

0 引言

循环取货（milk-run）模式作为汽车制造企业零部件集货入厂的主要方式，它通常是由第三方物流企业（TPL）根据汽车制造商的生产计划，按事先优化好的路线到指定的多个供应商处取货，然后返回制造厂或区域分拨物流中心（RDC）。这种模式适合汽车零部件多品种、短周期、小批量、多频次、准时性供应的特点，克服了供货批量与频次之间的矛盾。与传统物料供应相比，提高了物料供应的敏捷性和柔韧性。在milk-run中，运输效率取决于车辆派遣和取货的顺序，属于车辆路线问题（VRP）[1]。国外已经把VRP的研究成果应用于milk-run中，国内以上海通用为代表的汽车企业也尝试使用VRP解决milk-run中车辆路线安排[2]。本文针对milk-run模式建立了时间窗和车辆能力约束的VRP模型，并采用改进节约算法进行优化求解。

1 模型建立

在零部件供应商和RDC构成的物流网络中，C{i|1，2，…，n}表示供货点集合，0表示RDC，网络中的所有节点用N=C∪{0}表示。cij为网络中弧（i，j）的权重，表示网络节点间的行驶时间，i，j∈N且i≠j。可支持RDC零部件集货的规格相同容量为Q的车辆m辆，集合为K{k|1，2，…，m}，启用的车辆均从RDC出发，在与供应点约定的硬时间窗[ei，li]范围内到达取货路径上的每个供应点，取货完成后返回RDC。在时间点ei之前，提前到达供应点的取货车辆，因待交付的零部件可能尚未加工完成而无法装载，等待会导致机会损失，因此车辆不可提前到达取货点。在时间点li之后延迟到达的车辆，因错过供应点的装载服务时间，甚至可能会影响汽车制造企业的正常装配计划，因此车辆不可延迟到达供货点。供应点i的单次供货数量为qi（qi？燮Q），装货时间为si，同一供货点只能有一辆车前往取货，车辆到达供货点的时间为τi。在满足车辆能力约束和取货时间窗约束的情况下，建立以所有车辆取货完成总时间最短为目标的VRPTW模型。模型涉及的决策变量xijk表示为

目标函数（1）为所有供货点取货完成车辆总时间最小；约束（2）表示启动车辆数量不超过车辆总数；约束（3）表示从RDC出发的车辆在完成取货任务后必须返回RDC；约束（3）表示每个取货点均有一辆车前往取货；约束（4）为车辆路径连续条件，即到达某供货点的车辆数等于离开该点的车辆数；约束（5）为车辆容量限制，即车辆集货量不超过车辆容量；约束（6）为消除有子回路的路径；约束（7）为车辆到达供应点的时间表达式；约束（8）为车辆到达供应点的时间窗约束；约束（9）、（10）为变量的整数性及非负性限制。

2 改进节约算法

C-W节约算法[3]是一种常用的配送规划近似算法，由Clark和Wright于1964年提出。其基本思想是在为每个客户安排一辆车直接运输的基础上，依据运输距离减小幅度最大的原则，依次将运输中的两个回路合并为一个回路。当车辆达到容量限制后进行下一辆车的优化，最终使所有客户的需求全部满足。传统的节约算法仅考虑运输距离，不考虑客户时间窗和调用车辆数量。

2.1 节约值的计算 此处节约值为运输距离的节约值。配送中心“0”与各供应点i∈C直接相连，构成n条“0→i→0”初始路线，第i条线路的运输费用为Ci=c0i+ci0。当第i，j两条路线合并，即由同一辆车按路线“0→i→j→0”为其服务时，成本为Cij=c0i+cij+cj0，节约值为s（i，j）=ci0+c0j-cij。显然，合并优先级需按节约值从大到小依次排列。

2.3 改进节约算法

Step1：计算供应点对连接后的节约值s（i，j），并把节约值s（i，j）按从大到小排列，构成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：选择集合Sdescend中的第一个元素s1（i，j），检查其对应连接边（i，j）端点i，j是否在初始化路径上，若是，则转Step5，否则转Step3。

Step3：检查点i，j，是否其中一个在已构成的路径上且与RDC相连，另一个在初始化路径上，若是，则转Step5，否则转Step4。

Step4：检查点i，j，是否分别在不同的已构成路径上，且均与RDC相连。若是，则转Step5，否则转Step7。

Step5：若连接点i，j，把点i，j原所在的不同路径合并成一条路径，合并后的路径总取货量q■？燮Q，则转Step6，否则转Step7。

Step7：Sdescend=Sdescend＼s1（i，j），检查Sdescend若为空，则算法结束，否则转Step2。

3 算例分析

负责某汽车制造商入厂物流的第三方物流企业，现已知拥有统一容量为20单位的车辆若干辆，车辆在各供应点的装载时间为0.5，车辆的平均行驶速度为45，承担汽车零部件供应任务的区域供应商位置坐标、供货数量及取货约定时间窗如表1所示。

采用本文所提的改进节约算法，求得最优实验结果如表2所示。

从计算结果可以看出，算法运行结果满足所有约束条件，可作为入厂物流循环取货路径安排的依据，具有一定的实用价值。

4 结论

本文以汽车零部件入厂物流为研究对象，分析了零部件循环取货的特点，建立了基于硬时间窗和车辆容量约束的数学模型，构建了改进节约算法对该问题进行求解，最后通过算例验证了算法的可行性和有效性，为企业规划循环取货车辆路径提供了参考。

参考文献：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]叶雷.循环取料在上海通用汽车零部件入厂物流中的应用研究[D].上海：复旦大学，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]张建勇，郭耀煌，李军.一种具有模糊费用系数的VSP的修正C-W节约算法[J].西南交通大学学报，2004，6（3）：281-284.endprint