基于c-w算法物流配送线路优化探究摘要：首先介绍C-W算法的原理与步骤，之后分析公司现有物流配送路线。运用c-w算法优化了公司物流配送线路，减少了运输距离，提高了运输效率，降低了物流成本。关键词：物流配送；配送线路；CTV算法；优化中图分类号:F250文献标志码：A文章编号:1673-291X(2013)06-0184-03某公司以前的配送路线按照货车司机的经验，存在运输资源利用不合理、运输距离过髙、物流效率低下等诸多问题,物流配送成本居高不下。公司拟采用c-W节约启发式算法对公司物流配送线路进行优化。一、c-W算法简介(一)c-W算法基本原理启发式方法中最具有代表性的就是Clarke和Wright提出的节约法，许多成功的车辆调度软件就是根据该方法或其他改进方法开发的。G订liet和M订le提出的扫描法，先把节点或弧的需求进行分组或划群，然后对每一组按旅行商(TSP)求解，设计出一种经济的线路。C-W算法的原理是节约里程法从节约里程的角度来优化配送路线的，其基本思路是假设P为公司配送中心所在地，A和B分别为两个烟草经销商客户所在地，设P到A的距离为LI,P到B的距离为L2,B到A的距离为L3o根据上面的情况，从P点向这两个地方配送的最简单的配送的方案有两种方案。方案一：是用两辆车向A和B分别配送，那么车辆运行距离是2L1+2L2；方案二：然而改用一辆车向A和B同时配送，那么车辆运行的距离是L1+L2+L3O综合上面两种方案的比较可以得出节约运行距离：(2L1+2L2)-(L1+L2+L3)=Ll+L2-L3>0,L1+L2-L3这段节约的距离也被称为“节约行程”,换句话说L1+L2-L3就是节约的运输成本。(二)C-W节约启发式算法原理假设公司配送客户为i,i=l,-n(假定公司配送中心的代码为0),以cij表示车辆从点i行驶到点j的费用，由C-W算法，得到点i和点j连接在一条线路上的费用节约值：s(i,j)=ci0+cOj-cij(1)当不考虑时间约束时，其算法与C-W算法类似，只是在连接点对时，需要考虑车辆的容量约束，即一条线路上各个任务的货运量之和不应大于车辆的容量。若各项任务要求在一定的时间内完成，按费用节约值s(i,j)连接点i与j路时，若车辆到达j点的时间比原线路上j点任务的开始时间提前，则车辆在j后面的任务有可能需要等待；若连接后到达j点的时间比原来线路上j点任务的时间的开始时间推迟，则j后面的任务在执行时可能会发生延迟。以EFj表示连接点i和点j所在的线路后，车辆到达j点的时间比原线路上车辆到达j点时间的推迟（或提前量）,则EFj如下得到显然，EFjO时，到达时间推迟。为说明问题方便，定义参数如下：P-j—车辆在j点后面的任务处均不需要等待的j点到达时间的最大可以提前量；P+j—线路上j点后面的任务不违反时间窗约束的j点的到达时间的最大允许推迟量。p-j和可P+j分别按下式计算当考虑连接点i和点j所在的线路是时，需要检查是否违反时间窗约束。当EFjO时，若EFjWP+j,则j后面的任务的执行不会延迟，否则，要延迟进行。由于引入时间约束，在对称的费用情况下，连接点j和点i与连接点i点j已再不相同。二、公司主要供应商及路线状况公司物流配送中心与各销售商的路程（见下页表1）。公司物流配送货物的体积是110X10X50（cm3）,货运量gi（单位：箱），装货（或卸货）时间Ti（单位：小时）以及要求每项任务开始执行的时间范围［ETi,LTi］由表2给出（单位:小时）。公司采用的送货车量是5吨货车，其容积为6mX2.3mX2.5m,从而得出每辆车可以装600箱。配送中心与各任务点以及任务点之间的距离（单位：公里）（见表2）。三、公司物流配送线路优化（一）公司费用节约值的计算我们假设配送车辆的行驶时间与距离成正比，根据市内的交通状况，考虑到交通的拥挤等因素影响，设每辆车的平均行驶速度为30公里/小时，则从点i到j的行驶时间tij=dij/30,行使时间也将在下面给出。把各点之间的距离作为广义的物流成本费用，即cij二dij（i,j=0,1,2,3,4-10）,因此可以得到任何两个点之间得时间列表（见表3）（小时）。目前我们要做的就是如何安排车辆的行驶路线，在满足约束条件下使总运行费用最少。初始时，当车辆从配送中心0开始任务i时，若ETiWtOiWLTi,取si=tOi,若tOiWETi,取si二ETi。通过上面研究可以得出：各点对之间连接的费用节约值类似地，根据公式...