简论基于C—W算法物流配送线路优化

img src="www.udooo.com/UploadFiles/2014-02/2/20142177564258281.jpg" alt="基于C—W算法的物流配送线路优化研究" />摘 要：首先介绍C-W算法的原理与步骤，之后分析公司现有物流配送路线。运用C-W算法优化了公司物流配送线路，减少了运输距离，提高了运输效率，降低了物流成本。
关键词：物流配送；配送线路；C-W算法；优化
1673-291X（2013）06-0184-03
某公司以前的配送路线按照货车司机的经验，存在运输资源利用不合理、运输距离过高、物流效率低下等诸多理由，物流配送成本居高不下。公司拟采用C-W节约启发式算法对公司物流配送线路进行优化。

一、C-W算法简介

(一)C-W算法基本原理

启发式策略中最具有代表性的就是Clarke和Wright提出的节约法，许多成功的车辆调度软件就是根据该策略或其他改善策略开发的。Gilliet和Mille提出的扫描法，先把节点或弧的需求进行分组或划群，然后对每一组按旅行商（TSP）求解，设计出一种经济的线路。
C-W算法的原理是节约里程法从节约里程的角度来优化配送路线的，其基本思路是检测设P为公司配送中心所在地，A和B分别为两个烟草经销商客户所在地，设P到A的距离为L1，P到B的距离为L2，B到A的距离为L3。
根据上面的情况，从P点向这两个地方配送的最简单的配送的方案有两种方案。方案一：是用两辆车向A和B分别配送，那么车辆运转距离是2L1+2L2；方案二：然而改用一辆车向A和B同时配送，那么车辆运转的距离是L1+L2+L3。综合上面两种方案的比较可以得出节约运转距离：（2L1+2L2）-（L1+L2+L3）=L1+L2-L3>0，L1+L2-L3这段节约的距离也被称为“节约行程”，换句话说L1+ L2- L3就是节约的运输成本。

(二)C-W节约启发式算法原理

检测设公司配送客户为i，i=1，…n（检测定公司配送中心的代码为0），以cij 表示车辆从点i行驶到点j的费用，由C-W算法，得到点i和点j连接在一条线路上的费用节约值：
s（i，j）=ci0+ c0j- cij （1）
当不考虑时间约束时，其算法与C-W算法类似，只是在连接点对时，需要考虑车辆的容量约束，即一条线路上各个任务的货运量之和不应大于车辆的容量。
若各项任务要求在一定的时间内完成，按费用节约值s（i，j）连接点i与j路时，若车辆到达j点的时间比原线路上j点任务的开始时间提前，则车辆在j后面的任务有可能需要等待；若连接后到达j点的时间比原来线路上j点任务的时间的开始时间推迟，则j后面的任务在执行时可能会发生延迟。
以EFj表示连接点i和点j所在的线路后，车辆到达j点的时间比原线路上车辆到达j点时间的推迟（或提前量），则EFj如下得到
显然，EFj<0时，车辆到达j点任务的时间提前；EFj=0时，到达时间不变；EFj>0时，到达时间推迟。
为说明理由方便，定义参数如下：P-j—车辆在j点后面的任务处均不需要等待的j点到达时间的最大可以提前量；P+j—线路上j点后面的任务不违反时间窗约束的j点的到达时间的最大允许推迟量。
P-j和 可P+j分别按下式计算
当考虑连接点i和点j所在的线路是时，需要检查是否违反时间窗约束。
当EFj<0时，若|EFj|≤P-
j，车辆在j后面的任务处不需要等待，否则，要等待；当EFj>0时，若EFj≤P+
j，则j后面的任务的执行不会延迟，否则，要延迟进行。
由于引入时间约束，在对称的费用情况下，连接点j和点i与连接点i点j已再不相同。

二、公司主要供应商及路线状况

公司物流配送中心与各销售商的路程（见下页表1）。公司物流配送货物的体积是110×10×50（cm3），货运量gi（单位：箱），装货（或卸货）时间Ti（单位：小时）以及要求每项任务开始执行的时间范围[ETi，LTi]由表2给出（单位：小时）。公司采用的送货车量是5吨货车，其容积为6m×2.3m×2.5m，从而得出每辆车可以装600箱。配送中心与各任务点以及任务点之间的距离（单位：公里）（见表2）。

三、公司物流配送线路优化

(一)公司费用节约值的计算

我们检测设配送车辆的行驶时间与距离成正比，根据市内的交通状况，考虑到交通的拥挤等因素影响，设每辆车的平均行驶速度为30公里/小时，则从点i到j的行驶时间tij=dij /30，行使时间也将在下面给出。把各点之间的距离作为广义的物流成本费用，即cij=dij（i，j=0，1，2，3，4…10），因此可以得到任何两个点之间得时间列表（见表3）（小时）。目前我们要做的就是如何安排车辆的行驶路线，在满足约束条件下使总运转费用最少。
初始时，当车辆从配送中心0开始任务i时，若ETi≤t0i≤LTi，取si=t0i，若t0i≤ETi，取si= ETi。
通过上面研究可以得出：各点对之间连接的费用节约值
类似地，根据公式（4）可以得到连接其他各点对时的费用节约值。
由于距离为对称距离，因此有
故表中所示的s（i，j）与s（j，i）实际上是等价的。
为了计算及研究的方便，本文将把各个销售点之间的距离作为广义的物流成本来计算，检测设每公里作为一个单位成本，根据（4）、（5）两项公式可以得出下面的结果：s（1，2）=d10+ d20-

(二)公司物流配送路线优化分析

根据上面所列举的节约值，然后逐项考察对应的i-j，并且将在下面详细讲述点对之间的连接过程。在路线的优化过程中，对路线的优化要对其进行详细的分析最终才能得出正确的规划路线。如果被考察的i-j中，若两点均不在线路上，则考察i-j或j-i；若一点不在线路上，一点是外点，则考察（i不在线路上、j是线路的起点，或i是线路的终点、j不在线路上）或者j-i（j不在线路上、i是线路的起点，或j是线路的终点、i不在线路上）；若两点都是线路上的外点，则根据点的位置关系，构造成终点（一条线路）→起点（另一条线路）的顺序。在考查点对位置的时候如果不能连接，则可以将其终止，换到分析其他的点对，如果上面的两项都符合基于C—W算法的物流配送线路优化由优秀论文网站www.udooo.com提供,助您写好论文.，那么之后就将两个点的任务量汇总，只有在任务汇总不大于车载容量的时候才能继续进行。计算点i和点j连接后的EFj的数值，如果EFj>0，则计算P+
j，如果EFj<0，则计算P+
j，检测设结果满足时间约束，则可以按照该路线配送，同时用L表示i和 j连接后，j 后面的任务的新的开始时间，当一个点不在线路上时，认为点i与配送中心单独构成0—i—0。
其具体分析过程如下：
综合上面的分析可以得出公司最佳配送的路径如下：0→1→3→4→0；0→6→8→5→0；0→10→9→0；0→2→7→0。

四、结束语

公司物流配送路线优化之后，不仅减少了运输费用，而且在配送运输活动时，充分利用车辆的载重，减少了运输距离，使得运输资源得到了充分的利用，从而提高了运输效率，降低了物流成本。