论文部分内容阅读
摘要：文章研究Just in Time（JIT）背景下制造商主导的第三方物流（Third Party Logistics, 3PL）运输调度问题。制造商根据其生产计划的要求进行采购。文章使用C-W路线优化算法，在线路规划中考虑了车辆载重量、容积以及车辆到达时间的影响，实现以最小的成本达到JIT采购的目的，并用一个实例验证了修正的C-W算法对解决采购物流中运输调度问题的适用性。
关键词：JIT；运输调度；C-W节约算法；3PL
中图分类号：F224文献标识码：A
Abstract: After analyzed vehicle scheduling problem for manufacture using third party logistics in JIT condition, this paper used C-W algorithm in vehicle scheduling problem. In view of the characteristic of transported products in the manufacture purchasing logistics, vehicle capacity, volume and arriving time as constraint condition was inserted in the route plan, so as to satisfy the purpose of using the least cost for JIT purchase. Then an example was given to confirm the serviceability of the modified C-W algorithm in solving the vehicle scheduling problem.
Key words: JIT; scheduling problem; C-W algorithm; 3PL
0引言
制造业的激烈竞争，使Just in Time（JIT）的采购方式受到越来越多的企业的关注，这种源自于日本丰田汽车公司准时制生产的采购方式，要求既要能保证物资的供应，又要降低库存量、缩短订货提前期、提高产品质量、降低采购成本。在这种采购方式下，车辆的提早或延迟到达原材料供应地均会产生附加成本。因此制造企业在制定其生产调度和运输调度策略时，必须从全局出发，考虑供应链整体动作成本最小化。作为整个供应链中的一环，在进行车辆的运输调度时，必须考虑与生产之间的有效衔接。
受到外资第三方物流公司大举进入中国的影响，近年来，我国的物流企业有了较大的发展，第三方物流（Third Party Logistics，3PL）日益成熟，相当数量的制造商开始有选择性的将物流业务外包给3PL以有效衔接生产、提高JIT采购水平、降低采购成本。研究表明，供应链中第三方物流运输调度问题主要分为两类：生产企业主导和3PL主导[1]。
目前研究多关注第一种3PL运输调度问题。Ruiz Torres和Tyworth（1997）[2]用仿真模型测试了一些简单的调度法则，证明在生产和运输中采用恰当的调度法则可使整个系统的效率大大提高。Chang和Lee（2001）[3]的研究目标是最小化所有作业的生产和运输总时间。Garcia et al.（2004）[4]考虑多生产工厂的系统，目标是决定最优的订单至车辆的装载，使系统利润最大化。但在最终模型求解的过程中，由于精确算法（包括直接树搜索算法、动态规划法和整数线性规划法三类）只能有效求解中小规模的确定性问题，当求解大规模问题时，无法在有限时间里找到满意的次优解或可行解。因此，在实际应用中，人工智能算法应用更广泛。
1C-W节约算法研究与改进
Clarke和Wright在1964年提出的节约法（简称为C-W算法）是启发式算法中的一种，用来解决车辆数不固定的运输调度问题[5]。由于算法的简单实用，又能很容易的将真实世界的一些约束条件包含进算法模型中，因此在调度规划模型中得到了广泛应用。但国内使用该算法解决运输调度优化问题的研究还比较少。
目前有关C-W算法的研究多用于物流配送，如连锁超市、烟草配送等，且带时间窗约束的改进算法研究较多，但却少有将该算法应用于采购物流领域的。从物流布局来看，采购物流的VRP问题也可以用配送领域的C-W算法来解决。但必须满足两个前提条件：（1）整个供应链由生产企业主导；（2）采购所需原材料的生产过程平稳有序，采购企业可以使用JIT的生产方式。
1.1基本数学模型
1.1.1假设下列条件已知
（1）生产商的原材料仓库与供应商、供应商与供应商之间的距离。令Ci,j为i到j的距离，若i或j等于0，则为收货仓库；若i或j不等于0，则为供应商。N为供应商和生产商的集合。为单位距离的运输成本。
（2）每次取货时，向供应商采购产品的数量。令Wi为从供应商i处采购的原材料重量（i=1,2,…,n）。
（3）不同车型的载重量。令Qk为车辆k的最大载重量。K为车辆集合，k∈K。
1.1.2数学模型
由于采购取货的基本目标是总运输距离最小化，因此目标函数为：
minZ=CX
X=0或1（1）
Yk,i=0或1 （2）
WiYk,i≤Qk （3）
Yk,i=1 （4）
Xk,ij=Yk,j （5）
Xk,ij=Yk,i （6）
其中，约束条件（1）表示车辆k从点i到点j，其中i≠j；i,j∈N；约束条件（2）表示供应商i处的原材料由车辆k收取，其中i≠0；约束条件（3）表示每一采购路线上采购数量受车辆最大载重量的限制；约束条件（4）表示每个采购商处必须有一辆车去取货；约束条件（5）表示如果车辆k至采购商j处取货，则k必从点i到达点j；约束条件（6）表示若车辆k至采购商i处取货，则k必在该处取完货后到达采购商j。
1.2修正的数学模型
上述基本数学模型只对车辆的最大载重量做了限定，朱晓兰（2007）[6]在其研究中增加了车辆容积和取货周期内车辆最远行驶距离两个约束条件；李静（2007）[7]不仅考虑了车辆容积问题，同时考虑货物的形状对装载容积的影响，以总容积乘以经验系数来考虑容积约束问题。但是关于时间对运输影响的研究则不多见。在众多企业努力提高JIT采购水平时，忽略运输时间显然是与实际不相符的。
因此在基本C-W算法模型中加入容积约束以及运输提前或延迟对目标函数的影响。
（1）容积约束
ViYk,i≤Vc,k （7）
其中Vi为车辆在供应商i处的容积，Vc,k为车辆k的最大容积。
（2）时间的约束
LEij——连接供应商i与供应商j后，车辆到达供应商j的时间比原线路上车辆到达供应商j时间的提前量（延迟量）
di——为到达供应商i处的规定时间
dij——为从供应商i处到供应商j处的规定时间
Ti——为在供应商i处的装货时间
ETi——为供应商i处允许的最早开始时间，车辆早于此时间则会等待
LTi——为供应商i处允许的最迟开始时间，车辆晚于此时间则会延迟
则:
LEij=di+Ti+dij-dj （8）
设车辆经过供应商j之后所需要经过的供应商为r，当LEij<0，若LEij≤mind-ET，则在经过供应商j之后车辆到过其他供应商时不需要等待，否则，要等待；当LEij>0时，若LEij≤minLT-d，则在经过供应商j之后车辆到过其他供应商时不会出现延迟，否则需要延迟进行。
1.3修正的C-W算法
根据Clarke和Wright共同提出的C-W算法，本文做如下约定：（1）若只有1个供应商的线路0→i→0称作初始线路；（2）包含2个及2个以上供应商的线路称作组合线路0→…→i→j→…→0称作组合线路。根据上述修正后的模型，C-W算法步骤如下：
步骤1：将各供应商与工厂仓库相连，构成n条初始化线路。第i条线路的运输距离为DCi=C0,i+Ci,0。
步骤2：计算将两个供应商i，j连接在一条线路上的距离节约值Si,j=C0, j+C0, j-Di, j，令Si,j=Si,j+Pi,j，M=S|S>0；i,j=1,2,…,n，将集合M内的元素Si,j按从大到小的顺序排列。
步骤3：考虑集合M内的第一个元素NSi,j所对应的供应商i，j是否满足下列条件之一：
①供应商i，j均在初始路线上；
②供应商i，j中有一个在其他组合线路中，并且是线路的起点或终点，另一个在初始线路上；
③供应商分别在两条不同的线路上，但一个是起点，另一个是终点。
若满足则转步骤4，否则转步骤8。
步骤4：根据供应商i，j处货物的重量和体积计算若将i，j连接，车辆的载重量和容积是否满足约束条件（1）和（7）。若满足，转向步骤6，否则转步骤5。
步骤5：从车辆集合K中选择更大的车型，转步骤4，如果已达可用车辆容量上限，则转步骤8。
步骤6：计算LEij，若LEij=0，转步骤7；若LEij<0且LEij≤mind-ETr，则转步骤7，否则转步骤8；若LEij>0且LEij≤minLT-d，则转步骤7，否则转步骤8。
步骤7：连接供应商i和j，构成新组合线路。
步骤8：在集合M中消去元素Si,j，若M≠，转步骤3，继续探索新的组合方案。否则算法终止。
2实例
案例描述：P0为一家生产手机的公司，生产过程以流水线装配为主，产品采用按订单生产，使用JIT的生产方式，采用3PL公司保障物料供应，3PL公司采取主动上门收货的采购模式。各供应商的货物供给量、货物体积及车辆到达时间要求如表1所示，其中3PL的运输车队于凌晨2点出发，假定车辆的时速为60km/h，固定装货时间为1分钟。车队有10吨货车1辆、5吨货车2辆，5吨和10吨货车的有效容积分别为12m3和20m3，选取9家具有代表性的供应商，各个供应商P,P,…,P之间以及它们与P的地理位置如表2所示。
采用VC++编程求解。按照上述求解步骤，经计算产生三条线路：
P→P1→P0该线路采用10t货车满载运输。
P→P1→P8→P9→P7→P0该线路采用5吨货车满载运输，容积为10.4m3。
P→P3→P2→P4→P6→P5→P0该线路采用5吨货车，载重量为4.8t，容积为8.7m3。
由此可见，通过该算法，各需求点都能得到较优的运输方案，供应商P1的供应量最大，可以采用整车运输的方式，其余各供应商采用5吨货车收取货物。
3总结
本文研究了生产企业主导的第三方物流在JIT条件下的车辆调度问题。基本C-W算法可以保证运输路径的合理化，有效缩减了运输距离；加入到达时间约束后，使运输时间成为一项非常重要的决定因素。因此修正后的C-W算法可以较好地应用于JIT采购。本文建立模型还可以在多个方面进一步拓展，此外对于装卸货时间的动态变化等约束条件会使问题变得非常复杂，还有待作进一步的研究。
参考文献：
[1]李昆鹏, 马士华. 基于JIT配送的3PL运输协调调度问题建模与分析[J]. 交通与计算机, 2008(2):73-79.
[2]Ruiz Torres, A.J., Tyworth, J.E. Simulation based approach to study the interaction of scheduling and routing on a logistic network[C]//Proceeding of the 1997 Winter Simulation Conference, 1997.
[3]Chang, Y.C., Lee, C.Y.. Machine scheduling with job delivery coordination[J]. European Journal of Operational Research,2004,158:470-487.
[4]Garcia, J.M., Lozano, S., Canca, D.. Coordinated scheduling of production and delivery from multiple plants[J]. Robotics and Computer Integrated Manufacturing, 2004,20(3):191-198.
[5]祝崇隽, 刘民, 吴澄. 供应链中车辆路径问题的研究进展及前景[J]. 计算机集成制造系统——CIMS, 2001(7):1-6.
[6]朱晓兰, 赵一飞. C-W节约算法在装配企业采购物流中的应用[J]. 上海交通大学学报, 2007(9):1420-1424.
[7]李静, 钟典钦. 基于CW节约算法的ERP系统改进研究[J]. 计算机工程与设计, 2007(11):5214-5217.
[8]林晓宇, 李金铭, 纪寿文. 车辆路径问题Clarke-Wright算法的改进与实现[J]. 交通与计算机, 2004(6):72-75.
关键词：JIT；运输调度；C-W节约算法；3PL
中图分类号：F224文献标识码：A
Abstract: After analyzed vehicle scheduling problem for manufacture using third party logistics in JIT condition, this paper used C-W algorithm in vehicle scheduling problem. In view of the characteristic of transported products in the manufacture purchasing logistics, vehicle capacity, volume and arriving time as constraint condition was inserted in the route plan, so as to satisfy the purpose of using the least cost for JIT purchase. Then an example was given to confirm the serviceability of the modified C-W algorithm in solving the vehicle scheduling problem.
Key words: JIT; scheduling problem; C-W algorithm; 3PL
0引言
制造业的激烈竞争，使Just in Time（JIT）的采购方式受到越来越多的企业的关注，这种源自于日本丰田汽车公司准时制生产的采购方式，要求既要能保证物资的供应，又要降低库存量、缩短订货提前期、提高产品质量、降低采购成本。在这种采购方式下，车辆的提早或延迟到达原材料供应地均会产生附加成本。因此制造企业在制定其生产调度和运输调度策略时，必须从全局出发，考虑供应链整体动作成本最小化。作为整个供应链中的一环，在进行车辆的运输调度时，必须考虑与生产之间的有效衔接。
受到外资第三方物流公司大举进入中国的影响，近年来，我国的物流企业有了较大的发展，第三方物流（Third Party Logistics，3PL）日益成熟，相当数量的制造商开始有选择性的将物流业务外包给3PL以有效衔接生产、提高JIT采购水平、降低采购成本。研究表明，供应链中第三方物流运输调度问题主要分为两类：生产企业主导和3PL主导[1]。
目前研究多关注第一种3PL运输调度问题。Ruiz Torres和Tyworth（1997）[2]用仿真模型测试了一些简单的调度法则，证明在生产和运输中采用恰当的调度法则可使整个系统的效率大大提高。Chang和Lee（2001）[3]的研究目标是最小化所有作业的生产和运输总时间。Garcia et al.（2004）[4]考虑多生产工厂的系统，目标是决定最优的订单至车辆的装载，使系统利润最大化。但在最终模型求解的过程中，由于精确算法（包括直接树搜索算法、动态规划法和整数线性规划法三类）只能有效求解中小规模的确定性问题，当求解大规模问题时，无法在有限时间里找到满意的次优解或可行解。因此，在实际应用中，人工智能算法应用更广泛。
1C-W节约算法研究与改进
Clarke和Wright在1964年提出的节约法（简称为C-W算法）是启发式算法中的一种，用来解决车辆数不固定的运输调度问题[5]。由于算法的简单实用，又能很容易的将真实世界的一些约束条件包含进算法模型中，因此在调度规划模型中得到了广泛应用。但国内使用该算法解决运输调度优化问题的研究还比较少。
目前有关C-W算法的研究多用于物流配送，如连锁超市、烟草配送等，且带时间窗约束的改进算法研究较多，但却少有将该算法应用于采购物流领域的。从物流布局来看，采购物流的VRP问题也可以用配送领域的C-W算法来解决。但必须满足两个前提条件：（1）整个供应链由生产企业主导；（2）采购所需原材料的生产过程平稳有序，采购企业可以使用JIT的生产方式。
1.1基本数学模型
1.1.1假设下列条件已知
（1）生产商的原材料仓库与供应商、供应商与供应商之间的距离。令Ci,j为i到j的距离，若i或j等于0，则为收货仓库；若i或j不等于0，则为供应商。N为供应商和生产商的集合。为单位距离的运输成本。
（2）每次取货时，向供应商采购产品的数量。令Wi为从供应商i处采购的原材料重量（i=1,2,…,n）。
（3）不同车型的载重量。令Qk为车辆k的最大载重量。K为车辆集合，k∈K。
1.1.2数学模型
由于采购取货的基本目标是总运输距离最小化，因此目标函数为：
minZ=CX
X=0或1（1）
Yk,i=0或1 （2）
WiYk,i≤Qk （3）
Yk,i=1 （4）
Xk,ij=Yk,j （5）
Xk,ij=Yk,i （6）
其中，约束条件（1）表示车辆k从点i到点j，其中i≠j；i,j∈N；约束条件（2）表示供应商i处的原材料由车辆k收取，其中i≠0；约束条件（3）表示每一采购路线上采购数量受车辆最大载重量的限制；约束条件（4）表示每个采购商处必须有一辆车去取货；约束条件（5）表示如果车辆k至采购商j处取货，则k必从点i到达点j；约束条件（6）表示若车辆k至采购商i处取货，则k必在该处取完货后到达采购商j。
1.2修正的数学模型
上述基本数学模型只对车辆的最大载重量做了限定，朱晓兰（2007）[6]在其研究中增加了车辆容积和取货周期内车辆最远行驶距离两个约束条件；李静（2007）[7]不仅考虑了车辆容积问题，同时考虑货物的形状对装载容积的影响，以总容积乘以经验系数来考虑容积约束问题。但是关于时间对运输影响的研究则不多见。在众多企业努力提高JIT采购水平时，忽略运输时间显然是与实际不相符的。
因此在基本C-W算法模型中加入容积约束以及运输提前或延迟对目标函数的影响。
（1）容积约束
ViYk,i≤Vc,k （7）
其中Vi为车辆在供应商i处的容积，Vc,k为车辆k的最大容积。
（2）时间的约束
LEij——连接供应商i与供应商j后，车辆到达供应商j的时间比原线路上车辆到达供应商j时间的提前量（延迟量）
di——为到达供应商i处的规定时间
dij——为从供应商i处到供应商j处的规定时间
Ti——为在供应商i处的装货时间
ETi——为供应商i处允许的最早开始时间，车辆早于此时间则会等待
LTi——为供应商i处允许的最迟开始时间，车辆晚于此时间则会延迟
则:
LEij=di+Ti+dij-dj （8）
设车辆经过供应商j之后所需要经过的供应商为r，当LEij<0，若LEij≤mind-ET，则在经过供应商j之后车辆到过其他供应商时不需要等待，否则，要等待；当LEij>0时，若LEij≤minLT-d，则在经过供应商j之后车辆到过其他供应商时不会出现延迟，否则需要延迟进行。
1.3修正的C-W算法
根据Clarke和Wright共同提出的C-W算法，本文做如下约定：（1）若只有1个供应商的线路0→i→0称作初始线路；（2）包含2个及2个以上供应商的线路称作组合线路0→…→i→j→…→0称作组合线路。根据上述修正后的模型，C-W算法步骤如下：
步骤1：将各供应商与工厂仓库相连，构成n条初始化线路。第i条线路的运输距离为DCi=C0,i+Ci,0。
步骤2：计算将两个供应商i，j连接在一条线路上的距离节约值Si,j=C0, j+C0, j-Di, j，令Si,j=Si,j+Pi,j，M=S|S>0；i,j=1,2,…,n，将集合M内的元素Si,j按从大到小的顺序排列。
步骤3：考虑集合M内的第一个元素NSi,j所对应的供应商i，j是否满足下列条件之一：
①供应商i，j均在初始路线上；
②供应商i，j中有一个在其他组合线路中，并且是线路的起点或终点，另一个在初始线路上；
③供应商分别在两条不同的线路上，但一个是起点，另一个是终点。
若满足则转步骤4，否则转步骤8。
步骤4：根据供应商i，j处货物的重量和体积计算若将i，j连接，车辆的载重量和容积是否满足约束条件（1）和（7）。若满足，转向步骤6，否则转步骤5。
步骤5：从车辆集合K中选择更大的车型，转步骤4，如果已达可用车辆容量上限，则转步骤8。
步骤6：计算LEij，若LEij=0，转步骤7；若LEij<0且LEij≤mind-ETr，则转步骤7，否则转步骤8；若LEij>0且LEij≤minLT-d，则转步骤7，否则转步骤8。
步骤7：连接供应商i和j，构成新组合线路。
步骤8：在集合M中消去元素Si,j，若M≠，转步骤3，继续探索新的组合方案。否则算法终止。
2实例
案例描述：P0为一家生产手机的公司，生产过程以流水线装配为主，产品采用按订单生产，使用JIT的生产方式，采用3PL公司保障物料供应，3PL公司采取主动上门收货的采购模式。各供应商的货物供给量、货物体积及车辆到达时间要求如表1所示，其中3PL的运输车队于凌晨2点出发，假定车辆的时速为60km/h，固定装货时间为1分钟。车队有10吨货车1辆、5吨货车2辆，5吨和10吨货车的有效容积分别为12m3和20m3，选取9家具有代表性的供应商，各个供应商P,P,…,P之间以及它们与P的地理位置如表2所示。
采用VC++编程求解。按照上述求解步骤，经计算产生三条线路：
P→P1→P0该线路采用10t货车满载运输。
P→P1→P8→P9→P7→P0该线路采用5吨货车满载运输，容积为10.4m3。
P→P3→P2→P4→P6→P5→P0该线路采用5吨货车，载重量为4.8t，容积为8.7m3。
由此可见，通过该算法，各需求点都能得到较优的运输方案，供应商P1的供应量最大，可以采用整车运输的方式，其余各供应商采用5吨货车收取货物。
3总结
本文研究了生产企业主导的第三方物流在JIT条件下的车辆调度问题。基本C-W算法可以保证运输路径的合理化，有效缩减了运输距离；加入到达时间约束后，使运输时间成为一项非常重要的决定因素。因此修正后的C-W算法可以较好地应用于JIT采购。本文建立模型还可以在多个方面进一步拓展，此外对于装卸货时间的动态变化等约束条件会使问题变得非常复杂，还有待作进一步的研究。
参考文献：
[1]李昆鹏, 马士华. 基于JIT配送的3PL运输协调调度问题建模与分析[J]. 交通与计算机, 2008(2):73-79.
[2]Ruiz Torres, A.J., Tyworth, J.E. Simulation based approach to study the interaction of scheduling and routing on a logistic network[C]//Proceeding of the 1997 Winter Simulation Conference, 1997.
[3]Chang, Y.C., Lee, C.Y.. Machine scheduling with job delivery coordination[J]. European Journal of Operational Research,2004,158:470-487.
[4]Garcia, J.M., Lozano, S., Canca, D.. Coordinated scheduling of production and delivery from multiple plants[J]. Robotics and Computer Integrated Manufacturing, 2004,20(3):191-198.
[5]祝崇隽, 刘民, 吴澄. 供应链中车辆路径问题的研究进展及前景[J]. 计算机集成制造系统——CIMS, 2001(7):1-6.
[6]朱晓兰, 赵一飞. C-W节约算法在装配企业采购物流中的应用[J]. 上海交通大学学报, 2007(9):1420-1424.
[7]李静, 钟典钦. 基于CW节约算法的ERP系统改进研究[J]. 计算机工程与设计, 2007(11):5214-5217.
[8]林晓宇, 李金铭, 纪寿文. 车辆路径问题Clarke-Wright算法的改进与实现[J]. 交通与计算机, 2004(6):72-75.