基于C—W算法物流配送线路优化探究

1、基于c-w算法物流配送线路优化探究摘要：首先介绍c-w算法的原理与步骤，之后分 析公司现有物流配送路线。运用c-w算法优化了公司物流配 送线路，减少了运输距离，提高了运输效率，降低了物流成 本。关键词：物流配送；配送线路；c-w算法；优化中图分类号：f250文献标志码：a文章编号：1673-291x (2013) 06-0184-03某公司以前的配送路线按照货车司机的经验，存在运输 资源利用不合理、运输距离过高、物流效率低下等诸多问题, 物流配送成本居高不下。公司拟采用c-w节约启发式算法对 公司物流配送线路进行优化。一、c-w算法简介(一)c-w算法基本原理启发式方法中最具有代表性的就是cl

2、arke和wright提 出的节约法，许多成功的车辆调度软件就是根据该方法或其 他改进方法开发的。gilliet和m订le提出的扫描法，先把 节点或弧的需求进行分组或划群，然后对每一组按旅行商 (tsp)求解，设计出一种经济的线路。c-w算法的原理是节约里程法从节约里程的角度来优化 配送路线的，其基本思路是假设p为公司配送中心所在地，a和b分别为两个烟草经销商客户所在地，设p到a的距离 为li, p到b的距离为l2, b到a的距离为l3o根据上面的情况，从p点向这两个地方配送的最简单的 配送的方案有两种方案。方案一：是用两辆车向a和b分别 配送，那么车辆运行距离是2l1+2l2；方案二：然而改

3、用一 辆车向a和b同时配送，那么车辆运行的距离是l1+l2+l3。 综合上面两种方案的比较可以得出节约运行距离： (2l1+2l2) - (l1+l2+l3)二ll+l2-l3>0, l1+l2-l3 这段节 约的距离也被称为“节约行程”,换句话说l1+ l2- l3就 是节约的运输成本。(二)c-w节约启发式算法原理假设公司配送客户为1, 1=1, -n (假定公司配送中心 的代码为0),以cij表示车辆从点i行驶到点j的费用， 由c-w算法，得到点i和点j连接在一条线路上的费用节约 值：s (i, j) =ci0+ coj- cij (1)当不考虑时间约束时，其算法与c-w算法类似，

4、只是在 连接点对时，需要考虑车辆的容量约束，即一条线路上各个 任务的货运量之和不应大于车辆的容量。若各项任务要求在一定的时间内完成，按费用节约值s (i, j)连接点i与j路时，若车辆到达j点的时间比原线 路上j点任务的开始时间提前，则车辆在j后面的任务有可 能需要等待；若连接后到达j点的时间比原来线路上j点任 务的时间的开始时间推迟，则j后面的任务在执行时可能会 发生延迟。以efj表示连接点i和点j所在的线路后，车辆到达j 点的时间比原线路上车辆到达j点时间的推迟（或提前量）, 则efj如下得到显然，efjo时，到达时间推迟。为说明问题方便，定义参数如下：p-j车辆在j点后 面的任务处均不需

5、要等待的j点到达时间的最大可以提前 量；p+j线路上j点后面的任务不违反时间窗约束的j点 的到达时间的最大允许推迟量。p-j和 可p+j分别按下式计算当考虑连接点i和点j所在的线路是时，需要检查是否 违反时间窗约束。当 efjo 时，若 efjwp+j,则j后面的任务的执行不会延迟，否则，要延迟进 行。由于引入时间约束，在对称的费用情况下，连接点j和 点i与连接点i点j已再不相同。二、公司主要供应商及路线状况公司物流配送中心与各销售商的路程（见下页表l）o公 司物流配送货物的体积是110x10x50（cm3）,货运量gi（单 位：箱），装货（或卸货）时间ti （单位：小时）以及要求 每项任务开

6、始执行的时间范围eti, lti由表2给出（单位: 小时）。公司采用的送货车量是5吨货车，其容积为 6mx2. 3mx2. 5m,从而得出每辆车可以装600箱。配送中心 与各任务点以及任务点之间的距离（单位：公里）（见表2）。三、公司物流配送线路优化（一）公司费用节约值的计算我们假设配送车辆的行驶时间与距离成正比，根据市内 的交通状况，考虑到交通的拥挤等因素影响，设每辆车的平 均行驶速度为30公里/小时，则从点i到j的行驶时间 tij=dij /30,行使时间也将在下面给出。把各点之间的距 离作为广义的物流成本费用，即cij=dij （i, j=0, 1, 2, 3, 410）,因此可以得到任

7、何两个点之间得时间列表（见表3）（小时）。目前我们要做的就是如何安排车辆的行驶路线, 在满足约束条件下使总运行费用最少。初始时，当车辆从配送中心0开始任务i时，若etiwtoiwlti,取 si二toi,若 toiweti,取 si二 eti。通过上面研究可以得出：各点对之间连接的费用节约值 类似地，根据公式（4）可以得到连接其他各点对时的费用节约值。由于距离为对称距离，因此有 故表中所示的s （i, j）与s （j, i）实际上是等价的。为了计算及研究的方便，本文将把各个销售点之间的距 离作为广义的物流成本来计算，假设每公里作为一个单位成 本，根据（4）、（5）两项公式可以得出下面的结果：s （1, 2）二dlo+ d20-（二）公司物流配送路线优化分析根据上面所列举的节约值，然后逐项考察对应的i-j, 并且将在下面详细讲述点对之间的连接过程。在路线的优化 过程中，对路线的优化要对其进行详细的分析最终才能得出 正确的规划路线。如果被考察的i-j中，若两点均不在线路 上，则考察i-j或j-i;若一点不在线路上，一点是外点， 则考察（i不在线路上、j是线路的起点，或i是线路的终 点、j不在线路上）或者j-i （j不在线路上、i是线路的起 点，或j是线路的终点、i不在线路上）；若两点都是线路上 的外点，则根据点的位置关系，构造成终点（一条线路）一 起点（另一条线路）的顺序。在考查点对