基于C.W节约算法及禁忌搜索的路径优化

徐锡芬

【摘 要】随着经济的发展，物流在社会生产和生活中扮演着越来越重要的作用，第三方物流企业在整个物流系统中占据着很大的比重。车辆运输路径（VRP）的选择直接影响着第三方物流公司的物流水平，合理的运输路线选择可以降低物流成本，增加与商家进行运输运价谈判的筹码。本文采用了启发式算法里的C.W节约算法，对运输路线进行设计，并用禁忌搜索对设计的每条路线进行检验是否最优，并尝试局部优化。

【关键词】第三方物流;VRP;C.W节约算法;禁忌搜索

一、绪论

近十多年来，第三方物流企业在我国成高速发展的态势，在这众多的中小物流企业中，大部分依然没能摆脱传统的物流运作模式。如何在中小物流企业管理技术力量不足，针对第三方物流企业运输配送特点与实际需求，以实现运输合理化为目标，进行运输配送方案优化，从而促进我国第三方物流企业的发展。

二、案例分析

P第三方物流公司要完成Q公司邯郸生产基地的销售物流业务，将邯郸生产的产品运往A～O 15个销售地。

已知P公司与A～O15个销售地之间以及各销售地之间的距离（km）如下表一。P公司有载重量为2t和4t的两种车辆可供使用，但车辆一次巡回的行驶距离不能超过40km。为简化模型，距离取两地之间的最短距离。假设往返距离相等。A-O十五点的需求量分别为：1.5、0.6、0.7、0.6、0.6、1.4、0.8、0.9、0.3、1.2、0.4、0.6、0.8、0.7、0.9。

表一 各销售地之间的距离 单位：km

三、优化方案

（一）运用C.W节约算法优化求解

第一步：根据最短距离表，计算节约值Sij。当节约值Sij为负数时，无实际意义，故取值为零。

第二步：所有的节约值Sij按从大到小的顺序排列，见下表三。

第三步：按照节约值Sij的大小顺序，以及车辆载重量和行驶距离的限制，逐步构造配送线路。

（1）线路合并

按节约值的上述顺序，逐个考察其端点i和j，若满足以下条件，则连接i、j。其条件是：

a、点i和点j不在一条线路上

b、点i和点j均与基点相邻。

（2）重复此步骤，知道将所有的点考察结束。

得到最终的结果如下：P-I-A-C-H-L-P;P-F-O-K-N-B-P和P-G-M-D

-J-E-P。总的行驶路程为111km，原来的一对一往返路线的路程为200km，比之前节约了89km的运力。

（二）运用禁忌搜索进行检验并尝试优化

运用禁忌搜索对以求得的路线进行检验是否为最优，若不是，对其进行优化。

（1）对P-I-A-C-H-L-P的检验：

初始解x0=（PIACHLP）， f（x0）=36，设定禁忌长度为4

发现候选解的评价值都比原始值要大，所以f（x0）已为最优

（2）同理对P-F-O-K-N-B-P 和P-G-M-D-J-E-P进行同样的禁忌搜索，发现候选解的评价值都要比原始值要大。

因此检验结果为P公司该情景下，通过C.W节约算法得出的路线即为最优路线。该公司的配送方案为：派遣三辆载重量为4t的运输车，派送路线分别为P-I-A-C-H-L-P、P-F-O-K-N-B-P 和P-G-M-D-J-E-P。

【参考文献】

[1]郭娜. 基于节约算法和移动方向的禁忌搜索算法[D]. 大连：大连理工大学，2009：5-9.

[2]葛玉玺.基于C.W节约算法的第三方物流运输优化研究[D]. 赣州：江西理工大学，2011：1-2.

[3]蒋长兵.运输与配送管理建模与仿真[M]. 北京：中国物资出版社，2011.