求VRPTW问题的并行协同混合差异演化算法

马立肖

摘要：车辆路径优化问题的研究对物流配送系统的发展具有重要意义。寻找带时间窗的车辆路由问题的最优求解策略是其中的研究热点之一。该文提出并行协同混合差异演化算法用于该问题的求解，仿真实验结果表明该算法在问题求解中表现出良好的有效性和可靠性。

关键词:带时间窗的车辆路径问题;差异演化算法;协同进化;合作型协同进化;竞争型协同进化

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)20-4970-04

Co-evolutionary Mixed Differential Evolutionary Algorithm for VRP with Time Windows Problem

MA Li-xiao

(Shijiazhuang University of Economics,Shijiazhuang 050031,China)

Abstract：Research on vehicle routing problem is of great importance in logistics distribution system.For the vehicle routing problems with time windows, how to find a optimal strategy is one of difficult problem. In this work, a Co-evolutionary mixed differences evolutionary algorithm is designed to investigate the problem,The results of experiment show its dependability and feasibility.

Key words：VRP with time windows; differential Evolution; co-evolutionary; cooperative coevolution; Competitive collaborative evo? lution

车辆运输路径问题（Vehicle Routing Problem，简记为VRP）[1]的优化在物流配送中起重要的决策作用，它是指在车辆调度中对配送车辆的行驶路线方案的优化，找出优化后的配送车辆行驶路线方案，以提高货物运输效率，降低物流企业的运营成本。加入时间约束得到的带时间窗的车辆路径问题（VRP with Time Windows，简记为VRPTW）[2]是VRP扩展问题的一个广泛研究的分支问题。

VRPTW问题在当今的经济发展中具有非常重要的现实意义，也是相关领域学者研究的焦点之一。常用的求解方法可以分为精确算法和启发式算法。近年来，启发式算法以其在求解大规模复杂问题方面的优越性，广泛应用在VRPTW问题的求解中，例如马为民[3]在其博士论文中用在线和竞争策略研究了带时间窗的开放式VRPTW，冯萍[4]在其硕士论文中用插入法、遗传算法、模拟退火算法研究了带软时间窗的车辆路径问题，东北大学姜大立[5]等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。然而，目前的求解方法在大规模问题求解中，仍无法突破局部最优解的局限，因此，如何有效利用问题空间的有效信息，提高算法的局部搜索能力仍是一个值得研究的问题。

该文将差异演化算法与协同进化机制进行结合，充分利用了差异演化算法搜索速度快的优点，同时通过协同进化机制，促使种群间进行信息交流，防止陷入局部最优。

2.2.3基于并行协同机制的多种群的生成

步骤1：依据3.2.2方法随机生成3个初始化种群POP1，POP2，POP3；

步骤2：生成随机数r∈{1，2，3}，将POPr作为进化主种群；

步骤3：将POPr作为合作型种群模板，固定种群中染色体中0基因位，依据种群生成策略生成3个合作种群POPr1，POPr2，POPr3。

步骤4：生成随机整数h和f（h≠f≠r，且h,f∈{1，2，3}），指定种群POPh作为学习种群，POPf作为评价种群；

2.2.4 DE的变异、交叉、选择算子

1)变异

从种群中随机选择3个个体Xp1，Xp2，Xp3(且p1≠p2≠p3),执行如下操作：Vj

3.1算法实例

某物流中心有5辆配送车辆，车辆的最大载重量均为8T，一次配送的最大行驶距离均为50Km，需要向20个客户送货。物流中心的坐标为（13.0Km，14.5km），20个客户的坐标及其货物需求量见表1：

表1物流信息表

要求合理安排行车路线使得配送总里程最短。为了简化起见，配送车辆在客户处的卸货时间不计，各客户之间及配送中心与客户之间的距离均采用直线距离，该距离可根据客户和配送中心的坐标计算得到。3.2实验环境及参数设置

实验环境：CPU-PIV2.8G，内存512M；操作系统Microsoft Windows xp，开发语言Microsoft Visual C++6.0。

实验参数设置如下：种群规模POPSIZE=20，编码长度d=26，最大进化代数T=200，缩放因子F=0.5，交叉概率CR=0.3。

3.3实验结果及分析

针对3.1节的实例，应用CODEGA算法与DE算法，随机运行10次后，实验结果如表2所示。

表2 CODEGA算法与DE算法结果对比

该文针对物流配送中车辆运输路线优化问题的VRPTW问题模型，提出了并行协同混合差异演化算法，实验结果表明应用该算法在找到优良解的效率和解的质量方面均表现出较好的性能，并行协同进化机制的引入，有效改善了DE算法的求解性能。

[1]纪寿文,缪立新,李克强.货运车辆优化调度方法[J].公路交通科技,2003,20(6):109-112.

[2]朗茂祥.物流配送车辆调度问题的模型和算法研究[D].北京：北方交通大学,2002:135-140.

[3]马卫民.第三方物流配送优化问题及其竞争策略[D].西安交通大学,2003.

[4]冯萍.退火遗传算法在运输路线规划中的应用[D].西安交通大学,2001.

[5]姜大立,杨西龙,杜文,周贤伟.车辆路径问题的遗传算法研究[J].系统工程理论与实践,1999,19(6).

[6]范李平.物流配送及其车辆优化调度研究[D].上海海事大学,2004.

[7] Storn R, Price K. Differential evolution–a simple and efficient adaptive scheme for global optimization over continuous spaces. Techni? cal report, International Computer Science Institute, Berkley,1995.

[8] Hillis W D.协同进化的寄生物改善作为优化手段的模拟进化[J].物理学,1990,42(1-3):228-234.

[9] Rosin C D.RKBelew.面向竞争协同进化的新方法[J].进化计算,1997,5(1):1-29.

[10] CartlidgeJ,BullockS.Combating Coevolutionary Disengagement by Reducing Parasite Virulence [J].Evolutionary computation,2004,12(2): 193.